×

zbMATH — the first resource for mathematics

Cutting planes in integer and mixed integer programming. (English) Zbl 1130.90370
Summary: This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for (i) general integer programs, (ii) problems with local structure such as knapsack constraints, and (iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally, the use of valid inequalities for classes of problems with structure, such as network design, is explored.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aardal, K., Capacitated facility location: separation algorithms and computational experience, Math. programming, 81, 149-175, (1998) · Zbl 0919.90096
[2] Aardal, K.; Pochet, Y.; Wolsey, L.A., Capacitated facility location: valid inequalities and facets, Math. oper. res., 20, 562-582, (1995) · Zbl 0846.90088
[3] D. Applegate, R.E. Bixby, V. Chvátal, W. Cook, Project-and-lift (a paradigm for finding cuts), Draft, Aussois, March, 1998.
[4] A. Atamturk, On network design cut-set polyhedra, Draft, Department of Industrial Engineering and Operations Research, U.C. at Berkeley, August, 1999. · Zbl 1008.90003
[5] A. Atamturk, G.L. Nemhauser, M.W.P. Savelsbergh, Conflict graphs in integer programming, Technical Report LEC 98-03, Georgia Institute of Technology, 1998. · Zbl 0959.90034
[6] A. Balakrishnan, T.L. Magnanti, J. Sokol, Y. Wang, Modeling and solving the single facility line restoration problem, Technical report, MIT, Operations Research Center, 1998. Available at http://web.mit.edu/yiwang/www.
[7] Balas, E., Facets of the knapsack polytope, Math. programming, 8, 146-164, (1975) · Zbl 0316.90046
[8] Balas, E., Disjunctive programming, Ann. discrete math., 5, 3-51, (1979) · Zbl 0409.90061
[9] Balas, E.; Ho, A., Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study, Math. programming, 12, 37-60, (1980) · Zbl 0435.90074
[10] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. programming, 58, 295-324, (1993) · Zbl 0796.90041
[11] Balas, E.; Ceria, S.; Cornuéjols, G., Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Management sci., 42, 1229-1246, (1996) · Zbl 0880.90105
[12] Balas, E.; Ceria, S.; Cornuéjols, G.; Natraj, N., Gomory cuts revisited, Oper. res. lett., 19, 1-9, (1996) · Zbl 0865.90098
[13] E. Balas, E. Zemel, Lifting and complementing yields all the facets of positive zero-one programming polytopes, Math. Programming (1984) 13-24, Proceedings of the International Congress, Rio de Janeiro, 1981. · Zbl 0548.90048
[14] Balas, E.; Zemel, E., Facets of the knapsack polytope from minimal covers, SIAM J. appl. math., 34, 119-148, (1978) · Zbl 0385.90083
[15] Barahona, F., Network design using cut inequalities, SIAM J optim., 6, 823-837, (1996) · Zbl 0856.90112
[16] Barany, I.; Van Roy, T.J.; Wolsey, L.A., Strong formulations for multi-item capacitated lot-sizing, Management sci., 30, 1255-1261, (1984) · Zbl 0601.90037
[17] J.E. Beasley, OR-Library: distributing test problems by electronic mail, J. Oper. Res. Soc. 41 (1990) 1069-1072, available at (http://mscmga.ms.ic.ac.uk/info.html).
[18] Belvaux, G.; Wolsey, L.A., BC-PROD: A specialized branch-and-cut system for lot-sizing problems, Management sci., 46, 724-738, (2000) · Zbl 1231.90384
[19] C. Berge, Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung), in Wissenschaftliche Zeitschrift, Mathematisch-Naturwissenschaftliche Reihe. Martin-Luther-Universität Halle-Wittenberg, 1961.
[20] Bienstock, D.; Günlük, O., Capacitated network design—polyhedral structure and computation, ORSA J. comput., 8, 243-259, (1996) · Zbl 0871.90031
[21] Bienstock, D.; Chopra, S.; Günlük, O.; Tsai, C.-Y., Minimum cost capacity installation for multicommodity network flows, Math. programming, 81, 177-199, (1998) · Zbl 0922.90064
[22] R.E. Bixby, S. Ceria, C.M. McZeal, M.W.P. Savelsbergh, An updated mixed integer programming library: MIPLIB 3.0, text and problems available at http://www.caam.rice.edu/ bixby/miplib/miplib.html
[23] R. Borndörfer, Aspects of set packing, partitioning, and covering, Ph.D. Thesis, Technische Universität Berlin, 1998.
[24] R. Borndörfer, R. Weismantel, Relations among some combinatorial programs, Technical Report Preprint SC 97-54, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 1997.
[25] R. Borndörfer, R. Weismantel, Set packing relaxations of some integer programs, Technical Report Preprint SC 97-30, Konrad-Zuse Zentrum für Informationstechnik Berlin, 1997.
[26] B. Brockmüller, O. Günlük, L.A. Wolsey, designing private line networks—polyhedral analysis and computation, Core Discussion Paper 9647, Université Catholique de Louvain, 1996, revised March, 1998.
[27] Caprara, A.; Fischetti, M., Branch-and-cut algorithms, (), 45-63 · Zbl 1068.90505
[28] Caprara, A.; Fischetti, M., \({0,12}\)-chvátal – gomory cuts, Math. programming, 74, 221-236, (1996) · Zbl 0855.90088
[29] Ceria, S.; Cordier, C.; Marchand, H.; Wolsey, L.A., Cutting planes for integer programs with general integer variables, Math. programming, 81, 201-214, (1998) · Zbl 0919.90113
[30] Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete math., 4, 305-337, (1973) · Zbl 0253.05131
[31] Chvátal, V., On certain polytopes associated with graphs, J. combin. theory B, 18, 305-337, (1975) · Zbl 0253.05131
[32] Constantino, M., A cutting plane approach to capacitated lot-sizing with start-up costs, Math. programming, 75, 353-376, (1996) · Zbl 0874.90098
[33] Cook, W.; Kannan, R.; Schrijver, A., Chvátal closures for mixed integer programming problems, Math. programming, 47, 155-174, (1990) · Zbl 0711.90057
[34] Cordier, C.; Marchand, H.; Laundy, R.; Wolsey, L.A., Bc-opt: A branch-and-cut code for mixed integer programs, bc-opt: a branch-and-cut code for mixed integer programs, Math. programming, 86, 335-354, (1999) · Zbl 0939.90025
[35] CPLEX, Using the CPLEX callable library, ILOG CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, USA, Information available at URL http://www.cplex.com (1998).
[36] Crowder, H.; Johnson, E.; Padberg, M.W., Solving large-scale zero-one linear programming problems, Oper. res., 31, 803-834, (1983) · Zbl 0576.90065
[37] Dahl, G.; Martin, A.; Stoer, M., Routing through virtual paths in layered telecommunication networks, research note N78/95, telenor research and development, kjeller, Norway, 1995, Oper. res., 49, 693-702, (1999)
[38] Dahl, G.; Stoer, M., A cutting plane algorithm for multicommodity survivable network design problems, INFORMS J. comput., 10, 1-11, (1998)
[39] I.R. de Farias, E.L. Johnson, G.L. Nemhauser, Facets of the complementarity knapsack polytope, Technical Report LEC-98-08, Georgia Institute of Technology, 1998. · Zbl 1082.90586
[40] Edmonds, J., Matroids and the greedy algorithm, Math. programming, 1, 127-136, (1971) · Zbl 0253.90027
[41] Edmonds, J., Matroid intersection, Ann. discrete math., 4, 39-49, (1979) · Zbl 0416.05025
[42] M. Jünger, R.Euler; Reinelt, G., Generalizations of odd cycles and anti-cycles and their relation to independence system polyhedra, Math. oper. res., 12, 451-462, (1987) · Zbl 0624.05024
[43] Ferreira, C.E.; Martin, A.; Weismantel, R., Solving multiple knapsack problems by cutting planes, SIAM J. optim., 6, 858-877, (1996) · Zbl 0856.90082
[44] Fulkerson, D.R., Blocking and anti-blocking pairs of polyhedra, Math. programming, 1, 168-194, (1971) · Zbl 0254.90054
[45] Goemans, M.X., The Steiner tree polytope and related polyhedra, Math. programming, 63, 157-183, (1994) · Zbl 0808.90124
[46] Gomory, R.E., Outline of an algorithm for integer solutions to linear programs, Bull. amer. soc., 64, 275-278, (1958) · Zbl 0085.35807
[47] R.E. Gomory, An algorithm for the mixed integer problem, Technical Report RM-2597, The RAND Cooperation, 1960.
[48] R.E. Gomory, Solving linear programming problems in integers, in: R. Bellman, M. Hall (Eds.), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, Providence, RI, 1960. · Zbl 0096.14505
[49] Gomory, R.E., An algorithm for integer solutions to linear programming, (), 269-302
[50] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer Berlin · Zbl 0634.05001
[51] M. Grötschel, C.L. Monma, M. Stoer, Design of survivable networks, in: M.O. Ball et al. (Eds.), Network Models, Handbooks in OR and MS 7, Elsevier, Amsterdam, 1995 (chapter 10). · Zbl 0839.90132
[52] Gu, Z.; Nemhauser, G.L.; Savelsbergh, M.W.P., Sequence independent lifting in mixed integer programming, J. combin. optim., 4, 109-129, (2000) · Zbl 0964.90030
[53] Gu, Z.; Nemhauser, G.L.; Savelsbergh, M.W.P., Lifted flow cover inequalities for mixed 0-1 integer programs, Math. programming A, 85, 436-467, (1999) · Zbl 0977.90030
[54] Gu, Z.; Nemhauser, G.L.; Savelsbergh, M.W.P., Lifted cover inequalities for 0-1 integer programs: computation, INFORMS J. comput., 10, 427-437, (1998)
[55] O. Günlük, A branch-and-cut algorithm for capacitated network design, Technical report, Cornell University, 1966.
[56] O. Günlük, Y. Pochet, Mixing mixed-integer inequalities, Math. Programming (2001) 429-458. · Zbl 1041.90033
[57] Hammer, P.L.; Johnson, E.L.; Peled, U.N., Facets of regular 0-1 polytopes, Math. programming, 8, 179-206, (1975) · Zbl 0314.90064
[58] Hoffman, K.L.; Padberg, M.W., Solving airline crew-scheduling problems by branch-and-cut, Management sci., 39, 657-682, (1993) · Zbl 0783.90051
[59] Iri, M., On an extension of the maximum-flow minimum-cut theorem to multi-commodity flows, J. oper. res. soc. Japan, 13, 129-135, (1970/71)
[60] Jeroslow, R.G., Cutting plane theory: disjunctive methods, Ann. discrete math., 1, 293-330, (1977) · Zbl 0358.90035
[61] Johnson, E.L.; Padberg, M.W., Degree-two inequalities, clique facets, and biperfect graphs, Ann. discrete math., 16, 169-187, (1982) · Zbl 0523.52009
[62] Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M.W.P., Progress in linear programming based branch-and-bound algorithms: an exposition, INFORMS J. comput., 12, 2-23, (2000) · Zbl 1052.90048
[63] Jünger, M.; Reinelt, G.; Thienel, S., Practical problem solving with cutting plane algorithms in combinatorial optimization, (), 11-152 · Zbl 0835.90076
[64] Laurent, M., A generalization of antiwebs to independence systems and their canonical facets, Math. programming, 45, 97-108, (1989) · Zbl 0675.90055
[65] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1-7, (1979) · Zbl 0395.94021
[66] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. optim., 1, 166-190, (1991) · Zbl 0754.90039
[67] Magnanti, T.L.; Mirchandani, P.; Vachani, R., Modelling and solving the two-facility network loading problem, Oper. res., 43, 142-157, (1995) · Zbl 0830.90051
[68] H. Marchand, Etude d’un problème d’optimisation lié à la gestion d’un parc électrique, Engineering Thesis, Faculté des Sciences Appliquées, 1994.
[69] H. Marchand, A polyhedral study of the mixed knapsack set and its use to solve mixed integer programs, Ph.D. Thesis, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1998.
[70] H. Marchand, L.A. Wolsey, Aggregation and mixed integer rounding to solve MIPs, CORE DP9839, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1998, Oper. Res., to appear. · Zbl 1163.90671
[71] Marchand, H.; Wolsey, L.A., The 0-1 knapsack problem with a single continuous variable, Math. programming, 85, 15-33, (1999) · Zbl 0956.90021
[72] A. Martin, Integer programs with block structure, Habilitations-Schrift Technische Universität Berlin, 1998. Available at (ftp://ftp.zib.de/pub/zib-publications/reports/SC-99-03.ps).
[73] Martin, A.; Weismantel, R., The intersection of knapsack polyhedra and extensions, (), 243-256 · Zbl 0910.90223
[74] MEMIPS, Model enhanced solution methods for integer programming software, Esprit Project 20118, Public Report Reference DR1.1.10, 1997.
[75] Nemhauser, G.L.; Savelsbergh, M.W.P.; Sigismondi, G.C., MINTO, a mixed integer optimizer, Oper. res. lett., 15, 47-58, (1994) · Zbl 0806.90095
[76] Nemhauser, G.L.; Sigismondi, G., A strong cutting plane/branch-and-bound algorithm for node packing, J. oper. res. soc., 43, 443-457, (1992) · Zbl 0756.90067
[77] Nemhauser, G.L.; Trotter, L.E., J., properties of vertex packing and independence system polyhedra, Math. programming, 6, 48-61, (1974) · Zbl 0281.90072
[78] Nemhauser, G.L.; Wolsey, L.A., Integer and combinatorial optimization, (1988), Wiley New York · Zbl 0469.90052
[79] Nemhauser, G.L.; Wolsey, L.A., A recursive procedure to generate all cuts for 0-1 mixed integer programs, Math. programming, 46, 379-390, (1990) · Zbl 0735.90049
[80] Nobili, P.; Sassano, A., Facets and lifting procedures for the set covering polytope, Math. programming, 45, 111-137, (1989) · Zbl 0677.90055
[81] P. Nobili, A. Sassano, A separation routine for the set covering polytope, in: E. Balas, G. Cornuéjols, R. Kannan (Eds.), Integer Programming and Combinatorial Optimization, Proceedings of the 2nd IPCO Conference, 1992, pp. 201-219.
[82] Onaga, K.; Kakusho, O., On feasibility conditions of multicommodity flows in networks, IEEE trans. circuit theory, 18, 425-429, (1971)
[83] Owen, J.H.; Mehrotra, S., Math. programming, 89, 437-448, (2001)
[84] Padberg, M.W., On the facial structure of set packing polyhedra, Math. programming, 5, 199-215, (1973) · Zbl 0272.90041
[85] Padberg, M.W., A note on zero-one programming, Oper. res., 23, 833-837, (1975) · Zbl 0311.90053
[86] Padberg, M.W.; Van Roy, T.J.; Wolsey, L.A., Valid linear inequalities for fixed charge problems, Oper. res., 33, 842-861, (1985) · Zbl 0579.90072
[87] Pochet, Y., Valid inequalities and separation for capacitated economic lot-sizing, Oper. res. lett., 7, 109-116, (1988) · Zbl 0653.90051
[88] Pochet, Y.; Wolsey, L.A., Solving multi-item lot-sizing problems using strong cutting planes, Management sci., 37, 53-67, (1991) · Zbl 0727.90034
[89] Pochet, Y.; Wolsey, L.A., Lot-sizing with constant batches: formulation and valid inequalities, Math. oper. res., 18, 767-785, (1993) · Zbl 0808.90058
[90] Pochet, Y.; Wolsey, L.A., Integer knapsacks and flow covers with divisible coefficients: polyhedra, optimization and separation, Discrete appl. math., 59, 57-74, (1995) · Zbl 0835.90052
[91] Rardin, R.; Wolsey, L.A., Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems, European J. oper. res., 71, 95-109, (1993) · Zbl 0807.90051
[92] Renaud, A., Daily generation management at electricité de France: from planning towards real time, IEEE trans. automat. control, 38, 1080-1093, (1993)
[93] Sassano, A., On the facial structure of the set covering polytope, Math. programming, 44, 181-202, (1989) · Zbl 0675.90059
[94] Schrijver, A., On cutting planes, Ann. discrete math., 9, 291-296, (1980) · Zbl 0441.90070
[95] Schrijver, A., Theory of linear and integer programming, (1986), Wiley Chichester · Zbl 0665.90063
[96] Sherali, H.; Adams, W., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. discrete math., 3, 411-430, (1990) · Zbl 0712.90050
[97] S. Thienel, ABACUS—a branch-and-cut system, Doctoral Thesis, Universität zu Köln, 1995.
[98] R. van de Leensel, Models and algorithms for telecommunications network design, Proefschrift, Universiteit Maastricht, 1999.
[99] van de Leensel, R.; van Hoesel, C.P.M.; van de Klundert, J.J., Lifting valid inequalities for the precedence constrained knapsack problem, Math. programming A, 86, 161-185, (1999) · Zbl 1015.90072
[100] Van Roy, T.J.; Wolsey, L.A., Valid inequalities for mixed 0-1 programs, Discrete appl. math., 4, 199-213, (1986) · Zbl 0593.90058
[101] Van Roy, T.J.; Wolsey, L.A., Solving mixed 0-1 problems by automatic reformulation, Oper. res., 35, 45-57, (1987) · Zbl 0614.90082
[102] Weismantel, R., On the 0/1 knapsack polytope, Math. programming, 77, 49-68, (1997) · Zbl 0891.90130
[103] Wolsey, L.A., Faces for a linear inequality in 0-1 variables, Math. programming, 8, 165-178, (1975) · Zbl 0314.90063
[104] Wolsey, L.A., Valid inequalities and superadditivity for 0/1 integer programs, Math. oper. res., 2, 66-77, (1977) · Zbl 0402.90066
[105] Wolsey, L.A., Submodularity and valid inequalities in capacitated fixed charge networks, Oper. res. lett., 8, 119-124, (1989) · Zbl 0674.90027
[106] Wolsey, L.A., Valid inequalities for 0-1 knapsacks and MIPS with generalized upper bound constraints, Discrete appl. math., 29, 251-261, (1990) · Zbl 0718.90067
[107] Wolsey, L.A., Integer programming, (1998), Wiley New York · Zbl 0299.90012
[108] Eisenbrand, F., On the membership problem for the elementary closure of a ployhedron, Combinatorica, 12, 27-37, (1999)
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.