×

Strong-branching inequalities for convex mixed integer nonlinear programs. (English) Zbl 1310.90079

Summary: Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving mixed integer nonlinear programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use “discarded” information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various forms of disjunctive inequalities, and mixing-type inequalities are all discussed. The inequalities span a spectrum from those that require almost no extra effort to compute to those that require the solution of an additional linear program. In the end, we perform an extensive computational study to measure the impact of each of our proposed techniques. Computational results reveal that existing algorithms can be significantly improved by leveraging the information generated as a byproduct of strong branching in the form of valid inequalities.

MSC:

90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abhishek, K., Leyffer, S., Linderoth, J.T.: FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs. INFORMS J. Comput. 22, 555-567 (2010) · Zbl 1243.90142
[2] Achterberg, T.: Constraint Integer Programming. Ph.D. Thesis, Technischen Universtät Berlin (2007) · Zbl 1169.90414
[3] Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42-54 (2004) · Zbl 1076.90037
[4] Applegate, D., Bixby, R., Cook, W., Chvátal, V.: The Traveling Salesman Problem, A Computational Study. Princeton University Press, Princeton (2006) · Zbl 1130.90036
[5] Atamtürk, A., Nemhauser, G., Savelsbergh, M.W.P.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121, 40-55 (2000) · Zbl 0959.90034
[6] Balas, E.: A modified lift-and-project procedure. Math. Program. 79, 19-31 (1997) · Zbl 0887.90127
[7] Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discr. Appl. Math. 89(1-3), 3-44 (1998) · Zbl 0921.90118
[8] 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) · Zbl 0796.90041
[9] Balas, E., Ceria, S., Cornuéjols, G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42, 1229-1246 (1996) · Zbl 0880.90105
[10] Balas, E., Jeroslow, R.G.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224-234 (1980) · Zbl 0439.90064
[11] Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1-131 (2013) · Zbl 1291.65172
[12] Bonami, P., Kılınç, M., Linderoth, J.: Algorithms and software for solving convex mixed integer nonlinear programs. IMA Vol. Math. Appl. 54, 1-40 (2012) · Zbl 1242.90121
[13] Bonami, P., Lee, J., Leyffer, S., Wächter, A.: More branch-and-bound experiments in convex nonlinear integer programming. Preprint ANL/MCS-P1949-0911, Argonne National Laboratory, Mathematics and Computer Science Division, September (2011)
[14] Boorstyn, R.R., Frank, H.: Large-scale network topological optimization. IEEE Trans. Commun. 25, 29-47 (1997) · Zbl 0361.94044
[15] Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib - a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114-119 (2003) · Zbl 1238.90104
[16] Castillo, I., Westerlund, J., Emet, S., Westerlund, T.: Optimization of block layout deisgn problems with unequal areas: a comparison of MILP and MINLP optimization methods. Comput. Chem. Eng. 30, 54-69 (2005)
[17] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004
[18] Duran, M.A., Grossmann, I.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36, 307-339 (1986) · Zbl 0619.90052
[19] Elhedhli, S.: Service system design with immobile servers, stochastic demand, and congestion. Manuf. Serv. Oper. Manag. 8(1), 92-97 (2006)
[20] Fischetti, M., Lodi, A., Tramontani, A.: On the separation of disjunctive cuts. Math. Programm. 128, 205-230 (2011) · Zbl 1218.90125
[21] Fletcher, R., Leyffer, S.: User manual for filterSQP. University of Dundee Numerical Analysis Report NA-181 (1998)
[22] Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3, 227-252 (2002) · Zbl 1035.90050
[23] Günlük, O., Lee, J., Weismantel, R.: MINLP strengthening for separaable convex quadratic transportation-cost ufl. Technical Report RC24213 (W0703-042), IBM Research Division, March (2007)
[24] Günlük, O., Pochet, Y.: Mixing mixed-integer inequalities. Math. Program. 90(3), 429-457 (2001) · Zbl 1041.90033
[25] Harjunkoski, I.; Pörn, R.; Westerlund, T.; Floudas, Christodoulos A. (ed.); Pardalos, Panos M. (ed.), MINLP: Trim-loss problem, 2190-2198 (2009), New York
[26] Kılınç, M.: Disjunctive Cutting Planes and Algorithms for Convex Mixed Integer Nonlinear Programming. Ph.D. Thesis, University of Wisconsin-Madison (2011)
[27] Leyffer, S.: MacMINLP: Test Problems for Mixed Integer Nonlinear Programming, (2003). http://www.mcs.anl.gov/ leyffer/macminlp · Zbl 0439.90064
[28] Linderoth, J.T., Savelsbergh, M.W.P.: A computational study of search strategies in mixed integer programming. INFORMS J. Comput. 11, 173-187 (1999) · Zbl 1040.90535
[29] 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
[30] Pochet, Y., Wolsey, L.: Lot sizing with constant batches: formulation and valid inequalities. Math. Oper. Res. 18, 767-785 (1993) · Zbl 0808.90058
[31] Quesada, I., Grossmann, I.E.: An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16, 937-947 (1992)
[32] Ravemark, D.E., Rippin, D.W.T.: Optimal design of a multi-product batch plant. Comput. Chem. Eng. 22(1-2), 177-183 (1998)
[33] Sawaya, N.: Reformulations, relaxations and cutting planes for generalized disjunctive programming. Ph.D. Thesis, Chemical Engineering Department, Carnegie Mellon University (2006)
[34] Sawaya, N., Laird, C.D., Biegler, L.T., Bonami, P., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Lee, J., Lodi, A., Margot, F., Wächter, A.: CMU-IBM open source MINLP project test set, (2006). http://egon.cheme.cmu.edu/ibm/page.htm · Zbl 0796.90041
[35] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations. Math. Program. Ser. B 124, 383-411 (2010) · Zbl 1198.90330
[36] Stubbs, R., Mehrotra, S.: A branch-and-cut method for 0-1 mixed convex programming. Math. Program. 86, 515-532 (1999) · Zbl 0946.90054
[37] Türkay, M., Grossmann, I.E.: Logic-based MINLP algorithms for the optimal synthesis of process networks. Comput. Chem. Eng. 20(8), 959-978 (1996)
[38] Vecchietti, A., Grossmann, I.E.: LOGMIP: a disjunctive 0-1 non-linear optimizer for process system models. Comput. Chem. Eng. 23(4-5), 555-565 (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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.