-
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] |
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
Other articles
by authors
[Back to Top]