Lagrangean relaxation method for large-scale optimization models : application to the unit commitment problem in a power generation system = 대규모 최적화 모형을 위한 라그란쥐완화기법의 향상 방안에 관한 연구 : 발전시스템 기동정지계획에의 응용 application to the unit commitment problem in a power generation system

Many decision problems are now formulated as mathematical programs, requiring the maximization or minimization of an objective function subject to constraints. Such programs often have special structure. In truly large problems, some definite structure is almost always found since these commonly arise from a linking of independent subunits in either time or space. By developing specialized solution algorithms to take advantage of this structure, significant gains in computational efficiency and reductions in computer memory requirements may be achieved. Such methods are mandatory for truly large problems, which cannot otherwise be solved because of time and/or storage limitations. One of the most computationally useful ideas of the 1970s is the observation that many hard problems can be viewed as easy problems complicated by a relatively small set of global constraints which concern all subunits. Lagrangean duality, also referred to as Lagrangean relaxation, incorporates the complicating constraints into the objective function via Lagrangean multipliers, resulting in a problem that only contains the simple constraints. Despite the possible presence of a duality gap, this fact and the desirable properties of the dual function make this approach appealing in many respects. So this approach has led to dramatically improved algorithms for a number of important problems in the areas of routing, location, scheduling, assignment, set covering and so forth. Recently, there has been a great deal of interest in the area of nondifferentiable optimization. Nondifferential optimization arises naturally in many eigenvalue and min-max problems. Particularly, even if the original functions are differentiable, the Lagrangean dual function is not differentiable, thus necessitating special schemes for its maximization. Furthermore, in many large scale optimization problems, the set of variables can be decomposed in two sets, where an optimal solution can be easily obtained as one...
Kim, Se-Hunresearcher김세헌researcher
Issue Date
68142/325007 / 000835275

학위논문(박사) - 한국과학기술원 : 경영과학과, 1993.8, [ vi, 111 p. ]

Appears in Collection
Files in This Item
There are no files associated with this item.
  • Hit : 78
  • Download : 0
  • Cited 0 times in thomson ci


  • mendeley


rss_1.0 rss_2.0 atom_1.0