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 nonlinear integer programming problems. A seperable convex objective function is minimized over a feasible region defined by the constraints which are separable and convex. The ‘traditional branch and bound approach’ has been to relax integrality restrictions on the decision variables and solve hard nonlinear continuous subproblems. In contrast, the algorithm presented in this paper linearizes all nonlinear functions to form al linear programming problem at each node, which can be solved efficiently by the simplex method. Appropriate branching, bounding, fathoming, partitioning, and reoptimizing schemes are developed. In the computational study, the present ‘linear subproblem approach’ is compared with the ‘traditional nonlinear subproblem approach’. For the test problems randomly generated, the algorithm is shown to be better than the nonlinear subproblem approach.