Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/750
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Siamitros, C | - |
dc.contributor.author | Mitra, G | - |
dc.contributor.author | Poojari, CA | - |
dc.coverage.spatial | 60 | en |
dc.date.accessioned | 2007-05-09T14:16:00Z | - |
dc.date.available | 2007-05-09T14:16:00Z | - |
dc.date.issued | 2004 | - |
dc.identifier.citation | The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University; Technical Reports; CTR/04/03; Apr 2004 | en |
dc.identifier.uri | http://carisma.brunel.ac.uk/papers/CTR-04-Christos.pdf | en |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/750 | - |
dc.description.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. | en |
dc.format.extent | 676091 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University | en |
dc.title | Revisiting lagrange relaxation (LR) for processing large-scale mixed integer programming (MIP) problems | en |
dc.type | Working Paper | en |
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.