An algorithm and new penalties for concave integer minimization over a polyhedron

The authors present a branch-and-bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch-and-bound search, the authors also develop a framework for computing new and existing penalites. Computational testing indicates that penalities based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek-Tomlin and Tuy penalties can provide further decreases in solution time.