Nonconvex continuous models for combinatorial optimization problems with application to satisfiability and node packing problems

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.