Abstract
In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0-1 linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.
Original language | English (US) |
---|---|
Pages (from-to) | 173-189 |
Number of pages | 17 |
Journal | TOP |
Volume | 20 |
Issue number | 1 |
DOIs | |
State | Published - Apr 2012 |
Externally published | Yes |
Keywords
- Delayed relax-and-cut approach
- Dynamic Lagrangian dual
- Mixed-integer programming
- Reformulation-Linearization Technique (RLT)
- Valid inequalities
ASJC Scopus subject areas
- Modeling and Simulation
- Discrete Mathematics and Combinatorics
- Management Science and Operations Research
- Information Systems and Management