A study of lattice reformulations for integer programming

Karen Aardal, Lara Scavuzzo and Laurence Wolsey ()
Additional contact information
Karen Aardal: Technische Universiteit Delft
Lara Scavuzzo: Technische Universiteit Delft
Laurence Wolsey: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3287, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Integer optimization; Lattice-based reformulation; Branching on general disjunctions (search for similar items in EconPapers)
Pages: 7
Date: 2024-01-01
Note: In: Operations Research Letters, 2023, vol. 51(4), p. 401-407
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3287

DOI: 10.1016/j.orl.2023.05.001

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().