Continuous Representation Techniques in Combinatorial Optimization

Approaches to an analytic description of vertex located discrete sets are presented. They are based on algebraic-topological features of the sets and properties of functions over them. One is a polyhedral-surface approach that represents a set as an intersection of its convex hull (a combinatorial polytope) and a circumscribed surface. Another one describes a set as an intersection of surfaces. These are applied for deriving various analytic representations of such sets as the Boolean set, binary set, permutation matrices set, the set of Boolean vectors with a given number of ones, and the cross-polytope vertex set. Among the sets' representations, polyhedral-spherical ones represent the sets by a quadratic system of constraints and tangent representationsby polynomial equations of a degree less or equal to four. These results open new opportunities for applying standard continuous optimization methods to combinatorial problems on vertex located sets, as well as for developing novel approaches, which use a specific of the sets and problems. Amongst relaxation techniques, the most promising directions are surface relaxations and algorithms that combine polyhedral and surface relaxations. In the sphere of reformulation approaches, it is important to develop new ways to convexify the original problem and then solve it to the optimum.