Quadratic cone cutting surfaces for quadratic programs with on-off constraints. (English) Zbl 1387.90174
Summary: We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of the convex hull of the set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces is second-order-cone representable. Via a shooting experiment, we provide empirical evidence as to the importance of each inequality type in improving the relaxation. Computational results that employ the new cutting surfaces to strengthen the relaxation for MIQPs arising from portfolio optimization applications are promising.
References:
| [1] | Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, Math. Program., 74, 121-140 (1996) · Zbl 0855.90090 |
| [2] | Foster, D. P.; George, E. I., The risk inflation criterion for multiple regression, Ann. Statist., 22, 1947-1975 (1994) · Zbl 0829.62066 |
| [3] | Aktürk, S.; Atamtürk, A.; Gürel, S., A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Oper. Res. Lett., 37, 187-191 (2009) · Zbl 1167.90518 |
| [4] | Aktürk, S.; Atamtürk, A.; Gürel, S., Aircraft rescheduling with cruise speed control, Oper. Res., 62, 829-845 (2014) · Zbl 1302.90054 |
| [5] | Wei, D.; Sestok, C. K.; Oppenheim, A. V., Sparse filter design under a quadratic constraint: Low-complexity algorithms, IEEE Trans. Signal Process., 61, 857-870 (2013) · Zbl 1393.94485 |
| [6] | Gao, J.; Li, D., Cardinality constraint linear-quadratic optimal control, IEEE Trans. Automat. Control, 56, 1936-1941 (2011) · Zbl 1368.90166 |
| [7] | Stubbs, R. A., Branch-and-cut methods for mixed 0-1 convex programming (1996), Northwestern University, (Ph.D. thesis) |
| [8] | Günlük, O.; Linderoth, J., Perspective relaxation of mixed integer nonlinear programs with indicator variables, Math. Program. Ser. B, 104, 186-203 (2010) · Zbl 1229.90106 |
| [9] | Ceria, S.; Soares, J., Convex programming for disjunctive optimization, Math. Program., 86, 595-614 (1999) · Zbl 0954.90049 |
| [10] | Frangioni, A.; Gentile, C., Perspective cuts for a class of convex 0-1 mixed integer programs, Math. Program., 106, 225-236 (2006) · Zbl 1134.90447 |
| [11] | Frangioni, A.; Gentile, C.; Lacalandra, F., Tighter approximated MILP formulations for unit commitment problems, IEEE Trans. Power Syst., 24, 105-113 (2009) |
| [12] | O. Günlük, J.T. Linderoth, Perspective reformulation and applications, in: Lee, J., Leyffer, S. (Eds.), The IMA Volumes in Mathematics and its Applications, Vol. 154, 2012, pp. 61-92.; O. Günlük, J.T. Linderoth, Perspective reformulation and applications, in: Lee, J., Leyffer, S. (Eds.), The IMA Volumes in Mathematics and its Applications, Vol. 154, 2012, pp. 61-92. · Zbl 1242.90134 |
| [13] | Castro, J.; Frangioni, A.; Gentile, C., Perspective reformulations of the CTA problem with \(\ell_2\) distances, Oper. Res., 62, 891-909 (2014) · Zbl 1302.90138 |
| [14] | Bienstock, D.; Michalka, A., Cutting planes for optimization on convex functions over nonconvex sets, SIAM J. Optim., 24, 643-677 (2014) · Zbl 1334.90130 |
| [15] | Zheng, X.; Sun, X.; Li, D., Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach, INFORMS J. Comput., 26, 690-703 (2014) · Zbl 1304.90154 |
| [16] | Dong, H.; Linderoth, J., On valid inequalities for quadratic programming with continuous variables and binary indicators, (IPCO 2013: The Sixteenth Conference on Integer Programming and Combinatorial Optimization. Vol. 7801 (2013), Springer), 169-180 · Zbl 1372.90073 |
| [17] | Meyer, R. R., Integer and mixed-integer programming models: General properties, J. Optim. Theory Appl., 16, 191-206 (1976) · Zbl 0283.90032 |
| [18] | Kılınç-Karzan, F., On minimal inequalities for mixed integer conic programs, Math. Oper. Res., 41, 477-510 (2016) · Zbl 1338.90275 |
| [19] | Kuhn, H. W., On the origin of the Hungarian method, (Lenstra, J. K.; Kan, A. H.G. R.; Schrijver, A., History of Mathematical Programming: A Collection of Personal Reminiscences (1991), Elsevier: Elsevier Amsterdam), 77-81, postscript of the article · Zbl 0796.01014 |
| [20] | Gomory, R. E.; Johnson, E. L.; Evans, L., Corner polyhedra and their connection with cutting planes, Math. Program. Ser. B, 96, 321-329 (2003) · Zbl 1082.90145 |
| [21] | Hunsaker, B., Measuring facets of polyhedra to predict usefulness in branch-and-cut algorithms (2003), Georgia Institute of Technology, (Ph.D. thesis) |
| [22] | Frangioni, A.; Gentile, C., SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Oper. Res. Lett., 35, 181-185 (2007) · Zbl 1149.90379 |
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.
