科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2016-7
