-
Previous Article
Optimality results for a specific fractional problem
- JIMO Home
- This Issue
-
Next Article
Application of a modified VES production function model
Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming
1. | School of Economics and Management, Tongji University, Shanghai 200092, China |
2. | School of Information Science, Changzhou University, Jiangsu 203164, China |
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.
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. Google Scholar |
[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. 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. |
[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. |
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. |
[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. Google Scholar |
[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. 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. |
[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. |
gap(%) | time | nodes | gap(%) | time | nodes | |||||
6 | 18.94 | 141.81 | 3.02 | 1800.00 | 8305 | 0.02 | 727.71 | 533846 | ||
8 | 18.85 | 138.23 | 3.15 | 1800.00 | 7726 | 0.91 | 1753.91 | 1777822 | ||
10 | 18.74 | 110.77 | 3.49 | 1800.00 | 6052 | 1.67 | 1800.00 | 2084181 | ||
12 | 18.35 | 124.77 | 3.52 | 1800.01 | 6100 | 1.86 | 1800.00 | 1941049 | ||
6 | 20.40 | 124.90 | 34.75 | 1800.01 | 11038 | 27.09 | 1800.01 | 2183238 | ||
8 | 17.60 | 126.74 | 33.74 | 1800.01 | 10520 | 28.67 | 1800.01 | 2020237 | ||
10 | 16.68 | 116.01 | 34.17 | 1800.00 | 6104 | 27.61 | 1800.00 | 2612416 | ||
12 | 16.31 | 126.23 | 33.17 | 1800.00 | 8758 | 28.65 | 1800.01 | 2293060 | ||
6 | 18.78 | 129.74 | 58.70 | 1800.01 | 12628 | 50.00 | 1800.01 | 1990354 | ||
8 | 19.52 | 125.89 | 58.91 | 1800.00 | 11850 | 53.12 | 1800.01 | 2428332 | ||
10 | 19.00 | 125.75 | 58.75 | 1800.01 | 10990 | 55.25 | 1800.01 | 1911470 | ||
12 | 17.80 | 128.07 | 58.80 | 1800.00 | 11449 | 55.41 | 1800.01 | 1456779 | ||
6 | 48.31 | 314.17 | 3.01 | 1447.96 | 4793 | 1.97 | 1800.01 | 1357610 | ||
8 | 49.16 | 298.87 | 3.37 | 1445.44 | 3134 | 1.88 | 1441.80 | 1249562 | ||
10 | 48.54 | 320.01 | 3.37 | 1454.77 | 2186 | 2.04 | 1800.01 | 1024344 | ||
12 | 48.83 | 340.17 | 3.32 | 1502.79 | 2077 | 2.37 | 1800.01 | 811791 | ||
6 | 46.55 | 298.79 | 40.90 | 1800.00 | 3321 | 32.88 | 1800.01 | 2435679 | ||
8 | 43.08 | 295.82 | 40.66 | 1800.01 | 3452 | 34.04 | 1800.00 | 2132799 | ||
10 | 39.67 | 301.40 | 40.49 | 1800.00 | 3146 | 34.83 | 1800.00 | 1855355 | ||
12 | 42.47 | 279.30 | 40.24 | 1800.00 | 3648 | 35.28 | 1800.00 | 1701796 | ||
6 | 51.64 | 327.34 | 61.71 | 1800.00 | 4049 | 51.76 | 1800.01 | 1820914 | ||
8 | 51.08 | 294.60 | 61.29 | 1800.00 | 3859 | 53.30 | 1800.00 | 1806775 | ||
10 | 49.27 | 299.97 | 60.96 | 1800.00 | 3157 | 53.70 | 1800.00 | 1491932 | ||
12 | 50.44 | 276.10 | 60.52 | 1800.00 | 3824 | 55.42 | 1800.01 | 1238498 | ||
6 | 106.29 | 655.85 | 4.53 | 1800.00 | 1955 | 2.91 | 1800.00 | 760852 | ||
8 | 104.59 | 606.55 | 4.62 | 1800.00 | 1588 | 3.99 | 1800.01 | 546502 | ||
10 | 111.16 | 558.01 | 4.43 | 1800.01 | 1602 | 3.16 | 1800.00 | 608266 | ||
12 | 104.56 | 604.67 | 4.47 | 1800.00 | 1888 | 3.18 | 1800.00 | 687127 | ||
6 | 110.19 | 603.64 | 35.42 | 1800.00 | 1919 | 31.80 | 1800.01 | 736142 | ||
8 | 105.99 | 524.36 | 35.37 | 1800.00 | 1973 | 31.16 | 1800.00 | 800639 | ||
10 | 112.22 | 498.27 | 35.33 | 1800.00 | 2127 | 32.78 | 1800.01 | 764762 | ||
12 | 104.45 | 531.99 | 35.07 | 1800.01 | 2825 | 31.24 | 1800.00 | 954640 | ||
6 | 112.19 | 650.55 | 65.45 | 1800.00 | 1795 | 60.67 | 1800.01 | 571066 | ||
8 | 117.85 | 574.13 | 65.25 | 1800.01 | 1767 | 60.43 | 1800.00 | 695491 | ||
10 | 115.66 | 634.48 | 65.00 | 1800.00 | 2169 | 60.07 | 1800.00 | 707309 | ||
12 | 121.61 | 560.47 | 64.68 | 1800.00 | 2815 | 60.63 | 1800.00 | 831108 |
gap(%) | time | nodes | gap(%) | time | nodes | |||||
6 | 18.94 | 141.81 | 3.02 | 1800.00 | 8305 | 0.02 | 727.71 | 533846 | ||
8 | 18.85 | 138.23 | 3.15 | 1800.00 | 7726 | 0.91 | 1753.91 | 1777822 | ||
10 | 18.74 | 110.77 | 3.49 | 1800.00 | 6052 | 1.67 | 1800.00 | 2084181 | ||
12 | 18.35 | 124.77 | 3.52 | 1800.01 | 6100 | 1.86 | 1800.00 | 1941049 | ||
6 | 20.40 | 124.90 | 34.75 | 1800.01 | 11038 | 27.09 | 1800.01 | 2183238 | ||
8 | 17.60 | 126.74 | 33.74 | 1800.01 | 10520 | 28.67 | 1800.01 | 2020237 | ||
10 | 16.68 | 116.01 | 34.17 | 1800.00 | 6104 | 27.61 | 1800.00 | 2612416 | ||
12 | 16.31 | 126.23 | 33.17 | 1800.00 | 8758 | 28.65 | 1800.01 | 2293060 | ||
6 | 18.78 | 129.74 | 58.70 | 1800.01 | 12628 | 50.00 | 1800.01 | 1990354 | ||
8 | 19.52 | 125.89 | 58.91 | 1800.00 | 11850 | 53.12 | 1800.01 | 2428332 | ||
10 | 19.00 | 125.75 | 58.75 | 1800.01 | 10990 | 55.25 | 1800.01 | 1911470 | ||
12 | 17.80 | 128.07 | 58.80 | 1800.00 | 11449 | 55.41 | 1800.01 | 1456779 | ||
6 | 48.31 | 314.17 | 3.01 | 1447.96 | 4793 | 1.97 | 1800.01 | 1357610 | ||
8 | 49.16 | 298.87 | 3.37 | 1445.44 | 3134 | 1.88 | 1441.80 | 1249562 | ||
10 | 48.54 | 320.01 | 3.37 | 1454.77 | 2186 | 2.04 | 1800.01 | 1024344 | ||
12 | 48.83 | 340.17 | 3.32 | 1502.79 | 2077 | 2.37 | 1800.01 | 811791 | ||
6 | 46.55 | 298.79 | 40.90 | 1800.00 | 3321 | 32.88 | 1800.01 | 2435679 | ||
8 | 43.08 | 295.82 | 40.66 | 1800.01 | 3452 | 34.04 | 1800.00 | 2132799 | ||
10 | 39.67 | 301.40 | 40.49 | 1800.00 | 3146 | 34.83 | 1800.00 | 1855355 | ||
12 | 42.47 | 279.30 | 40.24 | 1800.00 | 3648 | 35.28 | 1800.00 | 1701796 | ||
6 | 51.64 | 327.34 | 61.71 | 1800.00 | 4049 | 51.76 | 1800.01 | 1820914 | ||
8 | 51.08 | 294.60 | 61.29 | 1800.00 | 3859 | 53.30 | 1800.00 | 1806775 | ||
10 | 49.27 | 299.97 | 60.96 | 1800.00 | 3157 | 53.70 | 1800.00 | 1491932 | ||
12 | 50.44 | 276.10 | 60.52 | 1800.00 | 3824 | 55.42 | 1800.01 | 1238498 | ||
6 | 106.29 | 655.85 | 4.53 | 1800.00 | 1955 | 2.91 | 1800.00 | 760852 | ||
8 | 104.59 | 606.55 | 4.62 | 1800.00 | 1588 | 3.99 | 1800.01 | 546502 | ||
10 | 111.16 | 558.01 | 4.43 | 1800.01 | 1602 | 3.16 | 1800.00 | 608266 | ||
12 | 104.56 | 604.67 | 4.47 | 1800.00 | 1888 | 3.18 | 1800.00 | 687127 | ||
6 | 110.19 | 603.64 | 35.42 | 1800.00 | 1919 | 31.80 | 1800.01 | 736142 | ||
8 | 105.99 | 524.36 | 35.37 | 1800.00 | 1973 | 31.16 | 1800.00 | 800639 | ||
10 | 112.22 | 498.27 | 35.33 | 1800.00 | 2127 | 32.78 | 1800.01 | 764762 | ||
12 | 104.45 | 531.99 | 35.07 | 1800.01 | 2825 | 31.24 | 1800.00 | 954640 | ||
6 | 112.19 | 650.55 | 65.45 | 1800.00 | 1795 | 60.67 | 1800.01 | 571066 | ||
8 | 117.85 | 574.13 | 65.25 | 1800.01 | 1767 | 60.43 | 1800.00 | 695491 | ||
10 | 115.66 | 634.48 | 65.00 | 1800.00 | 2169 | 60.07 | 1800.00 | 707309 | ||
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
Other articles
by authors
[Back to Top]