Iterated Chvátal--Gomory cuts and the geometry of numbers

Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207 and Letchford, Adam 2014. Iterated Chvátal--Gomory cuts and the geometry of numbers. SIAM Journal on Optimization 24 (3) , pp. 1294-1312. 10.1137/130926389

Preview

PDF - Accepted Post-Print Version Download (279kB) | Preview

Abstract

Chvátal--Gomory cutting planes (CG-cuts for short) are a fundamental tool in integer programming. Given any single CG-cut, one can derive an entire family of CG-cuts, by “iterating' its multiplier vector modulo one. This leads naturally to two questions: first, which iterates correspond to the strongest cuts, and, second, can we find such strong cuts efficiently? We answer the first question empirically, by showing that one specific approach for selecting the iterate tends to perform much better than several others. The approach essentially consists of solving a nonlinear optimization problem over a special lattice associated with the CG-cut. We then provide a partial answer to the second question, by presenting a polynomial-time algorithm that yields an iterate that is strong in a certain well-defined sense. The algorithm is based on results from the algorithmic geometry of numbers.

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	1052-6234
Date of First Compliant Deposit:	30 March 2016
Date of Acceptance:	14 April 2014
Last Modified:	27 Nov 2024 20:00
URI:	https://orca.cardiff.ac.uk/id/eprint/70672

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item