A study of lattice reformulations for integer programming

Journal article (2023)

Authors

K.I. Aardal Discrete Mathematics and Optimization - EEMCS
L.V. Scavuzzo Montaña Discrete Mathematics and Optimization - EEMCS
Laurence A. Wolsey Université Catholique de Louvain
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2023 K.I. Aardal, L.V. Scavuzzo Montaña, Laurence A. Wolsey
DOI: https://doi.org/10.1016/j.orl.2023.05.001
More Info
expand_more

Published Date

2023

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.