Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

In this paper, we consider the generation of disjunctive cuts for 0-1 mixed-integer programs by conducting a partial exploration of the branch-and-bound tree using quick Lagrangian primal and dual updates. We analyze alternative cut generation strategies based on formulating different disjunctions and adopting various choices of normalization techniques, and indicate how these inequalities can also be generated using a projection from a related high-order lifted formulation obtained via the Reformulation-Linearization Technique of Sherali and Adams. We conclude by presenting a brief computational study that motivates the potential benefits of this procedure.

Original languageEnglish (US)
Pages (from-to)127-139
Number of pages13
JournalOptimization Letters
Volume6
Issue number1
DOIs
StatePublished - Jan 1 2012
Externally publishedYes

Keywords

  • Disjunctive cuts
  • Lagrangian dual
  • Partial enumeration
  • Reformulation-Linearization Technique (RLT)
  • Valid inequalities

ASJC Scopus subject areas

  • Control and Optimization

Fingerprint Dive into the research topics of 'Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs'. Together they form a unique fingerprint.

  • Cite this