We present pure-integer Gomory cuts in a way so that they are derived with respect to a “dual form” pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In this manner, we obtain a finitely-terminating version of pure-integer Gomory cuts that employs the primal rather than the dual simplex algorithm.
Accepté le :
DOI : 10.1051/ro/2016013
Mots clés : Gomory cut, Chvátal–Gomory cut, cutting plane, integer program, integer linear program, integer optimization, simplex algorithm, lexicographical
@article{RO_2017__51_1_189_0, author = {He, Qi and Lee, Jon}, title = {Another pedagogy for pure-integer {Gomory}}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {189--197}, publisher = {EDP-Sciences}, volume = {51}, number = {1}, year = {2017}, doi = {10.1051/ro/2016013}, mrnumber = {3603501}, zbl = {1358.90077}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2016013/} }
TY - JOUR AU - He, Qi AU - Lee, Jon TI - Another pedagogy for pure-integer Gomory JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 189 EP - 197 VL - 51 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016013/ DO - 10.1051/ro/2016013 LA - en ID - RO_2017__51_1_189_0 ER -
He, Qi; Lee, Jon. Another pedagogy for pure-integer Gomory. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 189-197. doi : 10.1051/ro/2016013. http://www.numdam.org/articles/10.1051/ro/2016013/
M. Conforti, G. Cornuéjols and G. Zambelli, Integer programming. Vol. 271 of Grad. Texts Math. Springer (2014). | MR | Zbl
Linear-programming-based lifting and its application to primal cutting-plane algorithms. INFORMS J. Comput. 21 (2009) 137–150. | DOI | MR | Zbl
and ,R.E. Gomory, An algorithm for integer solutions to linear programs. Recent advances in mathematical programming. McGraw-Hill, New York (1963) 269–302. | MR | Zbl
J. Lee, A first course in combinatorial optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2004). | MR | Zbl
J. Lee, A first course in linear optimization (Second edition, version 2.1), Reex Press. Available at https://github.com/jon77lee/JLee˙LinearOptimizationBook (2013).
J. Lee and Angelika Wiegele, Another pedagogy for mixed-integer gomory, Tech. report. Preprint [math.OC], available at (2015). | arXiv | MR
The dual method of solving the linear programming problem. Naval Res. Logist. Quart. 1 (1954) 36–47. | DOI | MR | Zbl
,G.L. Nemhauser and Laurence A. Wolsey, Integer and combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York (1988). | MR | Zbl
R. Gary Parker and R.L. Rardin, Discrete optimization. Computer Science and Scientific Computing. Academic Press, Inc., Boston, MA (1988). | MR | Zbl
H.M. Salkin and K. Mathur, Foundations of integer programming. North-Holland Publishing Co., New York (1989). | MR | Zbl
A. Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester (1986). | MR | Zbl
Cité par Sources :