An algorithm of the simplex method using a~dual basis

G. I. Zabinyako

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 18 (2015) no. 4, pp. 349-359.

Résumé

An algorithm of the simplex method not requiring an explicit updating of the $LU$ decomposition in iterations is considered. Solutions obtained with fixed $LU$ factors are corrected using small auxiliary matrices. The results of numerical experiments are presented.

Bibliographie

[1] Murtaf B., Sovremennoe linejnoe programmirovanie. Teoriya i praktika, Mir, M., 1984 | MR

[2] Bartels R. H., Golub G. H., “The simplex method of linear programming using the LU decomposition”, Commun. ACM, 12 (1969), 266–268 | DOI | Zbl

[3] Forrest J. J. H., Tomlin J. A., “Updating triangular factors of the basis to maintain sparsity in the product form simplex method”, Math. Program., 2 (1972), 263–278 | DOI | MR | Zbl

[4] Reid J. K., “A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases”, Math. Program., 24 (1982), 55–69 | DOI | MR | Zbl

[5] Forrest J. J. H., Tomlin J. A., Vector processing in simplex and interior methods for linear programming, IBM Res. Report. No RJ 6390 (62372), 1988

[6] Bisschop J., Meeraus F., “Matrix augmentation and partitioning in the updating of the basis inverse”, Math. Program., 13 (1977), 241–254 | DOI | MR | Zbl

[7] Proctor P. E., “Implementation of the double-basis simplex method for the general linear programming problem”, SIAM J. Algebraic Discrete Methods, 6:4 (1985), 567–575 | DOI | MR | Zbl

[8] Eldersveld S. K., Saunders M. A., “A block-LU update for large-scale linear programming”, SIAM J. Matrix Anal. Appl., 13:1 (1992), 191–201 | DOI | MR | Zbl

[9] Markowitz H. M., “The elimination form of the inverse and its application to linear programming”, Management Science, 3 (1957), 255–269 | DOI | MR | Zbl

[10] Saunders M. A., Large-Scale Numerical Optimization, , 2014 http://web.stanford.edu/class/msande318/notes/notes05-updates.pdf

[11] Olschowka M., Neumaier A., “A new pivoting strategy for Gaussian elimination”, Linear Algebra Appl., 240:1–3 (1996), 131–151 | DOI | MR

[12] http://www.opensource.org/licenses/cpl1.0.php

[13] Pissanetski S., Tekhnologiya razrezhennykh matrits, Mir, M., 1988 | MR

[14] Jonker R., Volgenant A., “A shortest augmenting path algorithm for dense and sparse linear assignment problems”, Computing, 38 (1987), 325–340 | DOI | MR | Zbl

[15] Jonker R., Vogenant A., Linear Assignment Problem, http://www.assignmentproblems.com/LAPJV.htm

[16] Karypis G., Kumar V., Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4.0, , University of Minnesota, Department of Computer Science/Army HPC Research Center, Minneapolis, MN 55455, 1998 http://glaros.dtc.umn.edu/gkhome/views/metis

[17] Gay D. M., “Electronic mail distribution of linear programming test problems”, Mathematical Programming Society COAL Newsletter, 13 (1985), 10–12

[18] Zabinyako G. I., Kotelnikov E. A., “Linear optimization programs”, NCC Bulletin. Series Numerical Analysis, 11, Novosibirsk, 2002, 103–112 | Zbl

[19] Davis T. A., University of Florida sparse matrix collection, http://www.cise.ufl.edu

[20] Duff I. S., Koster J., “The design and use of algorithms for permuting large entries to the diagonal of sparse matrices”, SIAM J. Matrix Anal. Appl., 20:4 (1999), 889–901 | DOI | MR | Zbl

[21] Zabinyako G. I., “Perepostroenie obratnykh matrits”, Sib. zhurn. industr. matem., 12:3 (2009), 41–51 | MR | Zbl

[22] Schenk O., Gartner K., “Solving unsymmetric sparse systems of linear equation with PARDISO”, Future Generation Computer Systems, 20 (2004), 475–487 | DOI