Hybrid methods for solving Lagrangean duals and applications in mixed integer programming / Shunping Zhu.

Zhu, Shunping.
xiii, 126 leaves : ill ; 29 cm.
Local subjects:
Penn dissertations -- Managerial science and applied economics.
Managerial science and applied economics -- Penn dissertations.
This research considers Lagrangean schemes for (mixed) integer programming models in production scheduling and distribution systems. In particular, it focuses on new hybrid methods for solving Lagrangean duals, which yield better bounds in fewer iterations than traditional subgradient methods. The hybrid methods optimize the subgradient methods by exchanging information between Lagrangean subproblems and Dantzig-Wolfe master problems. This overcomes well-known disadvantages of traditional subgradient methods which have no stopping criterion and no precise target value, so that users are forced to use heuristic rules to adjust problem dependent parameters such as target value and step size. These disadvantages have limited the implementation of subgradient methods for more than 20 years.
The new hybrid methods provide steadily improving target values from the master problems while updating multipliers in subgradient iterations. In each iteration, a bracket over the Lagrangean dual value, and hence a stopping criterion as well, is provided by solving the dual master problem and Lagrangean subproblems. With no parameter to set, one can automate the Lagrangean relaxation process, and speed up the solution for (mixed) integer programming problems.
To test the robustness of the hybrid methods, we selected several applications for which Lagrangean relaxation, decomposition, or substitution may be employed. The applications are: the generalized assignment problem, the bi-dimensional knapsack problem, a forest management problem, and a fishing fleet dispatching problem. This gives the hybrid methods a broad exposure to different types of problem structures.
The hybrid methods were tested against traditional subgradient methods for solving the corresponding Lagrangean duals. For all examples tested, better convergence patterns in terms of bound quality and number of subgradient iterations were observed with the hybrid methods. Coupled with Lagrangean heuristics, the hybrid methods consistently found good feasible (and in most instances optimal) solutions.
Supervisor: Monique Guignard-Spielberg.
Thesis (Ph.D. in Managerial Science and Applied Economics) -- University of Pennsylvania, 1995.
Includes bibliographical references.
Local notes:
University Microfilms order no.: 95-32312.
Guignard-Spielberg, Monique, advisor.
University of Pennsylvania.
Location Notes Your Loan Policy
Description Status Barcode Your Loan Policy