On the equivalence between some discrete and continuous optimization problems

The simplex algorithm for linear programming is based on the well-known equivalence between the problem of maximizing a linear function f on a polyhedron P and the problem of maximizing f over the set Vp of all vertices of P. The equivalence between these two problems is also exploited by some methods for maximizing a convex or quasi-convex function on a polyhedron. In this paper we determine some very general conditions under which the problem of maximizing f over P is equivalent, in some sense, to the problem of maximizing f over Vp . In particular, we show that these two problems are equivalent when f is convex or quasi-convex on all the line segments contained in P and parallel to some edge of P. In the case where P is a box our results extend a well-known result of Rosenberg for 0-1 problems. Furthermore, when P is a box or a simplex, we determine some classes of functions that can be maximized in polynomial time over P.