\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming

  • * Corresponding author: Zhongyi Jiang

    * Corresponding author: Zhongyi Jiang

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

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90C11, 90C20; Secondary: 90C22.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV
  • [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. BillionnetS. 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. BillionnetS. 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. BorghettiA. FrangioniF. Lacalandra and C. Nucci, Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment, IEEE Transactions on Power Systems, 18 (2003), 313-323. 
    [6] S. Boyd and  L. VandenbergheConvex 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. FrangioniC. GentileE. 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.
    [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. JohnsonMatrix Analysis, Cambridge University Press, 1985.  doi: 10.1017/CBO9780511810817.
    [16] S. KazarlisA. 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. WuX. SunD. 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. ZhengX. 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.
  • 加载中

Tables(1)

SHARE

Article Metrics

HTML views(1076) PDF downloads(368) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return