Improved branch and bound algorithms for integer programming

This thesis is an investigation into improved branch and bound algorithms for linear and nonlinear mixed integer programming. Heuristics are developed for determining when the solution to a subproblem will involve fractional variables. When this situation is detected, the algorithm branches early, creating new subproblems with the fractional variables fixed at integer values. In this way, we avoid the work of solving the current subproblem to optimality.; Branch and bound codes for mixed integer linear programming problems have traditionally used the simplex method to solve the linear programming subproblems that arise. Early detection of fractional variables is difficult with the simplex method, because a variable might become basic (and thus fractional) at the last iteration of the simplex method. In contrast, with an interior point method, variables converge steadily to their optimal values. This makes it relatively easy to detect fractional variables.; To be useful in a branch and bound algorithm, an interior point method must generate lower bounds, which are used to fathom subproblems, and primal solution estimates, which the heuristics use to detect a fractional solution. Most interior point methods satisfy these requirements, but we concentrate on the dual-affine method and the primal-dual path following method. We describe experimental codes based on both methods. Computational results are provided for a number of randomly generated problems as well as for problems taken from the literature. These results indicate that the early branching idea is very effective, but more work is needed to make the experimental branch and bound codes competitive with simplex based branch and bound codes.; The early branching idea is also used in a branch and bound code for mixed integer nonlinear programs. This code uses the sequential quadratic programming method to solve the NLP subproblems. The SQP method generates estimates of the optimal solution at each iteration, which the early branching heuristics use. Computational results are provided for a number of sample problems taken from the literature. On some problems, the code with early branching uses 20% less CPU time than the code without early branching.