American Institute of Mathematical Sciences

Advanced
September  2021, 17(5): 2331-2343. 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  September 2021 Early access  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, 2021, 17 (5) : 2331-2343. 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]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[2]

Xin Zhao, Jinyan Fan. On subspace properties of the quadratically constrained quadratic program. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1625-1640. doi: 10.3934/jimo.2017010
[3]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[4]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[5]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213
[6]

Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[7]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[8]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
[9]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[10]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[11]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[12]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[13]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
[14]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653
[15]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[16]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543
[17]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[18]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83
[19]

Yong Xia. Convex hull of the orthogonal similarity set with applications in quadratic assignment problems. Journal of Industrial & Management Optimization, 2013, 9 (3) : 689-701. doi: 10.3934/jimo.2013.9.689
[20]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (224)
  • HTML views (637)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy