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 |
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. |
URI: | http://carisma.brunel.ac.uk/papers/CTR-04-Christos.pdf http://bura.brunel.ac.uk/handle/2438/750 |
Appears in Collections: | Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
CTR-04-Christos.pdf | 660.25 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.