Reoptimization in Interior-Point Methods with Application to Integer Programming

Date
1999-05
Journal Title
Journal ISSN
Volume Title
Publisher
Description
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/19416
Abstract

This 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.

Description
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/19416
Advisor
Degree
Type
Technical report
Keywords
Citation

McZeal, Cassandra M.. "Reoptimization in Interior-Point Methods with Application to Integer Programming." (1999) https://hdl.handle.net/1911/101933.

Has part(s)
Forms part of
Published Version
Rights
Link to license
Citable link to this page