Convexity in nonlinear integer programming

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.