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.
Convexity in nonlinear integer programming
Favati P;
1990-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
prod_453057-doc_171328.pdf
non disponibili
Descrizione: Convexity in nonlinear integer programming
Tipologia:
Versione Editoriale (PDF)
Dimensione
1.41 MB
Formato
Adobe PDF
|
1.41 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.