Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of Linear Programming

We describe a common extension of the fundamental theorem of Linear Programming on the existence of a global minimum in a vertex for lower bounded linear programs, and of the Frank-Wolfe theorem on the existence of the minimum of a lower bounded quadratic function on a polyhedron. We then show that several known results providing continuous formulations for discrete optimization problems can be easily derived and generalized with our result. These include the Quadratic Programming formulation of the maximum clique problem by Motzkin and Straus and its weighted extension by Gibbons et al., the equivalence between the minimization of a multilinear function on the continuous and discrete unit hypercube by Rosenberg, and a recent continuous polynomial formulation of the maximum independent set problem by Abello et al. Furthermore, we use our extension of the fundamental theorem of Linear Programming to obtain combinatorial formulations and polynomiality results for some nonlinear problems with simple polyhedral constraints. © 2004.