A study of lattice reformulations for integer programming

Aardal, K.I.; Scavuzzo Montaña, L.V.; Wolsey, Laurence A.

doi:10.1016/j.orl.2023.05.001

A study of lattice reformulations for integer programming

Title

A study of lattice reformulations for integer programming

Author

Aardal, K.I. (TU Delft Discrete Mathematics and Optimization)
Scavuzzo Montaña, L.V. (TU Delft Discrete Mathematics and Optimization)
Wolsey, Laurence A. (Université Catholique de Louvain)

Date

2023

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.

Subject

Branching on general disjunctions
Integer optimization
Lattice-based reformulation

To reference this document use:

http://resolver.tudelft.nl/uuid:556a4752-ba2e-4e8b-8b2a-af1c578409ad

DOI

https://doi.org/10.1016/j.orl.2023.05.001

ISSN

0167-6377

Source

Operations Research Letters, 51 (4), 401-407

Part of collection

Institutional Repository