Reoptimization in Interior-Point Methods with Application to Integer Programming

This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/19416This thesis examines current reoptimization techniques for interior-point methods available in the literature and studies their efficacy in a branch-and-bound framework for 0/1 mixed integer programming problems. This work is motivated by the observation that there are instances of integer programming problems where each individual linear program generated in a branch-and-bound tree can be solved much faster by an interior-point algorithm than by a simplex algorithm, in spite of the fact that effective "warm-start" techniques are available for the latter but not for the former. Because of many unresolved issues surrounding effective reoptimization techniques for interior-point methods, interior-point algorithms have not been commonly used as linear programming solvers in a branch-and-bound framework. In this work, we identify and examine a number of key factors that may affect and even preclude effective reoptimization for interior-point algorithms in the branch-and-bound framework, including change in optimal partition, distance to optimality, and primal infeasibility. We conclude that even though various "warm-start" techniques are capable of reducing the reoptimization cost to some extent, for certain problem instances a rapid reoptimization cannot always be expected from interior-point methods due to their inherent limitations. Continued research is needed in the direction of the present study in order to provide comprehensive guidelines for the most effective utilization of interior-point algorithms in a branch-and-bound algorithm