Abstract
The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm—a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If \(\bar{s}\in S\) the problem would be solved.
- 2.
Since we are considering rays of a simplicial cone of dimension p, they are all linearly independent. However, in practice, the set \(S\) is usually of dimension \(\ll p\). In these cases, one can either extend the \(S\)-free set to dimension p, or restrict the rays to the support of \(S\) for computational purposes. The latter might create linear dependence.
References
Andersen, K., Jensen, A.N.: Intersection cuts for mixed integer conic quadratic sets. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 37–48. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36694-9_4
Andersen, K., Louveaux, Q., Weismantel, R.: An analysis of mixed integer linear sets based on lattice point free convex sets. Math. Oper. Res. 35(1), 233–256 (2010)
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.A.: Inequalities from two rows of a simplex tableau. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 1–15. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72792-7_1
Balas, E.: Intersection cuts–a new type of cutting planes for integer programming. Oper. Res. 19(1), 19–39 (1971). https://doi.org/10.1287/opre.19.1.19
Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35(3), 704–720 (2010). https://doi.org/10.1287/moor.1100.0461
Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24(1), 158–168 (2010)
Bienstock, D., Chen, C., Muñoz, G.: Intersection cuts for polynomial optimization. In: Lodi, A., Nagarajan, V. (eds.) IPCO 2019. LNCS, vol. 11480, pp. 72–87. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17953-3_6
Bienstock, D., Chen, C., Gonzalo, M., et al.: Outer-product-free sets for polynomial optimization and oracle-based cuts. Math. Program. 183, 105–148 (2020). https://doi.org/10.1007/s10107-020-01484-3
Bonami, P., Linderoth, J., Lodi, A.: Disjunctive cuts for mixed integer nonlinear programming problems. Prog. Comb. Optim., 521–541 (2011)
Borozan, V., Cornuéjols, G.: Minimal valid inequalities for integer constraints. Math. Oper. Res. 34(3), 538–546 (2009). https://doi.org/10.1287/moor.1080.0370
Burer, S., Fatma, K.K.: How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Program. 162, 393–429 (2016). https://doi.org/10.1007/s10107-016-1045-z
Chmiela, A., Muñoz, G., Serrano, F.: On the implementation and strengthening of intersection cuts for QCQPs. Online preprint (2020). https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7999
Conforti, M., Cornuéjols, G., Daniilidis, A., Lemaréchal, C., Malick, J.: Cut-generating functions and S-free sets. Math. Oper. Res. 40(2), 276–391 (2015). https://doi.org/10.1287/moor.2014.0670
Cornuéjols, G., Wolsey, L., Yıldız, S.: Sufficiency of cut-generating functions. Math. Program. 152(1), 643–651 (2014). https://doi.org/10.1007/s10107-014-0780-2
Dey, S.S., Wolsey, L.A.: Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 463–475. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68891-4_32
Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: Intersection cuts for bilevel optimization. In: Louveaux, Q., Skutella, M. (eds.) IPCO 2016. LNCS, vol. 9682, pp. 77–88. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33461-5_7
Fischetti, M., Monaci, M.: A branch-and-cut algorithm for mixed-integer bilinear programming. Eur. J. Oper. Res. 282, 506–514 (2019). https://doi.org/10.1016/j.ejor.2019.09.043
Glover, F.: Polyhedral convexity cuts and negative edge extensions. Zeitschrift für Oper. Res. 18(5), 181–186 (1974)
Glover, F.: Convexity cuts and cut search. Oper. Res. 21(1), 123–134 (1973). https://doi.org/10.1287/opre.21.1.123
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra. Math. Program. 3(1), 23–85 (1972). https://doi.org/10.1007/bf01584976
Kılınç-Karzan, F.: On minimal valid inequalities for mixed integer conic programs. Math. Oper. Res. 41(2), 477–510 (2015)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part i – convex underestimating problems. Math. Program. 10(1), 147–175 (1976). https://doi.org/10.1007/bf01580665
MINLP library. http://www.minlplib.org/
Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10–15 (2015)
Modaresi, S., Kılınç, M.R., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155(1–2), 575–611 (2016)
Muñoz, G., Serrano, F.: Maximal quadratic-free sets. In: Bienstock, D., Zambelli, G. (eds.) IPCO 2020. LNCS, vol. 12125, pp. 307–321. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45771-6_24
Santana, A., Dey, S.S.: The convex hull of a quadratic constraint over a polytope. arXiv preprint arXiv:1812.10160 (2018)
SCIP - Solving Constraint Integer Programs. http://scip.zib.de
Sen, S., Sherali, H.D.: Facet inequalities from simple disjunctions in cutting plane theory. Math. Program. 34(1), 72–83 (1986). https://doi.org/10.1007/bf01582164
Sen, S., Sherali, H.D.: Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization. Math. Program. 37(2), 169–183 (1987)
Serrano, F.: Intersection cuts for factorable MINLP. In: Lodi, A., Nagarajan, V. (eds.) IPCO 2019. LNCS, vol. 11480, pp. 385–398. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17953-3_29
Towle, E., Luedtke, J.: Intersection disjunctions for reverse convex sets. arXiv preprint arXiv:1901.02112 (2019)
Tuy, H.: Concave programming with linear constraints. In: Doklady Akademii Nauk, vol. 159, pp. 32–35. Russian Academy of Sciences (1964)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Chmiela, A., Muñoz, G., Serrano, F. (2021). On the Implementation and Strengthening of Intersection Cuts for QCQPs. In: Singh, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2021. Lecture Notes in Computer Science(), vol 12707. Springer, Cham. https://doi.org/10.1007/978-3-030-73879-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-73879-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-73878-5
Online ISBN: 978-3-030-73879-2
eBook Packages: Computer ScienceComputer Science (R0)