Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time

• 成果类型: Article
• 署名作者: Edirisinghe, Chanaka; Jeong, Jaehwan
• 署名单位: Rensselaer Polytechnic Institute; Radford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1082-7
• 发表日期: 2017
• 页码: 193-227
• 关键词: knapsack-problems

摘要

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.