We show how a large class of combinatorial optimization problems can be reformulated as a nonconvex minimization problem over the unit hyper cube with continuous variables. No additional constraints are required; all constraints are incorporated in the n onconvex objective function, which is a polynomial function. The application of the general transform to satisfiability and node packing problems is discussed, and various approximation algorithms are briefly reviewed. To give an indication of the strength of the proposed approaches, we conclude with some computational results on instances of the graph coloring problem.

GENERAL (acm G.0), GENERAL (acm F.0)
Nonlinear programming (msc 90C30), Combinatorial optimization (msc 90C27), Boolean programming (msc 90C09)
CWI
Software Engineering [SEN]

Warners, J.P. (1997). Nonconvex continuous models for combinatorial optimization problems with application to satisfiability and node packing problems. Software Engineering [SEN]. CWI.