Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming

Xiaojin Zheng; Zhongyi Jiang

doi:10.3934/jimo.2020071

Article Contents

2021, Volume 17, Issue 5: 2331-2343. Doi: 10.3934/jimo.2020071

This issue Previous Article Computing shadow prices with multiple Lagrange multipliers Next Article Principal component analysis with drop rank covariance matrix

Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming

Xiaojin Zheng^1, and
Zhongyi Jiang^2, ,

1.
School of Economics and Management, Tongji University, Shanghai 200092, China
2.
School of Information Science, Changzhou University, Jiangsu 203164, China

^* Corresponding author: Zhongyi Jiang
^* Corresponding author: Zhongyi Jiang

Received: September 30, 2019

Revised: November 30, 2019

Early access: March 2020

Published: September 2021

This research was supported by the National Natural Science Foundation of China under Grants 11671300

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

The paper proposes a novel class of quadratically constrained convex reformulations (QCCR) for semi-continuous quadratic programming. We first propose the class of QCCR for the studied problem. Next, we discuss how to polynomially find the best reformulation corresponding with the tightest continuous bound within this class. The properties of the proposed QCCR are then studied. Finally, preliminary computational experiments are conducted to illustrate the effectiveness of the proposed approach.

Keywords:

Mathematics Subject Classification: Primary: 90C11, 90C20; Secondary: 90C22.

Citation:

FullText(HTML)

Table 1. Comparison results of perspective reformulation and QCCR for Problem $ \rm{(TP)} $

$ n $	$ K $	$ {\rm T_{PR}} $	$ {\rm T_{QCP}} $	$ ({\rm PR_{SOCP}}) $			$ ({\rm QCP}) $
$ n $	$ K $	$ {\rm T_{PR}} $	$ {\rm T_{QCP}} $	gap(%)	time	nodes	gap(%)	time	nodes
$ 200^+ $	6	18.94	141.81	3.02	1800.00	8305	0.02	727.71	533846
$ 200^+ $	8	18.85	138.23	3.15	1800.00	7726	0.91	1753.91	1777822
$ 200^+ $	10	18.74	110.77	3.49	1800.00	6052	1.67	1800.00	2084181
$ 200^+ $	12	18.35	124.77	3.52	1800.01	6100	1.86	1800.00	1941049
$ 200^0 $	6	20.40	124.90	34.75	1800.01	11038	27.09	1800.01	2183238
$ 200^0 $	8	17.60	126.74	33.74	1800.01	10520	28.67	1800.01	2020237
$ 200^0 $	10	16.68	116.01	34.17	1800.00	6104	27.61	1800.00	2612416
$ 200^0 $	12	16.31	126.23	33.17	1800.00	8758	28.65	1800.01	2293060
$ 200^- $	6	18.78	129.74	58.70	1800.01	12628	50.00	1800.01	1990354
$ 200^- $	8	19.52	125.89	58.91	1800.00	11850	53.12	1800.01	2428332
$ 200^- $	10	19.00	125.75	58.75	1800.01	10990	55.25	1800.01	1911470
$ 200^- $	12	17.80	128.07	58.80	1800.00	11449	55.41	1800.01	1456779
$ 300^+ $	6	48.31	314.17	3.01	1447.96	4793	1.97	1800.01	1357610
$ 300^+ $	8	49.16	298.87	3.37	1445.44	3134	1.88	1441.80	1249562
$ 300^+ $	10	48.54	320.01	3.37	1454.77	2186	2.04	1800.01	1024344
$ 300^+ $	12	48.83	340.17	3.32	1502.79	2077	2.37	1800.01	811791
$ 300^0 $	6	46.55	298.79	40.90	1800.00	3321	32.88	1800.01	2435679
$ 300^0 $	8	43.08	295.82	40.66	1800.01	3452	34.04	1800.00	2132799
$ 300^0 $	10	39.67	301.40	40.49	1800.00	3146	34.83	1800.00	1855355
$ 300^0 $	12	42.47	279.30	40.24	1800.00	3648	35.28	1800.00	1701796
$ 300^- $	6	51.64	327.34	61.71	1800.00	4049	51.76	1800.01	1820914
$ 300^- $	8	51.08	294.60	61.29	1800.00	3859	53.30	1800.00	1806775
$ 300^- $	10	49.27	299.97	60.96	1800.00	3157	53.70	1800.00	1491932
$ 300^- $	12	50.44	276.10	60.52	1800.00	3824	55.42	1800.01	1238498
$ 400^+ $	6	106.29	655.85	4.53	1800.00	1955	2.91	1800.00	760852
$ 400^+ $	8	104.59	606.55	4.62	1800.00	1588	3.99	1800.01	546502
$ 400^+ $	10	111.16	558.01	4.43	1800.01	1602	3.16	1800.00	608266
$ 400^+ $	12	104.56	604.67	4.47	1800.00	1888	3.18	1800.00	687127
$ 400^0 $	6	110.19	603.64	35.42	1800.00	1919	31.80	1800.01	736142
$ 400^0 $	8	105.99	524.36	35.37	1800.00	1973	31.16	1800.00	800639
$ 400^0 $	10	112.22	498.27	35.33	1800.00	2127	32.78	1800.01	764762
$ 400^0 $	12	104.45	531.99	35.07	1800.01	2825	31.24	1800.00	954640
$ 400^- $	6	112.19	650.55	65.45	1800.00	1795	60.67	1800.01	571066
$ 400^- $	8	117.85	574.13	65.25	1800.01	1767	60.43	1800.00	695491
$ 400^- $	10	115.66	634.48	65.00	1800.00	2169	60.07	1800.00	707309
$ 400^- $	12	121.61	560.47	64.68	1800.00	2815	60.63	1800.00	831108

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140. doi: 10.1007/BF02592208.
[2]	A. Billionnet and S. Elloumi, Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Mathematical Programming, 109 (2007), 55-68. doi: 10.1007/s10107-005-0637-9.
[3]	A. Billionnet, S. Elloumi and A. Lambert, Extending the QCR method to general mixed-integer programs, Mathematical Programming, 131 (2012), 381-401. doi: 10.1007/s10107-010-0381-7.
[4]	A. Billionnet, S. Elloumi and M. Plateau, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method, Discrete Applied Mathematics, 157 (2009), 1185-1197. doi: 10.1016/j.dam.2007.12.007.
[5]	A. Borghetti, A. Frangioni, F. Lacalandra and C. Nucci, Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment, IEEE Transactions on Power Systems, 18 (2003), 313-323.
[6]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004. doi: 10.1017/CBO9780511804441.
[7]	A. Frangioni and C. Gentile, Perspective cuts for a class of convex 0–1 mixed integer programs, Mathematical Programming, 106 (2006), 225-236. doi: 10.1007/s10107-005-0594-3.
[8]	A. Frangioni and C. Gentile, Solving nonlinear single-unit commitment problems with ramping constraints, Operations Research, 54 (2006), 767-775. doi: 10.1287/opre.1060.0309.
[9]	A. Frangioni and C. Gentile, SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters, 35 (2007), 181-185. doi: 10.1016/j.orl.2006.03.008.
[10]	A. Frangioni and C. Gentile, A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Operations Research Letters, 37 (2009), 206-210. doi: 10.1016/j.orl.2009.02.003.
[11]	A. Frangioni, C. Gentile, E. Grande and A. Pacifici, Projected perspective reformulations with applications in design problems, Operations Research, 59 (2011), 1225-1232. doi: 10.1287/opre.1110.0930.
[12]	M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), 2009.
[13]	O. Günlük and J. Linderoth, Perspective reformulations of mixed integer nonlinear programs with indicator variables, Mathematical Programming, 124 (2010), 183-205. doi: 10.1007/s10107-010-0360-z.
[14]	P. Hammer and A. Rubin, Some remarks on quadratic programming with 0-1 variables, R.I.R.O., 3 (1970), 67-79.
[15]	R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985. doi: 10.1017/CBO9780511810817.
[16]	S. Kazarlis, A. Bakirtzis and V. Petridis, A genetic algorithm solution to the unit commitment problem, IEEE Transactions on Power Systems, 11 (1996), 83-92. doi: 10.1109/59.485989.
[17]	P. Pardalos and G. Rodgers, Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144. doi: 10.1007/BF02247879.
[18]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.
[19]	B. Wu, X. Sun, D. Li and X. Zheng, Quadratic convex reformulations for semicontinuous quadratic programming, SIAM Journal on Optimization, 27 (2017), 1531-1553. doi: 10.1137/15M1012232.
[20]	X. Zheng, X. Sun and D. Li, Improving the performance of miqp solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach, INFORMS Journal on Computing, 26 (2014), 690-703. doi: 10.1287/ijoc.2014.0592.