An algorithm for concave integer minimization over a polyhedron

The authors present an algorithm for solving the problem of globally minimizing a concave function over the integers contained in a compact polyhedron. The objective function of this problem need not be separable or even analytically defined. As far as the authors are aware, the algorithm is the first ever proposed for this problem. Among the major advantages of the algorithm are that no nonlinear computations or optimizations are required, and that it allows one to exploit the polyhedral nature of X. The authors discuss these and other advantages and disadvantages of the algorithm, and they present some preliminary computational experience using the present computer code for the algorithm. This computational experience seems to indicate that the algorithm is quite practical for solving many concave integer minimization problems over compact polyhedra.