.png){kind=icon}
.png){kind=icon}
Return
Lexicography and degeneracy: can a pure cutting plane algorithm work?
.png){kind=icon}
PRE
AI
DOI：10.1007/s10107-009-0335-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for ILP problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon.
Keywords:
Cutting plane methods
Gomory cuts
Degeneracy in linear programming
Lexicographic dual simplex
Computational analysis
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.6
Papers:
195
Citations:
1.9K