×

zbMATH — the first resource for mathematics

Integer-programming software systems. (English) Zbl 1091.90046
Summary: 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.

MSC:
90C10 Integer programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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. · Zbl 1073.90528
[2] 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. · Zbl 1049.90042
[3] Anderson, E.D. and K.D. Anderson. (1995). ”Presolving in Linear Programming.” Mathematical Programming 71, 221–225.
[4] Atamtürk, A. (2003a). ”On the Facets of Mixed-Integer Knapsack Polyhedron.” Mathematical Programming 98, 145–175. · Zbl 1082.90073
[5] Atamtürk, A. (2003b). ”Strong Formulations of Robust Mixed 0-1 Programming.” Research Report BCOL.03.04. Available at http://ieor.berkeley.edu/\(\sim\)atamturk (To appear in Mathematical Programming). · Zbl 1082.90073
[6] 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/\(\sim\)atamturk. · Zbl 1167.90409
[7] Balas, E. (1975). ”Facets of the Knapsack Polytope.” Mathematical Programming 8, 146–164. · Zbl 0316.90046
[8] Balas, E., S. Ceria, G. Cornuéjols, and N. Natraj. (1996). ”Gomory Cuts Revisited.” Operations Research Letters 19, 1–9. · Zbl 0865.90098
[9] Balas, E. and E. Zemel. (1978). ”Facets of the Knapsack Polytope from Minimal Covers.” SIAM Journal of Applied Mathematics 34, 119–148. · Zbl 0385.90083
[10] 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. · Zbl 0551.90068
[11] 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. · Zbl 0405.90049
[12] 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. · Zbl 0233.90016
[13] Bertsimas, D. and M. Sim. (2003). ”Robust Discrete Optimization and Network Flows.” Mathematical Programming 98, 49–71. · Zbl 1082.90067
[14] Bienstock, D. (1996). ”Computational Study of a Family of Mixed-Integer Quadratic Programming Problems.” Mathematical Programming 74, 121–140. · Zbl 0855.90090
[15] Birge, J.R. and F. Louveaux. (1997). Introduction to Stochastic Programming. New York: Springer Verlag. · Zbl 0892.90142
[16] Bixby, R.E., M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. (2002). Mixed–integer programming: A progress report. · Zbl 1152.90542
[17] 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. · Zbl 1092.90529
[18] 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. · Zbl 0910.90220
[19] Crowder, H., E.L. Johnson, and M.W. Padberg. (1983). ”Solving Large–Scale Zero-One Linear Programming Problems.” Operations Research 31, 803–834. · Zbl 0576.90065
[20] Danna, E., E. Rothberg, and C.L. Pape. (2003). ”Exploring Relaxation Induced Neighborhoods to Improve MIP Solutions.” Technical report, ILOG, Inc. · Zbl 1131.90036
[21] Dash Optimization, L. (2004a). Proctor and Gamble Case Study.
[22] Dash Optimization, L. (2004b). XPRESS-BCL Reference Manual–Release 2.6.
[23] Dash Optimization, L. (2004c). XPRESS-Mosel Language Reference Manual–Release 1.4.
[24] Dash Optimization, L. (2004d). XPRESS-Optimizer Reference Manual–Release 15.
[25] 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. · Zbl 1060.90082
[26] 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. · Zbl 1023.90085
[27] Fischetti, M. and A. Lodi. (2003). ”Local Branching.” Mathematical Programming 98, 23–47. · Zbl 1060.90056
[28] Fischetti, M., F. Glover, and A. Lodi. (2005). ’The Feasibility Pump.” Mathematical Programming 104, 91–104. · Zbl 1077.90039
[29] 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. · Zbl 0304.90079
[30] Gomory, R.E. (1960). ”An Algorithm for the Mixed Integer Problem.” Technical Report RM-2597, The Rand Corporation. · Zbl 0095.14502
[31] Gondzio, J. (1997). ”Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method.” INFORMS Journal on Computing 9, 73–91. · Zbl 0890.90143
[32] 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.
[33] 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. · Zbl 0977.90030
[34] Guignard, M. and K. Spielberg. (1981). ”Logical Reduction Methods in Zero–One Programming.” Operations Research 29, 49–74. · Zbl 0452.90044
[35] Hammer, P.L., E.L. Johnson, and U.N. Peled. (1975). ”Facets of Regular 0-1 Polytopes.” Mathematical Programming 8, 179–206. · Zbl 0314.90064
[36] 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.
[37] Hirst, J.P.H. (1969). ”Features Required in Branch and Bound Algorithms for (0-1) Mixed Integer Linear Programming.” Privately circulated manuscript.
[38] 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. · Zbl 02020685
[39] ILOG, I. (2002). ILOG OPL User’s Manual.
[40] ILOG, I. (2003). ILOG CPLEX 9.0 Reference Manual.
[41] Jain, V. and I.E. Grossmann. (2001). ”Algorithms for Hybrid MILP/CP Methods.” INFORMS Journal on Computing 13, 258–276. · Zbl 1238.90106
[42] 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. · Zbl 0428.90048
[43] LINDO Systems, I. (2002). LINDO API User’s Manual.
[44] Louveaux, Q. and L.A. Wolsey. (2002). ”Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs.” 27, 470–484. · Zbl 1082.90551
[45] Marchand, H. and L.A. Wolsey. (2001). ”Aggregation and Mixed Integer Rounding to Solve MIPs.” Operations Research 49, 363–371. · Zbl 1163.90671
[46] Margot, F. (2003). ”Exploiting Orbits in Symmetric Ilp.” Mathematical Programming 98, 3–21. · Zbl 1082.90070
[47] Martin, A., T. Achterberg, and T. Koch. (2003). MIPLIB 2003. http://miplib.zib.de/.
[48] Mitra, G. (1973). ”Investigation of Some Branch and Bound Strategies for the Solution of Mixed Integer Linear Programs.” Mathematical Programming 4, 155–170. · Zbl 0258.90034
[49] Mittelman, H. (2002). ”Benchmarks for Optimization Software.” http://plato.asu.edu/bench.html.
[50] Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. New York: John Wiley & Sons. · Zbl 0652.90067
[51] 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. · Zbl 0735.90049
[52] 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. · Zbl 1163.90673
[53] Padberg, M.W. (1973). ”On the Facial Structure of Set Packing Polyhedra.” Mathematical Programming 5, 199–215. · Zbl 0272.90041
[54] Padberg, M.W. (1979). ”Covering, Packing and Knapsack Problems.” Annals of Discrete Mathematics 4, 265–287. · Zbl 0407.90056
[55] Padberg, M.W., T.J.V. Roy, and L.A. Wolsey. (1985). ”Valid Linear Inequalities for Fixed Charge Problems.” Operations Research 33, 842–861. · Zbl 0579.90072
[56] Savelsbergh, M.W.P. (1994). ”Preprocessing and Probing Techniques for Mixed Integer Programming Problems.” ORSA Journal on Computing 6, 445–454. · Zbl 0814.90093
[57] Sherali, H.D. and J.C. Smith. (2001). ”Improving Discrete Model Representations via Symmetry Considerations.” Management Science 47, 1396–1407. · Zbl 1232.90309
[58] van der Vlerk, M.H. (1996–2003). ”Stochastic Integer Programming Bibliography.” http://mally.eco.rug.nl/biblio/stoprog.html. · Zbl 0909.90222
[59] Van Roy, T.J. and L.A. Wolsey. (1987). ”Solving Mixed Integer Programming Problems using Automatic Reformulation.” Operations Research 35, 45–57. · Zbl 0614.90082
[60] Wolsey, L.A. (1998). Integer Programming. New York: John Wiley & Sons. · Zbl 0930.90072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.