Complete Solutions to Mixed Integer Programming

摘要

This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP-hard problem can be converted into concave maximization dual problems without duality gap. And the dual problems can be solved, under certain conditions, by polynomial algorithms.