An efficient ordering method and data structure of the interior point method (putting emphasis on the minimum deficiency ordering)

Ordering plays an important role in solving an LP problem with sparse matrix by the interior point method. Since ordering is NP-complete, the authors try to find an efficient heuristic method. The objective of this paper is to present an efficient heuristic ordering method for implementation of the minimum deficiency method. Both the ordering method and the data structure play important roles in implementation. First the authors define a new heuristic pseudo-deficiency ordering method and a data structure for the method-quotient graph and clique storage. Next they show an experimental result in terms of time and nonzero numbers by NETLIB problems. [In Korean.]