Combining Constraint Propagation and Discrete Ellipsoid-Based Search to Solve the Exact Quadratic Knapsack Problem

摘要: We propose an extension to the discrete ellipsoid-based search (DEBS) solve exact quadratic knapsack problem (EQKP), important class of optimization with a number practical applications. For first time, our enables DEBS convex quadratically constrained problems linear constraints. show that adding constraint propagation results in algorithm is able outperform both state-of-the-art MIP solver CPLEX and semi-definite programming approach by about one order magnitude on two variations EQKP.