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

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticle

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)173-189
Number of pages17
JournalTOP
Volume20
Issue number1
DOIs
StatePublished - Apr 1 2012
Externally publishedYes

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

Fingerprint Dive into the research topics of 'Dynamic Lagrangian dual and reduced RLT constructs for solving 0-1 mixed-integer programs'. Together they form a unique fingerprint.

  • Cite this