AN ALGORITHM AND NEW PENALTIES FOR CONCAVE INTEGER MINIMIZATION OVER A POLYHEDRON

We present a branch-and-bound algorithm for globally minimizing a conc ave function over linear constraints and integer variables. Concave co st functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To r educe the number of subproblems solved during the branch-and-bound sea rch, we also develop a framework for computing new and existing penalt ies. Computational testing indicates that penalties based on the Tuy c utting plane provide large decreases in solution time for some problem s. A combination of Driebeek-Tomlin and Tuy penalties can provide furt her decreases in solution time. (C) 1994 John Wiley & Sons, Inc.