Lattice Reformulation Cuts

Karen Aardal, Andrea Lodi, Andrea Tramontani, Frederik von Heymann and Laurence A. Wolsey

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

Abstract: Here we consider the question whether the lattice reformulation of a linear integer program can be used to produce effective cutting planes. In particular, we aim at deriving split cuts that cut off more of the integrality gap than Gomory mixed-integer (GMI) inequalities generated from LP-tableaus, while being less computationally demanding than generating the split closure. We consider integer programs (IPs) in the form max{cx∣Ax=b,x∈Zn+}, where the reformulation takes the form max{cx0+cQμ∣Qμ≥−x0, μ∈Zn−m}, where Q is an n×(n−m) integer matrix. Working on an optimal LP-tableau in the μ-space allows us to generate n−m GMIs in addition to the m GMIs associated with the optimal tableau in the x space. These provide new cuts that can be seen as GMIs associated to n−m nonelementary split directions associated with the reformulation matrix Q. On the other hand it turns out that the corner polyhedra associated to an LP basis and the GMI or split closures are the same whether working in the x or μ spaces. Our theoretical derivations are accompanied by an illustrative computational study. The computations show that the effectiveness of the cuts generated by this approach depends on the quality of the reformulation obtained by the reduced basis algorithm used to generate Q and that it is worthwhile to generate several rounds of such cuts. However, the effectiveness of the cuts deteriorates as the number of constraints is increased.

Keywords: Integer programming; cutting planes; lattice reformulations; lattice basis reduction (search for similar items in EconPapers)
Pages: 19
Date: 2023-01-01
Note: In: SIAM Journal on Optimization, 2021, vol. 31(4), p. 2539-2557
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:3223

DOI: 10.1137/19M1291145

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 ().