×

Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. (English) Zbl 1325.90071

Summary: The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to {\(\epsilon\)}-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation-linearization technique equations, convex multivariable terms, {\(\alpha\)}BB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Y. Crama’s [Math. Program. 61, No. 1 (A), 53–60 (1993; Zbl 0796.90040)] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.

MSC:

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
65K05 Numerical mathematical programming methods

Citations:

Zbl 0796.90040
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1007/978-3-540-68155-7_4 · Zbl 1142.68504
[2] DOI: 10.1007/s12532-008-0001-1 · Zbl 1171.90476
[3] DOI: 10.1287/opre.38.2.217 · Zbl 0724.90046
[4] Adams W.P., Quadratic Assignment and Related Problems: DIMACS Workshop pp 43– (1994)
[5] DOI: 10.1016/S0098-1354(98)00218-X
[6] DOI: 10.1016/S0098-1354(98)00027-1
[7] DOI: 10.1002/aic.12276
[8] DOI: 10.1007/BF01099647 · Zbl 0846.90087
[9] Anstreicher K.M., Math. Program 97 pp 27– (2003)
[10] DOI: 10.1007/s10898-008-9372-0 · Zbl 1169.90425
[11] DOI: 10.1007/s10107-012-0602-3 · Zbl 1267.90103
[12] Audet C., Math. Program 87 pp 131– (2000) · Zbl 0966.90057
[13] DOI: 10.1006/jcta.2001.3225
[14] DOI: 10.1287/mnsc.1030.0207 · Zbl 1232.90349
[15] DOI: 10.1016/j.jcta.2006.04.002 · Zbl 1259.90096
[16] DOI: 10.1016/j.compchemeng.2011.01.041
[17] DOI: 10.1080/10556780902883184 · Zbl 1179.90252
[18] DOI: 10.1080/10556780903087124 · Zbl 1179.90237
[19] DOI: 10.1007/978-1-4614-1927-3_15 · Zbl 1242.90120
[20] DOI: 10.3934/naco.2012.2.739 · Zbl 1269.90066
[21] DOI: 10.1023/A:1013886408463 · Zbl 1045.90042
[22] DOI: 10.1016/j.disopt.2006.10.011 · Zbl 1151.90028
[23] DOI: 10.1007/s10107-006-0080-6 · Zbl 1135.90034
[24] DOI: 10.1007/978-1-4614-1927-3_13 · Zbl 1242.90122
[25] DOI: 10.1287/ijoc.15.1.114.15159 · Zbl 1238.90104
[26] Bussieck M.R., Wiley Encyclopedia of Operations Research and Management Science pp 114– (2010)
[27] DOI: 10.1016/0167-6377(90)90057-C · Zbl 0711.90080
[28] DOI: 10.1016/j.resconrec.2006.06.013
[29] DOI: 10.1007/s10098-008-0172-5
[30] DOI: 10.1016/j.compchemeng.2013.01.013
[31] DOI: 10.1007/s12532-011-0033-9 · Zbl 1257.90065
[32] DOI: 10.1006/jctb.2000.2011 · Zbl 1026.05017
[33] DOI: 10.1007/BF01587085 · Zbl 0674.90069
[34] DOI: 10.1007/BF01582138 · Zbl 0796.90040
[35] De Loera J., Algorithms and Computation in Mathematics (2010)
[36] DOI: 10.1007/s101070100263 · Zbl 1049.90004
[37] DOI: 10.1021/ie100064q
[38] Floudas C.A., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications (1995) · Zbl 0886.90106
[39] DOI: 10.1007/978-1-4757-3040-1
[40] DOI: 10.1007/978-1-4757-4949-6
[41] DOI: 10.1016/j.compchemeng.2005.02.006
[42] DOI: 10.1007/s10898-008-9332-8 · Zbl 1180.90245
[43] DOI: 10.1007/978-1-4614-1927-3_18 · Zbl 1242.90111
[44] Gau C.Y., Frontiers in Global Optimization pp 145– (2003)
[45] Gerschgorin S., Izv. Akad. Nauk SSSR, Ser, Fiz. mat 6 pp 749– (1931)
[46] DOI: 10.1007/978-3-642-38171-3_26 · Zbl 1382.90063
[47] DOI: 10.1007/BF01096415 · Zbl 0791.90063
[48] DOI: 10.1007/978-3-662-03199-5
[49] J√ľnger M., Math. Program 91 pp 175– (2001)
[50] DOI: 10.1007/s10898-013-0129-z · Zbl 1298.90087
[51] DOI: 10.1007/s10898-007-9274-6 · Zbl 1169.90434
[52] DOI: 10.1016/j.compchemeng.2005.11.005
[53] DOI: 10.1021/ie0340995
[54] DOI: 10.1007/s10898-012-0022-1 · Zbl 1282.90137
[55] DOI: 10.1016/j.compchemeng.2013.01.016
[56] DOI: 10.1021/ie950519h
[57] DOI: 10.1002/aic.11280
[58] DOI: 10.1002/aic.12419
[59] DOI: 10.1002/aic.12623
[60] DOI: 10.1007/s10898-011-9792-0 · Zbl 1282.90141
[61] DOI: 10.1007/s10898-006-9005-4 · Zbl 1131.90045
[62] DOI: 10.1080/10556780902753221 · Zbl 1177.90325
[63] DOI: 10.1007/BF01096418 · Zbl 0785.90089
[64] DOI: 10.1016/j.ejor.2005.09.032 · Zbl 1103.90058
[65] DOI: 10.1147/rd.471.0057 · Zbl 05420370
[66] DOI: 10.1007/s10107-012-0606-z · Zbl 1286.90117
[67] DOI: 10.1007/BF01097059 · Zbl 0841.90115
[68] DOI: 10.1016/S0165-1889(97)00032-8 · Zbl 0901.90016
[69] DOI: 10.1007/BF01580665 · Zbl 0349.90100
[70] DOI: 10.1002/aic.10717
[71] DOI: 10.1007/s10957-013-0396-3 · Zbl 1303.90074
[72] DOI: 10.1007/s10898-014-0166-2 · Zbl 1301.90063
[73] DOI: 10.1016/j.compchemeng.2010.02.014
[74] DOI: 10.1016/j.compchemeng.2011.01.026
[75] DOI: 10.1007/s10107-012-0555-6 · Zbl 1257.90079
[76] DOI: 10.1007/s10898-012-9874-7 · Zbl 1272.90034
[77] DOI: 10.1021/ie8019592
[78] DOI: 10.1016/j.apenergy.2009.01.022
[79] Nowak I., International Series of Numerical Mathematics (2005)
[80] DOI: 10.1007/BF01098364 · Zbl 0797.90108
[81] DOI: 10.1007/11751595_95 · Zbl 1172.91324
[82] DOI: 10.1287/moor.20.3.550 · Zbl 0845.90089
[83] DOI: 10.1007/978-1-4614-1927-3_14 · Zbl 1242.90155
[84] DOI: 10.1023/A:1008217604285 · Zbl 0881.90099
[85] DOI: 10.1007/s10479-009-0592-6 · Zbl 1195.91148
[86] N.W. Sawaya,Reformulations, relaxations and cutting planes for generalized disjunctive programming, PhD in Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, 2006.
[87] DOI: 10.1007/s10107-010-0371-9 · Zbl 1198.90330
[88] DOI: 10.1007/s10107-010-0340-3 · Zbl 1229.90144
[89] Schrijver A., Wiley-Interscience Series in Discrete Mathematics and Optimization (1998)
[90] DOI: 10.1016/j.dam.2007.09.020 · Zbl 1163.90691
[91] DOI: 10.1002/aic.11385
[92] DOI: 10.1007/BF00122429 · Zbl 0791.90056
[93] DOI: 10.1007/BF01100203 · Zbl 0844.90064
[94] Sherali H.D., Acta Math. Vietnam 22 pp 245– (1997)
[95] DOI: 10.1016/S0167-6377(97)00013-8 · Zbl 0885.90105
[96] Sherali H.D., Nonconvex Optimization and its Applications (1999)
[97] Strang G., Introduction to Linear Algebra, 3. ed. (2003) · Zbl 1046.15001
[98] DOI: 10.1016/0166-218X(88)90093-5 · Zbl 0663.90068
[99] Tardella F., Frontiers in Global Optimization pp 563– (2003)
[100] DOI: 10.1007/s11590-007-0065-2 · Zbl 1152.90614
[101] Tawarmalani M., Nonconvex Optimization and its Applications (2002)
[102] DOI: 10.1007/s10107-005-0581-8 · Zbl 1099.90047
[103] DOI: 10.1007/s10107-012-0581-4 · Zbl 1273.90165
[104] DOI: 10.1016/j.ces.2007.09.033
[105] DOI: 10.1016/j.compchemeng.2012.02.018
[106] DOI: 10.1016/0095-8956(82)90028-4 · Zbl 0478.05026
[107] DOI: 10.1007/s10107-004-0550-7 · Zbl 1137.90010
[108] DOI: 10.1007/s10107-004-0549-0 · Zbl 1137.90009
[109] DOI: 10.1021/ie800257x
[110] DOI: 10.1023/A:1009795911987 · Zbl 0904.90145
[111] DOI: 10.1007/s10898-010-9630-9 · Zbl 1254.90151
[112] DOI: 10.1080/10556788.2013.783032 · Zbl 1285.90043
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.