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 |

1) Download Document PDF |

Open access Restricted Private