Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T14:16:20.471Z Has data issue: false hasContentIssue false
  • English
  • Français

Driving from degeneracy

Published online by Cambridge University Press:  09 April 2009

Neil Cameron
Neil Cameron
Affiliation:
Department of Mathematics, Monash University Clayton, Victoria 3168, Australia
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A method is proposed for driving degenerate feasible solutions to linear programming problems away from essential degeneracy and in particular for identifying essentially degenerate optimal solutions. An essentially degenerate cycling example is also given, so answering a question raised earlier.

MSC classification

Secondary: 90C05: Linear programming 90C06: Large-scale problems 65K05: Mathematical programming methods
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 47 , Issue 2 , October 1989 , pp. 236 - 239
Copyright
Copyright © Australian Mathematical Society 1989

References

[1]Balinski, M. L. and Tucker, A. W., ‘Duality theory of linear programs: A constructive approach with applications’, SIAM Rev. 11 (1969), 347–377.Google Scholar
[2]Cameron, N., ‘Stationarity in the simplex method’, J. Austral. Math. Soc. Ser. A 43 (1987), 137–142.CrossRefGoogle Scholar
[3]Dantzig, G. B., Linear programming and extensions, (Princeton University Press, Princeton, N.J., 1963).Google Scholar
[4]Fletcher, R., ‘Degeneracy in the presence of round-off errors’, J. Linear Algebra Appl. 106 (1988), 149–183.CrossRefGoogle Scholar
[5]Osborne, M. R., Finite algorithms in optimization and data analysis (John Wiley & Sons Ltd., Chichester, 1985).Google Scholar
[6]Ryan, D. M. and Osborne, M. R., ‘On the solution of highly degenerate linear programmes’, Mathematical Programming 41 (1988), 385–392.CrossRefGoogle Scholar
[7]Wolfe, P., ‘A technique for resolving degeneracy in linear programming’, J. Soc. Indust. Appl. Math. 11 (1963), 205–211.CrossRefGoogle Scholar