Another pedagogy for pure-integer Gomory
He, Qi1 ; Lee, Jon1
1 IOE Department, University of Michigan, Ann Arbor, MI, USA.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 189-197.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016013
Classification : 90C10
Mots-clés : Gomory cut, Chvátal–Gomory cut, cutting plane, integer program, integer linear program, integer optimization, simplex algorithm, lexicographical
He, Qi 1 ; Lee, Jon 1

1 IOE Department, University of Michigan, Ann Arbor, MI, USA. 
@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  - 
%0 Journal Article
%A He, Qi
%A Lee, Jon
%T Another pedagogy for pure-integer Gomory
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 189-197
%V 51
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2016013/
%R 10.1051/ro/2016013
%G en
%F RO_2017__51_1_189_0
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

S.S. Dey and J.-Philippe Richard, Linear-programming-based lifting and its application to primal cutting-plane algorithms. INFORMS J. Comput. 21 (2009) 137–150. | DOI | MR | Zbl

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

C.E. Lemke, 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 :