TY - JOUR
T1 - Dynamic Lagrangian dual and reduced RLT constructs for solving 0-1 mixed-integer programs
AU - Sherali, Hanif D.
AU - Smith, J. Cole
N1 - Funding Information:
Acknowledgements This research has been supported in part by the National Science Foundation under Grant No. CMMI-0969169 and by the Office of Naval Research under Grant No. N00014-03-1-0510. This paper is dedicated to Dr. Joaquim Judice on the occasion of his 60th birthday. The authors also thank the Guest Editor, Luis N. Vicente, and two anonymous referees for their constructive comments.
PY - 2012/4
Y1 - 2012/4
N2 - 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.
AB - 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.
KW - Delayed relax-and-cut approach
KW - Dynamic Lagrangian dual
KW - Mixed-integer programming
KW - Reformulation-Linearization Technique (RLT)
KW - Valid inequalities
UR - http://www.scopus.com/inward/record.url?scp=84859504252&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84859504252&partnerID=8YFLogxK
U2 - 10.1007/s11750-011-0199-3
DO - 10.1007/s11750-011-0199-3
M3 - Article
AN - SCOPUS:84859504252
SN - 1134-5764
VL - 20
SP - 173
EP - 189
JO - TOP
JF - TOP
IS - 1
ER -