PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Favati P., Tardella F. Convexity in nonlinear integer programming. In: Ricerca Operativa, vol. 53 pp. 3 - 44. Ass. Italiana di ricerca Operativa (ed.). FrancoAngeli, 1990.
 
 
Abstract
(English)
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 results.
Subject Convexity
Integer convexity
Non linear integer programming
Submodularity


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