An efficient global algorithm for a class of indefinite separable quadratic programs

• 成果类型: Article
• 署名作者: Edirisinghe, Chanaka; Jeong, Jaehwan
• 署名单位: Rensselaer Polytechnic Institute; Radford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0918-x
• 发表日期: 2016
• 页码: 143-173
• 关键词: knapsack-problems; SUBJECT; bounds

摘要

We present a global algorithm for indefinite knapsack separable quadratic programs with bound constraints. The upper bounds on variables with nonconvex terms are assumed to be infinite in the algorithmic development. By characterizing optimal solutions of the problem, we enumerate a subset of KKT points to determine a global optimum. The enumeration is made efficient by developing a theory for shrinking and partitioning the search domain of KKT multipliers. The global algorithmic procedure is developed based on interval and point testing techniques that have roots in solving strictly convex problems. Our algorithm has quadratic (worst-case) complexity and its performance is demonstrated on a broad range of randomly generated problem instances and comparisons with existing global and local solvers. It turns out that our method can solve these nonconvex problems of extremely large size in a fraction of the time (relative to commercial software such as CPLEX 12.6) on a desktop computer. Furthermore, a feasible upper bounding scheme is developed for the case when the variables with nonconvex terms are allowed to have finite upper limits, using an iterative application of the above global algorithm, and the computational experience is presented.