Istituto di Scienza e Tecnologie dell'Informazione     
Favati P., Tardella F. Convexity in nonlinear integer programming. Internal note IEI-B4-20, 1990.
We introduce a notion of convexity, called integer convexity, for a function defined on a discrete rectangle X of points in Z∆n, by means of ordinary convexity of an extended function defined on the convex hull of X in R∆n. One of the most interesting features of integrally convex functions is the coincidence between their local and global minima. We also analyze some connections between the convexity of a function on R∆n and the integer convexity of its restriction to Z∆n, determining some nontrivial classes of integrally convex functions. Finally, we prove that a submodular integrally convex function can be minimized in polynomial time over any discrete rectangle in Z∆n, thereby extending well-known results of Grotschel, Lovasz and Schrijver and of Picard and Ratliff, and we present an algorithm for this problem together with some computational restilts.
Subject Convexity
Nonlinear integer programming
Integer convexity

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