Implementation of an interior point method with basis preconditioning
- The implementation of a linear programming interior point solver is described that is based on iterative linear algebra. The linear systems are preconditioned by a basis matrix, which is updated from one interior point iteration to the next to bound the entries in a certain tableau matrix. The update scheme is based on simplex-type pivot operations and is implemented using linear algebra techniques from the revised simplex method. An initial basis is constructed by a crash procedure after a few interior point iterations. The basis at the end of the interior point solve provides the starting basis for a crossover method which recovers a basic solution to the linear program. Results of a computational study on a diverse set of medium to large-scale problems are discussed.
Metadaten| Author: | Lukas Schork, Jacek Gondzio |
|---|
| DOI: | https://doi.org/10.1007/s12532-020-00181-8 |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2020 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 12 |
|---|
| Issue: | 4 |
|---|
| Page Number: | 33 |
|---|
| First Page: | 603 |
|---|
| Last Page: | 635 |
|---|
| Mathematical Programming Computation : | MPC 2020 - Issue 4 |
|---|