Reformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive Prorams

摘要

The general (nonconvex) quadratic multidimensional knapsack problem (QMKP) is one of the most important combinatorial optimization problems with many practical applications. The purpose of this article is to establish equivalent formulations of (QMKP) as so called copositive programs and completely positive programs. The resulting programs can then be handled by copositive programming methods, which are completely different from classical algorithms for directly solv-ing quadratic knapsack problems.