Aardal, Karen, Lodi, Andrea, Tramontani, Andrea, von Heymann, Frederik and Wolsey, Laurence A. (2021). LATTICE REFORMULATION CUTS. SIAM J. Optim., 31 (4). S. 2539 - 2558. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7189
Full text not available from this repository.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 vertical bar Ax = b, x is an element of Z(+)(n)}, where the reformulation takes the form max{cx(0) + cQ mu vertical bar Q mu >= -x(0), mu is an element of Z(n-m)} , where Q is an n x (n - m) integer matrix. Working on an optimal LP-tableau in the mu-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 mu. 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.
| Item Type: | Journal Article | ||||||||||||||||||||||||
| Creators: |
|
||||||||||||||||||||||||
| URN: | urn:nbn:de:hbz:38-592079 | ||||||||||||||||||||||||
| DOI: | 10.1137/19M1291145 | ||||||||||||||||||||||||
| Journal or Publication Title: | SIAM J. Optim. | ||||||||||||||||||||||||
| Volume: | 31 | ||||||||||||||||||||||||
| Number: | 4 | ||||||||||||||||||||||||
| Page Range: | S. 2539 - 2558 | ||||||||||||||||||||||||
| Date: | 2021 | ||||||||||||||||||||||||
| Publisher: | SIAM PUBLICATIONS | ||||||||||||||||||||||||
| Place of Publication: | PHILADELPHIA | ||||||||||||||||||||||||
| ISSN: | 1095-7189 | ||||||||||||||||||||||||
| Language: | English | ||||||||||||||||||||||||
| Faculty: | Unspecified | ||||||||||||||||||||||||
| Divisions: | Unspecified | ||||||||||||||||||||||||
| Subjects: | no entry | ||||||||||||||||||||||||
| Uncontrolled Keywords: |
|
||||||||||||||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/59207 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
 |
View Item |