Numerical solutions to the Lagrangean relaxations of certain difficult mathematical programming problems involving integer variables
by Ornatsky, Alexander, Ph.D., UNIVERSITY OF PENNSYLVANIA, 2007, 201 pages; 3260963
 Abstract: In this thesis we propose a novel way to use subgradients and the Lagrangean multipliers to construct good feasible solutions for optimization problems involving integer variables. We apply our approach to two difficult problems. First, we consider the Multi-Item Capacitated Lot-Sizing Problem with complicating variables, which make this problem challenging to solve. We start with relaxing the demand constraints and use the bundle algorithm to solve the corresponding Lagrangean relaxation. To accelerate the algorithm we develop an efficient heuristic to quickly generate feasible solutions for subproblems by constructing 'profitable' production plans for each item and treating the Lagrangean multipliers as 'prices'. Subgradients from those solutions enrich the cutting-plane approximation used in the bundle. Embedded in a line-search, this heuristic significantly improved the performance of the bundle algorithm. To get a feasible solution for the whole problem we use optimal Lagrangean multipliers and extend the heuristic logic by introducing the coordination in selecting production plans for different items from different periods. If some demands remain unfilled, we fix the variables and solve the Lagrangean relaxation again. This process is repeated until all demands are met. With this approach we were able to efficiently obtain feasible solutions very close to optimal for the majority of the cases. Secondly, we generalize our approach further by noticing that the subgradients from solving the Lagrangean relaxation may contain elements of a feasible solution to a primal problem. We apply this approach to the Multi-Period Forest Harvesting Problem, which becomes difficult to solve when bounds on the total volume harvested are introduced for each period. To construct a feasible solution we first fix variables so that the solution will meet the lower bounds. Those variables are determined from subgradients after we relax the bounds and solve the corresponding Lagrangean relaxation. Then the primal problem is solved without the complicating bounds and the solution is adjusted to meet the upper bounds. With this approach good solutions have been obtained to some large-scale instances of the problem. Overall, proposed approach based on using subgradients and the Lagrangean multipliers represents an efficient path to obtaining good feasible solutions.

 Adviser Monique Guignard-Spielberg School UNIVERSITY OF PENNSYLVANIA Source DAI/B 68-04, p. , Aug 2007 Source Type Dissertation Subjects Operations research Publication Number 3260963
Access the complete dissertation:

» Find an electronic copy at your library.
 Use the link below to access a full citation record of this graduate work: http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3260963 If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).