Canonical dual approach to solving 0-1 quadratic programming problems

Abstract

By using the canonical dual transformation developedrecently, we derive a pair of canonical dual problems for 0-1quadratic programming problems in both minimization and maximizationform. Regardless convexity, when the canonical duals are solvable,no duality gap exists between the primal and corresponding dualproblems. Both global and local optimality conditions are given. Analgorithm is presented for finding global minimizers, even when theprimal objective function is not convex. Examples are included toillustrate this new approach.