A study of lattice reformulations for integer programming

Aardal, Karen;Scavuzzo, Lara;Wolsey, Laurence
(2023) Operations Research Letters — Vol. 51, n° 4, p. 401-407 (2023)

Files

CORE_RP_3287.pdf
  • Open Access
  • Adobe PDF
  • 709.42 KB
Download

Details

Authors
  • Aardal, KarenTechnische Universiteit Delft
    Author
  • Scavuzzo, LaraTechnische Universiteit Delft
    Author
  • Wolsey, LaurenceUCLouvain
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Aardal, K., Scavuzzo, L., & Wolsey, L. (2023). A study of lattice reformulations for integer programming. Operations Research Letters, 51(4), 401-407. https://doi.org/10.1016/j.orl.2023.05.001 (Original work published 2023)