Favati P., Tardella F. Convexity in nonlinear integer programming. Internal note IEI-B4-20, 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 restilts. | |

Subject | Convexity Submodularity Nonlinear integer programming Integer convexity |

1) Download Document PDF |

Open access Restricted Private