A Class of Nonlinear Integer Programs Solvable by a Single Linear Program

Abstract

Although the addition of integrality constraints to the existing constraints of an optimization problem will, in general, make the determination of an optimal solution more difficult, we consider here a class of nonlinear programs in which the imposition of integrality constraints on the variables makes it possible to solve the problem by a single, easily-constructed 1inear program. The class of problems addressed has a separable convex objective function and a totally unimodular constraint matrix. Such problems arise in logistic and personnel assignment applications.