American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020071

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

Received  October 2019 Revised  December 2019 Published  March 2020

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

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: Mixed-integer quadratically constrained quadratic programming, quadratic programming, quadratically constrained convex reformulation, quadratic convex reformulation, semi-continuous.
Mathematics Subject Classification: Primary: 90C11, 90C20; Secondary: 90C22.
Citation: Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020071
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[6] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), 2009. Google Scholar

[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.  Google Scholar

[14]

P. Hammer and A. Rubin, Some remarks on quadratic programming with 0-1 variables, R.I.R.O., 3 (1970), 67-79.   Google Scholar

[15] R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985.  doi: 10.1017/CBO9780511810817.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[18]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.  doi: 10.1137/1038003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[6] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge university press, 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), 2009. Google Scholar

[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.  Google Scholar

[14]

P. Hammer and A. Rubin, Some remarks on quadratic programming with 0-1 variables, R.I.R.O., 3 (1970), 67-79.   Google Scholar

[15] R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, 1985.  doi: 10.1017/CBO9780511810817.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[18]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.  doi: 10.1137/1038003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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}) $
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
Table Options

Download as excel

$ n $ $ K $ $ {\rm T_{PR}} $ $ {\rm T_{QCP}} $ $ ({\rm PR_{SOCP}}) $ $ ({\rm 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
[1]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032
[2]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[3]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[4]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[5]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[6]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364
[7]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[8]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[9]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[10]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[11]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334
[12]

Norman Noguera, Ademir Pastor. Scattering of radial solutions for quadratic-type Schrödinger systems in dimension five. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021018
[13]

Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033
[14]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[15]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[16]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[17]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[18]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[19]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113
[20]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (72)
  • HTML views (337)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences