Show simple item record

dc.contributor.advisor Bixby, Robert E.
dc.contributor.advisor Zhang, Yin
dc.creatorMcZeal, Cassandra Moore
dc.date.accessioned 2009-06-04T06:38:06Z
dc.date.available 2009-06-04T06:38:06Z
dc.date.issued 1999
dc.identifier.urihttps://hdl.handle.net/1911/19416
dc.description.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 can not 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.
dc.format.extent 111 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectMathematics
dc.title Reoptimization in interior-point methods with application to integer programming
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Mathematics
thesis.degree.discipline Natural Sciences
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation McZeal, Cassandra Moore. "Reoptimization in interior-point methods with application to integer programming." (1999) Diss., Rice University. https://hdl.handle.net/1911/19416.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record