The authors introduce a notion of convexity, called integer convexity, for a function defined on a discrete rectangle X of points in Zn, by means of ordinary convexity of an extended function defined on the convex hull of X in Rn. One of the most interesting features of integrally convex functions is the coincidence between their local and global minima. The authors also analyze some connections between the convexity of a function on Rn and the integer convexity of its restriction to Zn, determining some nontrivial classes of integrally convex functions. Finally, they prove that a submodular integrally convex function can be minimized in polynomial time over any discrete rectangle in Zn, thereby extending well-known results of Grotschel, Lovasz and Schrijver and of Picard and Ratliff, and the authors present an algorithm for this problem together with some computational results.
