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
Authors: Siamitros, C
Mitra, G
Poojari, CA
Issue Date: 2004
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:Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
CTR-04-Christos.pdf660.25 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.