×

Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time. (English) Zbl 1387.90156

Authors’ abstract: Non-convex knapsack separable quadratic optimization with compact box constraints is an NP-hard problem. We present tight lower and upper bounding procedures that are computationally-efficient as the problem size grows. The lower bound is based on Lagrangian relaxation, and it is computed in linear-time. When the bound is not an exact global solution, a worst-case bound-quality measure is developed. Moreover, the lower bounding (LB) solution is improved to construct a feasible solution, leading to an upper bound (UB) on the given problem. The UB is based on fixing the convex variables and a subset of non-convex and linear variables at the LB solution, and considering the remaining problem, which is always feasible. The UB is computable with linear-time complexity, and it is the global optimum in certain verifiable cases when the duality gap is zero. In our limited computational experiments, the UB has very small relative gap with an exact global optimum solution when there is a nonzero duality gap. Performance of the bounds is demonstrated through a broad range of randomly generated problem instances and comparisons with existing global and non-global solvers. The proposed method on these indefinite problems of extremely large size is an order of magnitude faster than the alternative solvers, including IBM’s commercial software Cplex12.6.

MSC:

90C11 Mixed integer programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows, 4th edn. Wiley, New York (2009) · Zbl 1200.90002 · doi:10.1002/9780471703778
[2] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Applications, 3rd edn. Wiley, New York (2006) · Zbl 1140.90040 · doi:10.1002/0471787779
[3] Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33-52 (2012) · Zbl 1257.90065 · doi:10.1007/s12532-011-0033-9
[4] Cominetti, R., Mascarenhas, W., Silva, P.: A Newton’s method for the continuous quadratic knapsack problem. Math. Program. Comput. 6(2), 151-169 (2014) · Zbl 1328.65135 · doi:10.1007/s12532-014-0066-y
[5] Dai, Y.H., Fletcher, R.: New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Program. 106(3), 403-421 (2006) · Zbl 1134.90030 · doi:10.1007/s10107-005-0595-2
[6] Edirisinghe, C., Jeong, J.: An efficient global algorithm for a class of indefinite separable quadratic programs. Math. Program. 158(1), 143-173 (2016) · Zbl 1343.90058 · doi:10.1007/s10107-015-0918-x
[7] Floyd, R.W., Rivest, R.L.: Algorithm 489: the algorithm select for finding the i th smallest of n elements. Commun. ACM 18(3), 173 (1975) · doi:10.1145/360680.360694
[8] Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0-1 knapsack problem. Manag. Sci. 45(3), 414-424 (1999) · Zbl 1231.90338 · doi:10.1287/mnsc.45.3.414
[9] Moré, J.J., Vavasis, S.A.: On the solution of concave knapsack problems. Math. Program. 49(1), 397-411 (1991) · Zbl 0723.90059
[10] Nakagawa, Y., James, R.J.W., Rego, C., Edirisinghe, C.: Entropy-based optimization of nonlinear separable discrete decision models. Manag. Sci. 60(3), 695-707 (2014) · doi:10.1287/mnsc.2013.1772
[11] Patriksson, M., Strömberg, C.: Algorithms for the continuous nonlinear resource allocation problem—new implementations and numerical studies. Eur. J. Oper. Res. 243(3), 703-722 (2015) · Zbl 1346.90672 · doi:10.1016/j.ejor.2015.01.029
[12] Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271-2284 (2005) · Zbl 1116.90089 · doi:10.1016/j.cor.2004.03.002
[13] Robinson, A.G., Jiang, N., Lerme, C.S.: On the continuous quadratic knapsack-problem. Math. Program. 55(1), 99-108 (1992) · Zbl 0762.90061 · doi:10.1007/BF01581193
[14] Vavasis, S.A.: Local minima for indefinite quadratic knapsack-problems. Math. Program. 54(2), 127-153 (1992) · Zbl 0751.90058 · doi:10.1007/BF01586048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.