Back to search

University of British Columbia

The interior point method and its application to the fractional (g.f)-factor problem

Abstract

dc:description

This thesis contains six chapters. From Chapter 1 to Chapter 5, we give an exposition of interiorpoint methods (IPM). In Chapter 1 a brief survey of the recent development in interior-point methods is given. Chapter 2 gives a detailed description on the history of the primal-dual pathfollowing methods for linear programming. Chapter 3 introduces several predictor-corrector methods. This is an efficient and powerful class of interior-point methods and a lot ofattention has been paid during recent years. Chapter 4 discusses the various efficient linear algebraic methods which are used for solving the Newton equations system. Practically, most of the computational effort in implementations of interior-point methods is taken up in solving the Newton equations system. Therefore an efficient method for solving the Newton equations system can make the whole algorithm very efficient. Chapter 5 talks about the presolving procedure which is used to reduce the size of the LP problem and to make the system sparser before passing the problems to optimization. The presolve procedure is a very efficient adjunct for any LP solver. In chapter 6, we apply the interior-point method to the fractional (g,f)-factor problem, we first exploit the special structure of the fractional (g,f)-factor problem and propose two IPM algorithms to take advantage of the special structure of the fractional (g,f)-factor problem. In each of the two algorithms, we use a different linear programming model for the fractional (g/f)-factor problem in order to make the corresponding algorithm more efficient. Then, we discuss three starting point approaches and the strategy for creating our test problems. Last, we use the high order predictor-corrector primal-dual path-following code HOPDM[45] to test the three starting point approaches and from the computational results we get the conclusion that a fractional (g/f)-factor problem-specific starting point can save iterations of the IPM and make the IPM more efficient for solving fractional (g,f)-factor problem.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
1996

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shi, Ping

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/6038

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Shi, Ping. The interior point method and its application to the fractional (g.f)-factor problem. master's thesis, University of British Columbia, 1996. http://hdl.handle.net/2429/6038