A study of lattice reformulations for integer programming

Karen Aardal*, Lara Scavuzzo, Laurence A. Wolsey

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

59 Downloads (Pure)

Abstract

Branch-and-bound for integer optimization typically uses single-variable disjunctions. Enumerative methods for integer optimization with theoretical guarantees use a non-binary search tree with general disjunctions based on lattice structure. These disjunctions are expensive to compute and challenging to implement. Here we compare two lattice reformulations that can be used to heuristically obtain general disjunctions in the original space, we develop a new lattice-based variant, and compare the derived disjunctions computationally with those produced by the algorithm of Lovász and Scarf.

Original languageEnglish
Pages (from-to)401-407
Number of pages7
JournalOperations Research Letters
Volume51
Issue number4
DOIs
Publication statusPublished - 2023

Keywords

  • Branching on general disjunctions
  • Integer optimization
  • Lattice-based reformulation

Fingerprint

Dive into the research topics of 'A study of lattice reformulations for integer programming'. Together they form a unique fingerprint.

Cite this