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

Variable fixing method by weighted average for the continuous quadratic knapsack problem

  • * Corresponding author: Hsin-Min Sun

    * Corresponding author: Hsin-Min Sun 
Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by
  • We analyze the method of solving the separable convex continuous quadratic knapsack problem by weighted average from the viewpoint of variable fixing. It is shown that this method, considered as a variant of the variable fixing algorithms, and Kiwiel's variable fixing method generate the same iterates. We further improve the algorithm based on the analysis regarding the semismooth Newton method. Computational results are given and comparisons are made among the state-of-the-art algorithms. Experiments show that our algorithm has significantly good performance; it behaves very much like an $ O(n) $ algorithm with a very small constant.

    Mathematics Subject Classification: Primary: 65K05; Secondary: 90C20.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  uncorrelated test

    Dimension Iterations Time (msec) Iterations Time (msec)
    $ n $ avg max min avg max min avg max min avg max min
    QWMVA2 QWMVA
    50000 4.9 9 3 1.5 1.8 1.2 7.8 11 6 1.6 1.9 1.4
    100000 5.7 12 3 3.0 4.3 2.6 8.2 11 7 3.3 3.7 2.5
    500000 5.7 13 4 16.0 23.0 13.5 8.7 12 7 17.5 20.0 14.0
    1000000 5.7 14 3 38.5 71.0 30.0 8.8 12 7 46.6 55.0 33.0
    1500000 5.7 13 4 62.1 116.7 46.7 8.9 12 7 76.7 91.7 56.7
    2000000 6.0 14 4 86.7 164.0 64.0 8.9 12 7 104.3 122.0 68.0
    Newton Secant
    50000 4.7 8 3 2.3 2.7 1.8 8.2 12 6 3.0 4.0 2.2
    100000 5.2 9 3 4.7 5.5 3.8 8.7 14 6 6.1 8.2 4.1
    500000 5.3 9 4 25.8 30.5 20.5 8.6 14 6 31.2 43.0 21.5
    1000000 5.2 10 3 52.0 63.0 42.0 8.4 13 6 60.9 82.0 44.0
    1500000 5.1 9 3 77.0 93.3 58.3 8.4 14 6 93.2 130.0 63.3
    2000000 5.2 11 4 102.1 124.0 84.0 8.5 15 7 126.5 170.0 94.0
    Variable fixing Median search
    50000 7.8 11 6 2.5 2.8 2.2 16.7 17 16 4.3 4.5 3.6
    100000 8.2 11 7 5.0 5.4 4.4 17.7 18 17 8.4 9.0 7.3
    500000 8.7 12 7 30.6 34.5 26.5 19.9 20 19 45.2 50.5 39.0
    1000000 8.8 12 7 65.1 73.0 55.0 20.9 21 20 92.8 99.0 80.0
    1500000 8.9 12 7 98.1 108.3 85.0 21.6 22 21 144.4 151.7 125.0
    2000000 8.9 12 7 129.4 144.0 108.0 22.0 22 21 192.4 202.0 166.0
     | Show Table
    DownLoad: CSV

    Table 2.  weakly correlated test

    Dimension Iterations Time (msec) Iterations Time (msec)
    $ n $ avg max min avg max min avg max min avg max min
    QWMVA2 QWMVA
    50000 5.0 11 3 1.4 2.0 1.2 7.7 10 6 1.6 1.7 1.3
    100000 5.5 11 3 2.9 3.9 2.4 7.9 11 7 3.1 3.5 2.4
    500000 5.7 13 3 15.5 22.0 13.5 8.2 11 7 16.8 18.0 14.5
    1000000 5.5 13 3 37.4 62.0 27.0 8.4 11 7 44.6 50.0 31.0
    1500000 5.4 13 4 60.3 108.3 48.3 8.6 10 7 74.2 83.3 56.7
    2000000 5.9 13 4 84.4 146.0 66.0 8.6 12 7 100.4 110.0 64.0
    Newton Secant
    50000 4.6 8 3 2.2 2.4 1.8 8.0 12 6 2.9 4.2 1.9
    100000 5.0 9 3 4.4 4.8 3.5 8.4 14 6 5.8 8.8 3.7
    500000 5.1 8 3 24.3 28.0 19.5 8.5 13 6 29.6 45.0 19.5
    1000000 5.0 9 3 49.4 59.0 37.0 8.2 13 6 57.3 91.0 39.0
    1500000 5.0 8 3 74.2 90.0 60.0 8.3 13 6 88.3 130.0 56.7
    2000000 5.1 10 3 98.9 118.0 78.0 8.3 14 6 120.8 182.0 76.0
    Variable fixing Median search
    50000 7.7 10 6 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.6
    100000 7.9 11 7 4.8 5.3 4.4 17.7 18 17 8.3 8.7 7.2
    500000 8.2 11 7 29.1 31.5 26.0 19.9 20 19 44.8 47.5 39.0
    1000000 8.4 11 7 61.9 67.0 55.0 21.0 21 20 91.7 97.0 80.0
    1500000 8.6 10 7 93.4 100.0 83.3 21.6 22 21 141.9 150.0 123.3
    2000000 8.6 12 7 125.3 138.0 102.0 21.9 22 21 189.7 198.0 162.0
     | Show Table
    DownLoad: CSV

    Table 3.  correlated test

    Dimension Iterations Time (msec) Iterations Time (msec)
    $ n $ avg max min avg max min avg max min avg max min
    QWMVA2 QWMVA
    50000 5.1 12 3 1.4 1.8 1.2 7.6 9 7 1.6 1.7 1.4
    100000 5.1 11 3 2.9 3.7 2.5 7.8 10 6 3.1 3.4 2.5
    500000 5.5 12 3 15.5 21.0 13.0 8.1 10 7 16.7 18.0 14.5
    1000000 5.6 12 3 37.2 58.0 27.0 8.3 10 7 44.0 49.0 36.0
    1500000 5.5 14 3 60.4 96.7 46.7 8.4 11 7 72.0 80.0 53.3
    2000000 5.5 13 3 82.1 128.0 62.0 8.3 10 7 97.9 106.0 88.0
    Newton Secant
    50000 4.8 7 3 2.1 2.4 1.7 8.1 12 6 2.8 4.3 1.6
    100000 4.7 9 3 4.3 4.8 3.4 8.0 11 6 5.8 8.7 3.8
    500000 5.0 8 3 23.8 28.5 18.0 8.3 12 6 29.0 44.5 19.0
    1000000 4.9 8 3 48.9 60.0 37.0 8.2 12 6 57.2 88.0 38.0
    1500000 5.0 9 3 73.1 93.3 56.7 8.3 12 6 91.1 131.7 58.3
    2000000 4.9 7 3 96.1 116.0 72.0 8.1 11 6 114.3 176.0 80.0
    Variable fixing Median search
    50000 7.6 9 7 2.4 2.6 2.2 16.7 17 16 4.2 4.4 3.8
    100000 7.8 10 6 4.8 5.5 4.4 17.7 18 17 8.3 8.7 7.3
    500000 8.1 10 7 28.8 31.0 26.0 19.9 20 19 44.8 47.5 39.5
    1000000 8.3 10 7 61.1 68.0 55.0 20.9 21 20 91.2 97.0 81.0
    1500000 8.4 11 7 92.2 103.3 83.3 21.6 22 21 142.2 150.0 123.3
    2000000 8.3 10 7 122.0 136.0 110.0 21.9 22 21 188.6 198.0 172.0
     | Show Table
    DownLoad: CSV

    Table 4.  Multicommodity network flow test

    Dimension Iterations Time (msec) Iterations Time (msec)
    $ n $ avg max min avg max min avg max min avg max min
    QWMVA2 QWMVA
    50000 5.9 8 4 1.1 1.3 0.9 5.9 8 4 1.1 1.2 0.8
    100000 5.8 9 4 2.2 2.6 1.8 5.8 9 4 2.1 2.5 1.7
    500000 6.1 9 4 12.2 14.0 10.0 6.1 9 4 11.5 13.5 9.0
    1000000 6.2 9 4 27.1 32.0 21.0 6.2 9 4 25.5 30.0 19.0
    1500000 6.1 11 4 44.1 51.7 35.0 6.1 11 4 42.0 50.0 33.3
    2000000 6.2 8 4 59.5 68.0 48.0 6.2 8 4 56.8 66.0 44.0
    Newton Secant
    50000 5.9 8 4 1.9 2.4 1.2 14.2 18 9 3.0 3.9 1.9
    100000 5.8 9 4 3.8 4.9 2.6 14.0 19 9 6.0 8.2 4.2
    500000 6.1 9 4 22.7 30.5 14.5 14.2 19 9 32.4 43.5 23.5
    1000000 6.2 9 4 46.9 64.0 29.0 14.2 19 9 64.5 87.0 40.0
    1500000 6.1 11 4 69.1 95.0 43.3 14.0 21 10 95.6 145.0 66.7
    2000000 6.1 8 4 92.7 124.0 58.0 14.2 16 11 128.1 148.0 98.0
    Variable fixing Median search
    50000 5.9 8 4 1.9 2.4 1.2 16.6 17 16 3.3 3.6 3.1
    100000 5.8 9 4 3.7 4.7 2.5 17.7 18 17 6.5 6.9 6.1
    500000 6.1 9 4 22.0 28.5 14.0 19.9 20 19 35.8 38.0 33.0
    1000000 6.2 9 4 45.6 61.0 27.0 20.9 21 20 73.3 77.0 69.0
    1500000 6.1 11 4 66.5 91.7 41.7 21.6 22 21 112.9 118.3 108.3
    2000000 6.2 8 4 90.9 118.0 56.0 21.9 22 21 151.0 162.0 144.0
     | Show Table
    DownLoad: CSV

    Table 5.  Results for the projection in SVM training. The values reported are the average number of iterations and the average computing time in milliseconds. For $ \textsf{BLGnapsack} $ only the time is reported

    Set $ n $ QWMVA2 QWMVA Newton Secant BLG Var. Fixing
    Iter. Time Iter. Time Iter. Time Iter. Time Time Iter. Time
    UCI 1065 5.02 0.023 7.84 0.021 4.98 0.022 8.20 0.031 0.025 7.84 0.017
    UCI 2265 5.28 0.061 8.55 0.061 5.28 0.081 9.03 0.109 0.093 8.55 0.066
    UCI 3185 5.37 0.102 8.23 0.097 5.31 0.133 9.06 0.176 0.165 8.23 0.127
    UCI 6370 5.51 0.249 8.67 0.248 5.44 0.316 9.46 0.445 0.402 8.67 0.363
    UCI 12740 5.87 0.540 9.37 0.555 5.80 0.665 9.98 1.036 0.843 9.37 0.776
    MNIST 800 3.32 0.018 5.72 0.022 3.14 0.015 6.77 0.016 0.012 5.72 0.017
    MNIST 1600 3.56 0.038 5.94 0.045 3.31 0.029 7.01 0.033 0.029 5.94 0.035
    MNIST 3200 3.65 0.092 6.37 0.111 3.45 0.068 7.11 0.074 0.103 6.37 0.098
    MNIST 6400 3.56 0.189 6.73 0.231 3.47 0.161 7.25 0.170 0.222 6.73 0.260
    MNIST 11702 3.74 0.357 7.39 0.438 3.59 0.322 7.32 0.344 0.398 7.39 0.525
     | Show Table
    DownLoad: CSV
  • [1] E. G. BirginJ. M. Martínez and M. Raydan, Algorithm 813: SPG—software for convex-constrained optimization, ACM Trans. Math. Softw., 27 (2001), 340-349. 
    [2] G. R. Bitran and A. C. Hax, Disaggregation and resource allocation using convex knapsack problems with bounded variables, Manag. Sci., 27 (1981), 431-441.  doi: 10.1287/mnsc.27.4.431.
    [3] B. E. Boser, I. M. Guyon and V. N. Vapnik, A training algorithm for optimal margin classifiers, in Proc. 5th Annu. Wkshp. Comput. Learning Theory (COLT'92) (ed. D. Haussler), ACM Press, (1992), 144–152.
    [4] K. M. Bretthauer and B. Shetty, Quadratic resource allocation with generalized upper bounds, Oper. Res. Lett., 20 (1997), 51-57.  doi: 10.1016/S0167-6377(96)00039-9.
    [5] K. M. BretthauerB. Shetty and S. Syam, A branch-and-bound algorithm for integer quadratic knapsack problems, ORSA J. Comput., 7 (1995), 109-116.  doi: 10.1287/ijoc.7.1.109.
    [6] K. M. BretthauerB. Shetty and S. Syam, A projection method for the integer quadratic knapsack problem, J. Oper. Res. Soc., 47 (1996), 457-462.  doi: 10.1057/jors.1996.44.
    [7] P. Brucker, An O($n$) algorithm for quadratic knapsack problems, Oper. Res. Lett., 3 (1984), 163-166.  doi: 10.1016/0167-6377(84)90010-5.
    [8] P. H. Calamai and J. J. Moré, Quasi-Newton updates with bounds, SIAM J. Numer. Anal., 24 (1987), 1434-1441.  doi: 10.1137/0724092.
    [9] R. CominettiW. F. Mascarenhas and P. J. S. Silva, A Newton's method for the continuous quadratic knapsack problem, Math. Prog. Comp., 6 (2014), 151-169.  doi: 10.1007/s12532-014-0066-y.
    [10] C. Cortes and V. Vapnik, Support-vector networks, Machine Learning, 20 (1995), 273-297. 
    [11] S. Cosares and D. S. Hochbaum, Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources, Math. Oper. Res., 19 (1994), 94-111.  doi: 10.1287/moor.19.1.94.
    [12] R. W. CottleS. G. Duvall and K. Zikan, A Lagrangian relaxation algorithm for the constrained matrix problem, Nav. Res. Logist. Q., 33 (1986), 55-76.  doi: 10.1002/nav.3800330106.
    [13] Y.-H. Dai and R. Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Math. Program., 106 (2006), 403-421.  doi: 10.1007/s10107-005-0595-2.
    [14] T. A. Davis, W. W. Hager and J. T. Hungerford, An efficient hybrid algorithm for the separable convex quadratic knapsack problem, ACM Trans. Math. Softw., 42 Article 22 (2016), 25 pages. doi: 10.1145/2828635.
    [15] J.-P. DussaultJ. A. Ferland and B. Lemaire, Convex quadratic programming with one constraint and bounded variables, Math. Program., 36 (1986), 90-104.  doi: 10.1007/BF02591992.
    [16] B. C. Eaves, On quadratic programming, Manag. Sci., 17 (1971), 698-711.  doi: 10.1287/mnsc.17.11.698.
    [17] C. Edirisinghe and J. Jeong, Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time, Math. Program., 164 (2017), 193-227.  doi: 10.1007/s10107-016-1082-7.
    [18] A. Frangioni and E. Gorgone, A library for continuous convex separable quadratic knapsack problems, Eur. J. Oper. Res., 229 (2013), 37-40.  doi: 10.1016/j.ejor.2013.02.038.
    [19] W. W. Hager and J. T. Hungerford, Continuous quadratic programming formulations of optimization problems on graphs, Eur. J. Oper. Res., 240 (2015), 328-337.  doi: 10.1016/j.ejor.2014.05.042.
    [20] W. W. Hager and Y. Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J. Disc. Math., 12 (1999), 500-523.  doi: 10.1137/S0895480199335829.
    [21] M. HeldP. Wolfe and H. P. Crowder, Validation of subgradient optimization, Math. Program., 6 (1974), 62-88.  doi: 10.1007/BF01580223.
    [22] R. HelgasonJ. Kennington and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Math. Program., 18 (1980), 338-343.  doi: 10.1007/BF01588328.
    [23] D. S. Hochbaum and S. P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Math. Program., 69 (1995), 269-309.  doi: 10.1007/BF01585561.
    [24] J. Jeong, Indefinite Knapsack Separable Quadratic Programming: Methods and Applications, Ph.D. Dissertation, University of Tennessee, Knoxville, 2014. Available from: https://trace.tennessee.edu/utk_graddiss/2704/
    [25] N. Katoh, A. Shioura and T. Ibaraki, Resource allocation problems, in Handbook of Combinatorial Optimization (eds. P.M. Pardalos, DZ Du and R.L. Graham), Springer, (2013), 2897–2988. doi: 10.1007/978-1-4419-7997-1.
    [26] K. C. Kiwiel, On linear-time algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 134 (2007), 549-554.  doi: 10.1007/s10957-007-9259-0.
    [27] K. C. Kiwiel, Breakpoint searching algorithms for the continuous quadratic knapsack problem, Math. Program., 112 (2008), 473-491.  doi: 10.1007/s10107-006-0050-z.
    [28] K. C. Kiwiel, Variable fixing algorithms for the continuous quadratic knapsack problem, J. Optim. Theory Appl., 136 (2008), 445-458.  doi: 10.1007/s10957-007-9317-7.
    [29] N. MaculanC. P. SantiagoE. M. Macambira and M. H. C. Jardim, An $O(n)$ algorithm for projecting a vector on the intersection of a hyperplane and a box in $\mathbb{R}^n$, J. Optim. Theory Appl., 117 (2003), 553-574.  doi: 10.1023/A:1023997605430.
    [30] N. Megiddo and A. Tamir, Linear time algorithms for some separable quadratic programming problems, Oper. Res. Lett., 13 (1993), 203-211.  doi: 10.1016/0167-6377(93)90041-E.
    [31] S. S. Nielsen and S. A. Zenios, Massively parallel algorithms for singly constrained convex programs, ORSA J. Comput., 4 (1992), 166-181.  doi: 10.1287/ijoc.4.2.166.
    [32] P. M. Pardalos and N. Kovoor, An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds, Math. Program., 46 (1990), 321-328.  doi: 10.1007/BF01585748.
    [33] P. M. PardalosY. Ye and C.-G. Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl., 152 (1991), 69-91.  doi: 10.1016/0024-3795(91)90267-Z.
    [34] M. Patriksson, A survey on the continuous nonlinear resource allocation problem, Eur. J. Oper. Res., 185 (2008), 1-46.  doi: 10.1016/j.ejor.2006.12.006.
    [35] M. Patriksson and C. Strömberg, Algorithms for the continuous nonlinear resource allocation problem–-New implementations and numerical studies, Eur. J. Oper. Res., 243 (2015), 703-722.  doi: 10.1016/j.ejor.2015.01.029.
    [36] A. G. RobinsonN. Jiang and C. S. Lerme, On the continuous quadratic knapsack problem, Math. Program., 55 (1992), 99-108.  doi: 10.1007/BF01581193.
    [37] B. Shetty and R. Muthukrishnan, A parallel projection for the multicommodity network model, J. Oper. Res. Soc., 41 (1990), 837-842. 
    [38] H.-M. Sun and R.-L. Sheu, Minimum variance allocation among constrained intervals, J. Glob. Optim., 74 (2019), 21-44.  doi: 10.1007/s10898-019-00748-3.
    [39] J. A. Ventura, Computational development of a Lagrangian dual approach for quadratic networks, Networks, 21 (1991), 469-485.  doi: 10.1002/net.3230210407.
  • 加载中

Tables(5)

SHARE

Article Metrics

HTML views(2225) PDF downloads(185) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return