On the safety of Gomory cut generators.pdf.pdf' (540.48 kB)
Download file

On the safety of Gomory cut generators

Download (540.48 kB)
journal contribution
posted on 01.01.1987, 00:00 authored by Gerard CornuejolsGerard Cornuejols, Francois MargotFrancois Margot, Giacomo Nannicini

Gomory mixed-integer cuts are one of the key components in Branch-and-Cut solvers for mixed-integer linear programs. The textbook formula for generating these cuts is not used directly in open-source and commercial software due to the limited numerical precision of the computations: Additional steps are performed to avoid the generation of invalid cuts. This paper studies the impact of some of these steps on the safety of Gomory mixed-integer cut generators. As the generation of invalid cuts is a relatively rare event, the experimental design for this study is particularly important. We propose an experimental setup that allows statistically significant comparisons of generators. We also propose a parameter optimization algorithm and use it to find a Gomory mixed-integer cut generator that is as safe as a benchmark cut generator from a commercial solver even though it generates many more cuts.

History

Date

01/01/1987

Usage metrics

Exports