Ordering plays an important role in solving an LP problem with sparse matrix by the interior point method. Since ordering is NP-complete, we try to find an efficient heuristic method.
The objective of this paper is to present an efficient heuristic o...
Ordering plays an important role in solving an LP problem with sparse matrix by the interior point method. Since ordering is NP-complete, we 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 we define a new heuristic pseudo-deficiency ordering method and a data structure for the method - quotient graph and clique storage. Next we show an experimental result in terms of time and nonzero numbers by NETLIB problems.