Istituto di Scienza e Tecnologie dell'Informazione     
Tardella F. On the equivalence between some discrete and continuous optimization problems. In: Annals of Operations Research, vol. 25 pp. 291 - 300. Baltzer Science Publishers, 1990.
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.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional