The final NETLIB-LP results. (English) Zbl 1137.90613
Summary: With standard linear programming solvers there is always some uncertainty about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the exact optimal objective values for all NETLIB problems.
MSC:
| 90C05 | Linear programming |
| 90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |
References:
| [1] | Avis, D., A revised implementation of the reverse search vertex enumeration algorithm, (Kalai, G.; Ziegler, G. M., Polytopes—Combinatorics and Computation. Polytopes—Combinatorics and Computation, DMV Seminar, Vol. 29 (2000), Birkhäuser: Birkhäuser Basel), 177-198, Software available at http://cgm.cs.mcgill.ca /avis/lrs.html · Zbl 0960.68171 |
| [2] | Chvátal, V., Linear Programming (1983), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0318.05002 |
| [3] | M. Dhiflaoui, S. Funke, C. Kwappik, K. Mehlhorn, M. Seel, E. Schömer, R. Schulte, D. Weber, Certifying and repairing solutions to large lps - how good are lp-solvers? in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003. Paper available at; M. Dhiflaoui, S. Funke, C. Kwappik, K. Mehlhorn, M. Seel, E. Schömer, R. Schulte, D. Weber, Certifying and repairing solutions to large lps - how good are lp-solvers? in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003. Paper available at · Zbl 1176.90395 |
| [4] | K. Fukuda, cddlib reference manual, cddlib version 092a, 2001. Program available at; K. Fukuda, cddlib reference manual, cddlib version 092a, 2001. Program available at |
| [5] | B. Gärtner. Exact arithmetic at low cost—a case study in linear programming, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998.; B. Gärtner. Exact arithmetic at low cost—a case study in linear programming, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998. |
| [6] | M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Bulletin No. 13, 1985, pp. 10-12. Data available at; M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Bulletin No. 13, 1985, pp. 10-12. Data available at |
| [7] | P.E. Gill, W. Murray, M.H. Wright, Numerical Linear Algebra and Optimization, Vol. 1, Addison-Wesley, 1991.; P.E. Gill, W. Murray, M.H. Wright, Numerical Linear Algebra and Optimization, Vol. 1, Addison-Wesley, 1991. · Zbl 0714.65063 |
| [8] | GNU multiple precision arithmetic library (GMP), version 4.1.2., 2003. Code and documentation available at http://www.swox.com/gmp; GNU multiple precision arithmetic library (GMP), version 4.1.2., 2003. Code and documentation available at http://www.swox.com/gmp |
| [9] | Goldberg, D., What every computer scientist should know about floating-point arithmetic, ACM Comput. Surveys, 23, 1, 5-48 (1991) |
| [10] | IBM optimization library guide and reference, 1997. For an online reference see; IBM optimization library guide and reference, 1997. For an online reference see |
| [11] | ILOG CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, USA. ILOG CPLEX 8.0 Reference Manual, 2002. Information available at; ILOG CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, USA. ILOG CPLEX 8.0 Reference Manual, 2002. Information available at |
| [12] | C. Kwappik, Exact linear programming, Master’s Thesis, Universität des Saarlandes, Fachbereich 14, 1998.; C. Kwappik, Exact linear programming, Master’s Thesis, Universität des Saarlandes, Fachbereich 14, 1998. |
| [13] | SoPlex—The sequential object-oriented simplex class library, 2003. See; SoPlex—The sequential object-oriented simplex class library, 2003. See |
| [14] | R.J. Vanderbei, Linear Programming: Foundations and Extensions, 2nd Edition, Kluwer Academic, Dordrecht, 2001.; R.J. Vanderbei, Linear Programming: Foundations and Extensions, 2nd Edition, Kluwer Academic, Dordrecht, 2001. · Zbl 1043.90002 |
| [15] | R. Wunderling, Paralleler und objektorientierter Simplex, Technical Report TR 96-09, Konrad-Zuse-Zentrum Berlin, 1996. Electronically available at; R. Wunderling, Paralleler und objektorientierter Simplex, Technical Report TR 96-09, Konrad-Zuse-Zentrum Berlin, 1996. Electronically available at |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
