Abstract
For many years the principal solution technique used in the practice of mixed-integer programming has remained largely unchanged: Linear programming based branch-and-bound, introduced by Land and Doig (1960). This, in spite of the fact that there has been significant progress in the theory of integer programming and in the closely related field of combinatorial optimization. Many of the ideas developed there have received extensive computational testing, but, until recently, relatively little of that work has made it into the commercial codes used by practitioners. That situation has now changed. Several such codes, among them LINGO1, OSL2, and XPRESS-MP3, as well as the CPLEX4 code studied in this paper, now include cutting-plane capabilities as well as other ideas from the backlog of accumulated theory. As suggested by the title of this paper, the gap between theory and practice is indeed closing.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-0-387-35514-6_15
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
E. D. Anderson and K. D. Anderson (1995), Presolving in Linear Programming, Mathematical Programming, 71, No. 2, pp. 221–245.
A. Atamturk, G. L. Nemhauser and M. W. P. Savelsbergh (1998), Conflict Graphs in Integer Programming, Report LEC-98–03, Georgia Institute of Technology.
E. Balas, S. Ceria, G. Cornueljols and N. Natraj (1996), Gomory Cuts Revisited, Operations Research Letters, 19, pp. 1–10.
R. E. Bixby, S. Ceria, C. M. McZeal and M. W. P. Savelsbergh (1998), An Updated Mixed Integer Programming Library: MIPLIB 3.0, Optima, 54, pp. 12–15.
A. L. Brearley, G. Mitra and H. P. Williams (1975), Analysis of Mathematical Programming Problems Prior to Applying the Simplex Algorithm, Mathematical Programming, 8, pp. 54–83.
W. J. Carolan, J. E. Hill, J. L. Kennington, S. Niemi and S. J. Wichmann (1990), An Empirical Evaluation of the KORBX Algorithms for Military Airlift Applications, Operations Research, 38, No. 2, pp. 240–248.
V. Chvatâl (1983). Linear Programming, Freeman, New York.
H. P. Crowder, E. L. Johnson and M. W. Padberg (1983), Solving Large-Scale Zero-One Linear Programming Problems, Operations Research, 31, pp. 803–834.
J. R. Gilbert and T. Peierls (1988), Sparse Partial Pivoting in Time Proportional to Arithmetic Operations, SJSSC, 9, pp. 862–874.
R. E. Gomory (1960), An Algorithm for the Mixed Integer Problem, RM-2597, The Rand Corporation.
Z. Gu, G. L. Nemhauser and M. W. P. Savelsbergh (1998), Lifted Cover Inequalities for 0–1 Integer Programs, INFORMS Journal on Computing, 10, pp. 417–426.
Z. Gu, G. L. Nemhauser and M. W. P. Savelsbergh (1999), Lifted Flow Covers for Mixed 0–1 Integer Programs, Mathematical Programming, 85, pp. 439–467.
K. Hoffman and M. Padberg (1991), Improving Representations of Zero-one Linear Programs for Branch-and-Cut, ORSA Journal of Computing, 3, pp. 121–134.
E. Johnson (1999), Private communication.
E. L. Johnson and M. W. Padberg (1983), Degree-two Inequalities, Clique Facets, and Bipartite Graphs, Annals of Discrete Mathematics, 16, pp. 169–188.
A. H. Land and A. G. Doig (1960), An Automatic Method for Solving Discrete Programming Problems, Econometrica, 28, pp. 497520.
I. J. Lustig (1999), Private communication.
R. E. Marsten (1981), XMP: A Structured Library of Subroutines for Experimental Mathematical Programming, ACM Transactions on Mathematical Software, 7, pp. 481–497.
A. Martin and R. Weismantel (1995), Private communication.
M. W. Padberg, T. J. Van Roy and L. A. Wolsey (1985), Valid Linear Inequalities for Fixed Charged Problems, Operations Research, 33, pp. 842–861.
Jean-Francois Puget (1999), Private communication.
E. Rothberg and A. Gupta (1991), Efficient Sparse Matrix Factorization on High Performance Workstations Exploiting the Mem- ory Hierarchy, ACM Transactions on Mathematical Software, 17, No. 3, pp. 313–334.
E. Rothberg and B. Hendrickson (1998), Sparse Matrix Ordering Methods for Interior Point Linear Programming, INFORMS Journal on Computing, 10, No. 1, pp. 107–113.
M. W. P. Savelsbergh (1994), Preprocessing and Probing for Mixed Integer Programming Problems, ORSA Journal on Computing, 6, pp. 445–454.
U. H. Suhl and R. Szymanski (1994), Supernode Processing of Mixed-Integer Models, Computational Optimization and Applications, 3, pp. 317–331.
P. Van Hentenryck (1999), The OPL Optimization Programming Language,MIT Press.
R. Weismantel (1997), On the 0/1 Knapsack Polytope, Mathematical Programming, 77, pp. 49–68.
L. A. Wolsey (1998), Integer Programming,Wiley.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 IFIP International Federation for Information Processing
About this paper
Cite this paper
Bixby, E.R., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R. (2000). MIP: Theory and Practice — Closing the Gap. In: Powell, M.J.D., Scholtes, S. (eds) System Modelling and Optimization. CSMO 1999. IFIP — The International Federation for Information Processing, vol 46. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-35514-6_2
Download citation
DOI: https://doi.org/10.1007/978-0-387-35514-6_2
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4757-6673-8
Online ISBN: 978-0-387-35514-6
eBook Packages: Springer Book Archive