Extended formulations for Gomory Corner polyhedra

Köppe, Matthias; Louveaux, Quentin; Weismantel, Robert; Wolsey, Laurence A.

doi:10.1016/j.disopt.2004.06.001

Download

Article (Scientific journals)

Extended formulations for Gomory Corner polyhedra

Köppe, Matthias; Louveaux, Quentin; Weismantel, Robert et al.

2004 • In Discrete Optimization, 1 (2), p. 141-165

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/1133

DOI
10.1016/j.disopt.2004.06.001

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

reformulations_preprint.pdf

Author preprint (479.59 kB)

Download

The published version is available at ScienceDirect

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Integer Programming; Gomory group relaxation; Extended formulations

Abstract :

[en] We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory’s group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation.

Research center :

Center for Operations Research and Econometrics

Disciplines :

Computer science
Mathematics

Author, co-author :

Köppe, Matthias; Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung

Louveaux, Quentin ; Université catholique de Louvain > CORE, INMA

Weismantel, Robert; Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung

Wolsey, Laurence A.; Université catholique de Louvain > CORE, INMA

Language :

English

Title :

Extended formulations for Gomory Corner polyhedra

Publication date :

2004

Journal title :

Discrete Optimization

ISSN :

1572-5286

eISSN :

1873-636X

Publisher :

Elsevier

Volume :

Issue :

Pages :

141-165

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B7GWV-4DBCFC5-1&_user=532038&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000026659&_version=1&_urlVersion=0&_userid=532038&md5=3f1f956a0a95137d961dd32e0e61dc26

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique

Available on ORBi :

since 25 November 2008

Statistics

Number of views

154 (5 by ULiège)

Number of downloads

182 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

K. Aardal, R. Weismantel, and L. Wolsey Non-standard approaches to integer programming Discrete Appl. Math. 123 2002 5 74
J. Aráoz, L. Evans, R.E. Gomory, and E.L. Johnson An approach to integer programming Math. Programming Ser. B 96 2 2003 377 408
R.E. Gomory Some polyhedra related to combinatorial problems Linear Algebra Appl. 2 1969 451 558
R.E. Gomory, and E. Johnson Some continuous functions related to corner polyhedra I Math. Programming 3 1972 23 85
R.E. Gomory, and E. Johnson Some continuous functions related to corner polyhedra II Math. Programming 3 1972 359 389
R.E. Gomory, and E. Johnson The group problem and subadditive functions Math. Programming 1973 157 184
R.E. Gomory, and E. Johnson T-space and cutting planes Math. Programming Ser. B 96 2003 341 375
R.E. Gomory, E. Johnson, and L. Evans Corner polyhedra and their connection with cutting planes Math. Programming Ser. B 96 2003 321 339
G.A. Gorry, W.D. Northup, and J.F. Shapiro Computational experience with a group theoretic integer programming algorithm Math. Programming 4 1973 171 192
U.-U. Haus, M. Köppe, and R. Weismantel A primal all-integer algorithm based on irreducible solutions Math. Programming Ser. B 96 2003 205 246
M. Köppe, Exact primal algorithms for general integer and mixed-integer linear programs, PhD Thesis, Otto-von-Guericke-Universität Magdeburg, 2002 (Published by Shaker Verlag, Aachen, 2003).
M. Köppe. Tables of primitive partition identities, Available from http://www.math.uni-magdeburg.de/~mkoeppe/art/ppi/, 2003.
L.A. Wolsey A number theoretic reformulation and decomposition method for integer programming Discrete Math. 7 1974 393 403