Abstract
This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming where branching is performed on general disjunctions rather than on variables. We select promising branching disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining the mixed integer Gomory cuts at an optimal basis of the linear programming relaxation. The procedure is tested on instances from the literature. Experiments show that, for a majority of the instances, the enumeration tree obtained by branching on these general disjunctions has a smaller size than the tree obtained by branching on variables, even when variable branching is performed using full strong branching.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal K., Bixby R.E., Hurkens C.A.J., Lenstra A.K., Smeltink J.W.: Market split and basis reduction: towards a solution of the Cornuéjols-Dawande instances. Inf. J. Comput. 12(3), 192–202 (2000)
Aardal K., Hurkens C.A.J., Lenstra A.K.: Solving a system of linear diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25(3), 427–442 (2000)
Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2005)
Achterberg, T.,Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372Available from http://www.miplib.zib.de (2006)
Andersen K., Cornuéjols G., Li Y.: Reduce-and-split cuts: improving the performance of mixed integer Gomory cuts. Manag. Sci. 51, 1720–1732 (2006)
Balas E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)
Balas E., Ceria S., Cornuéjols G.: Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42(9), 1229–1246 (1996)
Beale E.M.L., Tomlin J.A.: Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence, J. (eds) OR 69: Proc. Fifth Int. Conf. Oper. Res., pp. 447–454. Tavistock Publications, London (1970)
Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima. 58, 12–15 (1998)
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: a progress report. In: Grötschel, M. (ed.) The Sharpest Cut: The Impact of Manfred Padberg and his Work, pp. 309–326. MPS/SIAM Series in Optimization, SIAM (2004)
Cook W., Kannan R., Schrijver A.: Chvátal closures for mixed integer programs. Math. Program. 47, 155–174 (1990)
Cornuéjols G., Dawande M.: A class of hard small 0–1 programs. In: Bixby, R.E., Boyd, E.A., Rios-Mercado, R.Z. (eds) Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, Lecture notes in Computer Science 1412, pp. 284–293. Springer-Verlag, Berlin (1998)
Cornuéjols, G., Liberti, L., Nannicini, G.: Improved strategies for branching on general disjunctions. Technical report, Working paper, July 2008, revised April (2009)
Fischetti M., Lodi A.: Local branching. Math. Program. 98, 23–47 (2003)
Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, Rand Corporation (1960)
Grötschel M., Lovász L., Schrijver A.: Progress in combinatorial optimizarion chapter Geometric methods in combinatorial optimization, pp. 167–183. Academic Press, Toronto (1984)
Lenstra H.W. Jr: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving hard mixed integer programming problems with Xpress-MP: a MIPLIB 2003 case study. Technical report (2009)
Lenstra A.K., Lenstra H.W. Jr., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)
Linderoth J.T., Savelsbergh M.W.P.: A computational study of search strategies for mixed integer programming. Inf. J. Comput. 11, 172–187 (1999)
Lovász L., Scarf H.E.: The generalized basis reduction algorithm. Math. Oper. Res. 17, 751–764 (1992)
Mahajan, A., Ralphs, T.K.: Experiments with branching using general disjunctions. In: Chinneck, J.W. et al. (eds.) Operations Research and Cyber-Infrastructure, Operations Research/Computer Science Interfaces Series 47, pp. 101–118. Springer, Berlin (2009)
Marchand H., Wolsey L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)
Mehrotra, S., Li, Z.: On generalized branching methods for mixed integer programming. Technical report, Northwestern University, Evanston, Illinois 60208 (2004)
Mittelman, H.: Benchmarks for optimization software. http://www.plato.la.asu.edu/bench.html (2006)
Owen J., Mehrotra S.: Experimental results on using general disjunctions in branch-and-bound for general-integer linear program. Comput. Optim. Appl. 20, 159–170 (2001)
MIPLIB website of Zuse Institute Berlin. URL: http://www.miplib.zib.de/miplib3/miplib_prev.html
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by NSF grant CMMI-0653419, ANR grant 06-BLAN-0375, and ONR grant N00014-09-1-0133.
Rights and permissions
About this article
Cite this article
Karamanov, M., Cornuéjols, G. Branching on general disjunctions. Math. Program. 128, 403–436 (2011). https://doi.org/10.1007/s10107-009-0332-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0332-3