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]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055
[3]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2543-2557. doi: 10.3934/dcds.2020374
[4]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[5]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[6]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046
[7]

Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021026
[8]

Norman Noguera, Ademir Pastor. Scattering of radial solutions for quadratic-type Schrödinger systems in dimension five. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3817-3836. doi: 10.3934/dcds.2021018
[9]

Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074
[10]

Alexander Tolstonogov. BV solutions of a convex sweeping process with a composed perturbation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021012
[11]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[12]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[13]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067
[14]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[15]

Kai Kang, Taotao Lu, Jing Zhang. Financing strategy selection and coordination considering risk aversion in a capital-constrained supply chain. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021042
[16]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[17]

Bingru Zhang, Chuanye Gu, Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs†. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061
[18]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[19]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2635-3652. doi: 10.3934/dcds.2020378
[20]

Ruonan Liu, Run Xu. Hermite-Hadamard type inequalities for harmonical $ (h1,h2)- $convex interval-valued functions. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021005

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (95)
  • HTML views (419)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences