A BRANCH-AND-BOUND ALGORITHM FOR SOLVING SEPARABLE CONVEX INTEGER PROGRAMMING-PROBLEMS

This paper proposes a branch and bound method that solves a class of n onlinear integer programming problems. A separable convex objective fu nction is minimized over a feasible region defined by the constraints which are separable and convex. The ''traditional branch and bound app roach'' has been to relax integrality restrictions on the decision var iables and solve hard nonlinear continuous subproblems. In contrast, t he algorithm presented in this paper linearizes all nonlinear function s to form a linear programming problem at each node, which can be solv ed efficiently by the simplex method. Appropriate branching, bounding, fathoming, partitioning, and reoptimizing schemes are developed. In t he computational study, our ''linear subproblem approach'' is compared with the ''traditional nonlinear subproblem approach''. For the test problems randomly generated, our algorithm is shown to be better than the nonlinear subproblem approach.