Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs

• Hanif D. Sherali ^[2] ; J. Cole Smith ^[1]
  1. [1] University of Florida

     University of Florida

     Estados Unidos

     
  2. [2] Virginia Polytechnic Institute and State University, USA
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 20, Nº. 1, 2012, págs. 173-189
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • 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.