Skip to main content
SpringerLink
Log in

Integer-Programming Software Systems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Recent developments in integer-programming software systems have tremendously improved our ability to solve large-scale instances. We review the major algorithmic components of state-of-the-art solvers and discuss the options available to users for adjusting the behavior of these solvers when default settings do not achieve the desired performance level. Furthermore, we highlight advances towards integrated modeling and solution environments. We conclude with a discussion of model characteristics and substructures that pose challenges for integer-programming software systems and a perspective on features we may expect to see in these systems in the near future.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aardal, K., C.A.J. Hurkens, and A.K. Lenstra. (2000). “Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables.” Mathematics of Operations Research 25(3), 427–442.

    Article  Google Scholar 

  • Aardal, K. and A. Lenstra. (2002). “Hard Equality Constrained Integer Knapsacks.” In W. Cook and A. Schultz (eds.), Proc. 9th International IPCO Conference Springer-Verlag, pp. 350–366.

  • Anderson, E.D. and K.D. Anderson. (1995). “Presolving in Linear Programming.” Mathematical Programming 71, 221–225.

    Google Scholar 

  • Atamtürk, A. (2003a). “On the Facets of Mixed-Integer Knapsack Polyhedron.” Mathematical Programming 98, 145–175.

    Article  Google Scholar 

  • Atamtürk, A. (2003b). “Strong Formulations of Robust Mixed 0-1 Programming.” Research Report BCOL.03.04. Available at http://ieor.berkeley.edu/~atamturk (To appear in Mathematical Programming).

  • Atamtürk, A. and M. Zhang. (2004). “Two-Stage Robust Network Flow and Design for Demand Uncertainty.” Research Report BCOL.04.03. Available at http://ieor.berkeley.edu/~atamturk.

  • Balas, E. (1975). “Facets of the Knapsack Polytope.” Mathematical Programming 8, 146–164.

    Article  Google Scholar 

  • Balas, E., S. Ceria, G. Cornuéjols, and N. Natraj. (1996). “Gomory Cuts Revisited.” Operations Research Letters 19, 1–9.

    Article  Google Scholar 

  • Balas, E. and E. Zemel. (1978). “Facets of the Knapsack Polytope from Minimal Covers.” SIAM Journal of Applied Mathematics 34, 119–148.

    Article  Google Scholar 

  • Barany, I., T.J. Van Roy, and L.A. Wolsey. (1984). “Uncapacitated lot Sizing: The Convex Hull of Solutions.” Mathematical Programming Study 22, 32–43.

    Google Scholar 

  • Beale, E.M.L. (1979). “Branch and Bound Methods for Mathematical Programming Systems.” In P.L. Hammer, E.L. Johnson, and B.H. Korte (eds.), Discrete Optimization II, North Holland Publishing Co, pp. 201–219.

  • Bénichou, M., J.M. Gauthier, P. Girodet, G. Hentges, G. Ribière, and O. Vincent. (1971). “Experiments in Mixed-Integer Linear Programming.” Mathematical Programming 1, 76–94.

    Article  Google Scholar 

  • Bertsimas, D. and M. Sim. (2003). “Robust Discrete Optimization and Network Flows.” Mathematical Programming 98, 49–71.

    Article  Google Scholar 

  • Bienstock, D. (1996). “Computational Study of a Family of Mixed-Integer Quadratic Programming Problems.” Mathematical Programming 74, 121–140.

    Article  Google Scholar 

  • Birge, J.R. and F. Louveaux. (1997). Introduction to Stochastic Programming. New York: Springer Verlag.

    Google Scholar 

  • Bixby, R.E., M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. (2002). Mixed–integer programming: A progress report.

  • Codato, G. and M. Fischetti. (2004). “Combinatorial Benders' Cuts.” In D. Bienstock, and G.L. Nemhauser (eds.), Proc. 10th International IPCO Conference Springer-Verlag; pp. 178–195.

  • Cornuejols, G. and M. Dawande. (1998). “A Class of Hard Small 0-1 Programs.” In R.E. Bixby, E.A. Boyd, and R.Z. Rios-Mercado (eds.), Proc. 6th International IPCO Conference Springer-Verlag, pp. 284–293.

  • Crowder, H., E.L. Johnson, and M.W. Padberg. (1983). “Solving Large–Scale Zero-One Linear Programming Problems.” Operations Research 31, 803–834.

    Google Scholar 

  • Danna, E., E. Rothberg, and C.L. Pape. (2003). “Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions.” Technical report, ILOG, Inc.

  • Dash Optimization, L. (2004a). Proctor and Gamble Case Study.

  • Dash Optimization, L. (2004b). XPRESS-BCL Reference Manual—Release 2.6.

  • Dash Optimization, L. (2004c). XPRESS-Mosel Language Reference Manual—Release 1.4.

  • Dash Optimization, L. (2004d). XPRESS-Optimizer Reference Manual—Release 15.

  • Farias, I.R.D., E.L. Johnson, and G.L. Nemhauser. (2001). “Branch-and-Cut for Combinatorial Optimisation Problems without Auxiliary Binary Variables.” Knowledge Engineering Review 16, 25–39.

    Article  Google Scholar 

  • Farias, I.R.D., E.L. Johnson, and G.L. Nemhauser. (2003). “A Polyhedral Study of the Cardinality Constrained Knapsack Problem.” Mathematical Programming 96, 439–467.

    Article  Google Scholar 

  • Fischetti, M. and A. Lodi. (2003). “Local Branching.” Mathematical Programming 98, 23–47.

    Article  Google Scholar 

  • Fischetti, M., F. Glover, and A. Lodi. (2005). ‘The Feasibility Pump.” Mathematical Programming 104, 91–104.

    Article  Google Scholar 

  • Forrest, J.J.H., J.P.H. Hirst, and J.A. Tomlin. (1974). “Practical Solution of Large Scale Mixed Integer Programming Problems with UMPIRE.” Management Science 20, 736–773.

    Google Scholar 

  • Gomory, R.E. (1960). “An Algorithm for the Mixed Integer Problem.” Technical Report RM-2597, The Rand Corporation.

  • Gondzio, J. (1997). “Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method.” INFORMS Journal on Computing 9, 73–91.

    Google Scholar 

  • Gu, Z., G.L. Nemhauser, and M.W.P. Savelsbergh. (1998). “Lifted Cover Inequalities for 0-1 Integer Programs: Computation.” INFORMS Journal on Computing 10, 427–437.

    Google Scholar 

  • Gu, Z., G.L. Nemhauser, and M.W.P. Savelsbergh. (1999). “Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs.” Mathematical Programming 85, 439–467.

    Article  Google Scholar 

  • Guignard, M. and K. Spielberg. (1981). “Logical Reduction Methods in Zero–One Programming.” Operations Research 29, 49–74.

    Google Scholar 

  • Hammer, P.L., E.L. Johnson, and U.N. Peled. (1975). “Facets of Regular 0-1 Polytopes.” Mathematical Programming 8, 179–206.

    Article  Google Scholar 

  • Harjunkoski, I., V. Jain, and I.E. Grossman. (2000). “Hybrid Mixed-Integer/Constraint Logic Programming Strategies for Solving Scheduling and Combinatorial Optimization Problems.” Computers and Chemical Engineering 24, 337–343.

    Article  Google Scholar 

  • Hirst, J.P.H. (1969). “Features Required in Branch and Bound Algorithms for (0-1) Mixed Integer Linear Programming.” Privately circulated manuscript.

  • Hooker, J.N., G. Ottosson, E.S. Thornsteinsson, and H.-J. Kim. (2000). “A Scheme for Unifying Optimization and Constraint Satisfaction Methods.” Knowledge Engineering Review 15, 11–30.

    Article  Google Scholar 

  • ILOG, I. (2002). ILOG OPL User's Manual.

  • ILOG, I. (2003). ILOG CPLEX 9.0 Reference Manual.

  • Jain, V. and I.E. Grossmann. (2001). “Algorithms for Hybrid MILP/CP Methods.” INFORMS Journal on Computing 13, 258–276.

    Article  Google Scholar 

  • Land, A. and S. Powell. (1979). “Computer Codes for Problems of Integer Programming.” In P.L. Hammer, E.L. Johnson, and B.H. Korte (eds.), Discrete Optimization II North Holland Publishing Co, pp. 221–269.

  • LINDO Systems, I. (2002). LINDO API User's Manual.

  • Louveaux, Q. and L.A. Wolsey. (2002). “Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs.” 27, 470–484.

  • Marchand, H. and L.A. Wolsey. (2001). “Aggregation and Mixed Integer Rounding to Solve MIPs.” Operations Research 49, 363–371.

    Article  Google Scholar 

  • Margot, F. (2003). “Exploiting Orbits in Symmetric Ilp.” Mathematical Programming 98, 3–21.

    Article  Google Scholar 

  • Martin, A., T. Achterberg, and T. Koch. (2003). MIPLIB 2003. http://miplib.zib.de/.

  • Mitra, G. (1973). “Investigation of Some Branch and Bound Strategies for the Solution of Mixed Integer Linear Programs.” Mathematical Programming 4, 155–170.

    Article  Google Scholar 

  • Mittelman, H. (2002). “Benchmarks for Optimization Software.” http://plato.asu.edu/bench.html.

  • Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. New York: John Wiley & Sons.

    Google Scholar 

  • Nemhauser, G.L. and L.A. Wolsey. (1990). “A Recursive Procedure for Generating all Cuts for 0-1 Mixed Integer Programs.” Mathematical Programming 46, 379–390.

    Article  Google Scholar 

  • Owen, J.H. and S. Mehrotra. (2002). “On the Value of Binary Expansions for General Mixed-Integer Linear Programs.” Operations Research 50(5), 810–819.

    Article  Google Scholar 

  • Padberg, M.W. (1973). “On the Facial Structure of Set Packing Polyhedra.” Mathematical Programming 5, 199–215.

    Article  Google Scholar 

  • Padberg, M.W. (1979). “Covering, Packing and Knapsack Problems.” Annals of Discrete Mathematics 4, 265–287.

    Article  Google Scholar 

  • Padberg, M.W., T.J.V. Roy, and L.A. Wolsey. (1985). “Valid Linear Inequalities for Fixed Charge Problems.” Operations Research 33, 842–861.

    Google Scholar 

  • Savelsbergh, M.W.P. (1994). “Preprocessing and Probing Techniques for Mixed Integer Programming Problems.” ORSA Journal on Computing 6, 445–454.

    Google Scholar 

  • Sherali, H.D. and J.C. Smith. (2001). “Improving Discrete Model Representations via Symmetry Considerations.” Management Science 47, 1396–1407.

    Article  Google Scholar 

  • van der Vlerk, M.H. (1996–2003). “Stochastic Integer Programming Bibliography.” http://mally.eco.rug.nl/biblio/stoprog.html.

  • Van Roy, T.J. and L.A. Wolsey. (1987). “Solving Mixed Integer Programming Problems using Automatic Reformulation.” Operations Research 35, 45–57.

    Article  Google Scholar 

  • Wolsey, L.A. (1998). Integer Programming. New York: John Wiley & Sons.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, 94720-1777, USA

    Alper Atamtürk

  2. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332-0205, USA

    Martin W. P. Savelsbergh

Authors
  1. Alper Atamtürk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin W. P. Savelsbergh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alper Atamtürk.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Atamtürk, A., Savelsbergh, M.W.P. Integer-Programming Software Systems. Ann Oper Res 140, 67–124 (2005). https://doi.org/10.1007/s10479-005-3968-2

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-3968-2

Keywords

Search

Navigation