×

zbMATH — the first resource for mathematics

Recovering an optimal LP basis from an interior point solution. (English) Zbl 0814.90073
Summary: An important issue in the implementation of interior point algorithms for linear programming is the recovery of an optimal basic solution from an optimal interior point solution. In this paper we describe a method for recovering such a solution. Our implementation links a high-performance interior point code (OB1) with a high-performance simplex code (CPLEX). Results of our computational tests indicate that basis recovery can be done quickly and efficiently.

MSC:
90C05 Linear programming
Software:
CPLEX; DEVEX
PDF BibTeX Cite
Full Text: DOI
References:
[1] Adler, I.; Montiero, R.D.C., A geometric view of parametric linear programming, ()
[2] Bixby, R.E., Implementing the simplex method: the initial basis, ORSA J. comput., 4, 3, 267-287, (1992) · Zbl 0759.90063
[3] R.E. Bixby and I.J. Lustig, “An implementation of a strongly polynomial time algorithm for basis recovery”, in preparation.
[4] Gay, D.M., Electronic mail distribution of linear programming test problems, COAL newsletter, 13, 10-12, (1985)
[5] Gill, P.E.; Murray, W.; Wright, M.H., ()
[6] Güler, O.; Ye, Y., Convergence behavior of some interior-point algorithms, () · Zbl 0803.90087
[7] Harris, P.M.J., Pivot selection methods in the devex LP code, Math. programming, 5, 1-28, (1973) · Zbl 0261.90031
[8] H.-W. Jung, R.E. Marsten, M.J. Saltzman, “Numerical factorization methods for interior point algorithms”, ORSA J. Comput. 6(1), 94-105 · Zbl 0798.90099
[9] Liu, J.W.-H., Modification of the minimum-degree algorithm by multiple elimination, ACM trans. math. software, 11, 2, 141-153, (1985) · Zbl 0568.65015
[10] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Computational experience with a primal-dual interior point method for linear programming, Linear algebra appl., 152, 191-222, (1991) · Zbl 0731.65049
[11] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., On implementing Mehrotra’s predictor-corrector interior point method for linear programming, SIAM J. optim., 2, 435-449, (1992) · Zbl 0771.90066
[12] Marsten, R.E.; Saltzman, M.J.; Shanno, D.F.; Pierce, G.S.; Ballintijn, J.F., Implementation of a dual affine interior point algorithm for linear programming, ORSA J. comput., 1, 4, 287-297, (1989) · Zbl 0752.90046
[13] Megiddo, N., Pathways to the optimal set in linear programming, (), 131-158
[14] Megiddo, N., On finding primal- and dual-optimal bases, ORSA J. comput., 3, 1, 63-65, (1991) · Zbl 0755.90056
[15] Mehrotra, S., On finding a vertex solution using interior point methods, () · Zbl 0737.65050
[16] Suhl, U.H.; Suhl, L.M., Computing sparse LU factorizations for large-scale linear programming bases, ORSA J. comput., 2, 4, 325-335, (1990) · Zbl 0755.90059
[17] Wolfe, P., The composite simplex algorithm, SIAM rev., 7, 1, 42-54, (1965) · Zbl 0133.42703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.