Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/750

Title: Revisiting lagrange relaxation (LR) for processing large-scale mixed integer programming (MIP) problems
Authors: Siamitros, C
Mitra, G
Poojari, CA
Publication 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.
URI: http://carisma.brunel.ac.uk/papers/CTR-04-Christos.pdf
http://bura.brunel.ac.uk/handle/2438/750
Appears in Collections:Mathematical Science
Dept of Mathematics Research Papers

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.