×

zbMATH — the first resource for mathematics

A branch-and-cut algorithm for mixed-integer bilinear programming. (English) Zbl 1430.90431
Summary: In this paper, we consider the mixed-integer bilinear programming problem, a widely-used reformulation of the classical mixed-integer quadratic programming problem. For this problem we describe a branch-and-cut algorithm for its exact solution, based on a new family of intersection cuts derived from bilinear-specific disjunctions. We also introduce a new branching rule that is specifically designed for bilinear problems. We computationally analyze the behavior of the proposed algorithm on a large set of mixed-integer quadratic instances from the MINLPlib problem library. Our results show that our method, even without intersection cuts, is competitive with a state-of-the-art mixed-integer nonlinear solver. As to intersection cuts, their extensive use at each branching node tends to slow down the solver for most problems in our test bed, but they are extremely effective for some specific instances.

MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, W. P.; Sherali, H. D., Mixed-integer bilinear programming problems, Mathematical Programming, 59, 279-305 (1993) · Zbl 0801.90085
[2] Al-Khayyal, F. A.; Sherali, H. D., On finitely terminating branch-and-bound algorithms for some global optimization problems, SIAM Journal on Optimization, 10, 1049-1057 (2000) · Zbl 0994.65068
[3] Andersen, E. D.; Andersen, K. D., The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, (Frenk, H., High performance optimization (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands), 197-232 · Zbl 1028.90022
[4] Audet, C.; Brimberg, J.; Hansen, P.; Digabel, S. L.; Mladenović, N., Pooling problem: alternate formulations and solution methods, Management Science, 50, 6, 761-776 (2004) · Zbl 1232.90349
[5] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Mathematical Programming, 87, 1, 131-152 (2000) · Zbl 0966.90057
[6] Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Operations Research, 19, 1, 19-39 (1971) · Zbl 0219.90035
[7] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24, 4-5, 597-634 (2009) · Zbl 1179.90237
[8] Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, (Balas, E.; Clausen, J., Integer programming and combinatorial optimization (1995), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 80-94
[9] Bienstock, D., Chen, C., & Muñoz, G. (2016). Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts. arXiv:1610.04604.
[10] Bloemhof-Ruwaard, J. M.; Hendrix, E. M.T., Generalized bilinear programming: an application in farm management, European Journal of Operational Research, 90, 1, 102-114 (1996) · Zbl 0914.90184
[11] Bonami, P.; Lee, J., BONMIN User’s manual, Technical Report (2007), IBM Corporation
[12] Byrd, R. H.; Nocedal, J.; Waltz, R. A., Knitro: An integrated package for nonlinear optimization, (Di Pillo, G.; Roma, M., Large-scale nonlinear optimization (2006), Springer US: Springer US Boston, MA), 35-59) · Zbl 1108.90004
[13] Caprara, A.; Locatelli, M.; Monaci, M., Bidimensional packing by bilinear programming, Proceedings of IPCO 2005. Proceedings of IPCO 2005, Lecture notes in computer science, 3509, 377-391 (2005) · Zbl 1119.90357
[14] Conforti, M.; Cornuéjols, G.; Zambelli, G., Corner polyhedron and intersection cuts, Surveys in Operations Research and Management Science, 16, 2, 105-120 (2011)
[15] D’Ambrosio, C.; Linderoth, J.; Luedtke, J., Valid inequalities for the pooling problem with binary variables, Proceedings of IPCO 2011. Proceedings of IPCO 2011, Lecture Notes in computer science, 6655, 117-129 (2011) · Zbl 1339.90238
[16] Dey, S. S.; Gupte, A., Analysis of MILP techniques for the pooling problem, Operations Research, 63, 2, 412-427 (2015) · Zbl 1327.90351
[17] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004
[18] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research, 65, 6, 1615-1637 (2017) · Zbl 1386.90085
[19] Fischetti, M.; Monaci, M., Branching on nonchimerical fractionalities, Operations Research Letters, 40, 159-164 (2012) · Zbl 1245.90068
[20] Fischetti, M.; Monaci, M., Exploiting erraticism in search, Operations Research, 62, 1, 114-122 (2014) · Zbl 1291.90148
[21] Foulds, L. R.; Haugland, D.; Jörnsten, K., A bilinear approach to the pooling problem, Optimization, 24, 1-2, 165-180 (1992) · Zbl 0817.90073
[22] Glover, F., Polyhedral convexity cuts and negative edge extensions, Zeitschrift für Operations Research, 18, 5, 181-186 (1974) · Zbl 0288.90056
[23] Glover, F.; Klingman, D., Improved convexity cuts for lattice point problems, Journal of Optimization Theory and Applications, 19, 2, 283-291 (1976) · Zbl 0307.90053
[24] Gupte, A.; Ahmed, S.; Cheon, M. S.; Dey, S. S., Solving mixed integer bilinear problems using MILP formulations, SIAM Journal on Optimization, 23, 2, 721-744 (2013) · Zbl 1300.90021
[25] Gupte, A.; Ahmed, S.; Dey, S. S.; Cheon, M. S., Relaxations and discretizations for the pooling problem, Journal of Global Optimization, 67, 3, 631-669 (2017) · Zbl 1392.90117
[26] Karuppiah, R.; Grossmann, I. E., Global optimization for the synthesis of integrated water systems in chemical processes, Computers and Chemical Engineering, 30, 650-673 (2006)
[27] Karzan, F. K.; Nemhauser, G. L.; Savelsbergh, M. W.P., Information-based branching schemes for binary linear mixed integer problems, Mathematical Programming Computation, 1, 249-293 (2009) · Zbl 1184.90114
[28] Lodi, A.; Tramontani, A., Performance variability in mixed-integer programming, INFORMS TutORials in Operations Research, 1-12 (2014)
[29] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I - convex underestimating problems, Mathematical Programming, 10, 1, 146-175 (1976) · Zbl 0349.90100
[30] Mc-Cormick, G. P., Nonlinear programming: Theory, algorithms and applications (1983), John Wiley & Sons
[31] Misener, R.; Floudas, C. A., Advances for the pooling problem: modeling, global optimization, and computational studies, Applied and Computational Mathematics, 8, 1, 3-22 (2009) · Zbl 1188.90287
[32] Misener, R.; Floudas, C. A., Antigone: algorithms for continuous/integer global optimization of nonlinear equations, The Journal of Global Optimization, 59, 2-3, 503-526 (2014) · Zbl 1301.90063
[33] Nahapetyan, A. G., Bilinear programming: Applications in the supply chain management, Encyclopedia of optimization, 282-288) (2009), Springer US: Springer US Boston, MA
[34] Sahinidis, N. V., BARON: A general purpose global optimization software package, Journal of Global Optimization, 8, 2, 201-205 (1996) · Zbl 0856.90104
[35] Sherali, H. D.; Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, Journal of Global Optimization, 2, 4, 379-410 (1992) · Zbl 0791.90056
[36] Tawarmalani, M.; Richard, J.-P.; Chung, K., Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Mathematical Programming, 124, 1, 481-512 (2010) · Zbl 1198.90298
[37] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optimization Methods and Software, 33, 3, 563-593 (2018) · Zbl 1398.90112
[38] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57 (2006) · Zbl 1134.90542
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.