Branch and bound methods for solving a class of nonlinear integer programming problems

This dissertation is concerned with development of the branch and bound methods for solving a class of nonlinear integer programming problems where a convex separable objective function is minimized over a feasible region defined by convex separable functions. Several important real-world problems have been formulated as Convex Separable Nonlinear Integer Problem (CSNIP). Examples are optimum distribution of effort problems, resource allocation problems, certain capital budgeting problems, some reliability problems, and lot sizing (recorder interval) problems.;Two algorithms for solving the CSNIP are presented. Both algorithms transform the CSNIP into a linear program by use of a linearization technique based on tangential underestimation of the convex functions. Therefore, at a branch and bound node, a linear program is solved by the simplex method. While both algorithms use essentially the same linearization technique, they solve different formulations of the linear program and thus their solution strategies are different.;As a computational study, these two algorithms are compared with a "conventional approach" where a nonlinear continuous problem is solved by a nonlinear programming technique at each branch and bound node. One of the proposed algorithms is shown to be computationally promising for nonlinearly constrained problems when compared to the conventional approach. Finally, some ideas are presented to enhance the performance of the algorithms. We also discuss the possibility of extending the algorithms to separable convex network programming problems.