Please use this identifier to cite or link to this item:
|Title:||Revisiting lagrange relaxation (LR) for processing large-scale mixed integer programming (MIP) problems|
|Publisher:||The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University|
|Citation:||The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University; Technical Reports; CTR/04/03; Apr 2004|
|Abstract:||Lagrangean Relaxation has been successfully applied to process many well known instances of NP-hard Mixed Integer Programming problems. In this paper we present a Lagrangean Relaxation based generic solver for processing Mixed Integer Programming problems. We choose the constraints, which are relaxed using a constraint classification scheme. The tactical issue of updating the Lagrange multiplier is addressed through sub-gradient optimisation; alternative rules for updating their values are investigated. The Lagrangean relaxation provides a lower bound to the original problem and the upper bound is calculated using a heuristic technique. The bounds obtained by the Lagrangean Relaxation based generic solver were used to warm-start the Branch and Bound algorithm; the performance of the generic solver and the effect of the alternative control settings are reported for a wide class of benchmark models. Finally, we present an alternative technique to calculate the upper bound, using a genetic algorithm that benefits from the mathematical structure of the constraints. The performance of the genetic algorithm is also presented.|
|Appears in Collections:||Mathematical Science|
Dept of Mathematics Research Papers
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.