Degeneracy Graphs and Simplex Cycling
Many problems in economics can be formulated as linearly constrained mathematical optimization problems, where the feasible solution set X represents a convex polyhedral set. In practice, the set X frequently contains degenerate verti- ces, yielding diverse problems in the determination of an optimal solution as well as in postoptimal analysis.The so- called degeneracy graphs represent a useful tool for des- cribing and solving degeneracy problems. The study of dege- neracy graphs opens a new field of research with many theo- retical aspects and practical applications. The present pu- blication pursues two aims. On the one hand the theory of degeneracy graphs is developed generally, which will serve as a basis for further applications. On the other hand dege- neracy graphs will be used to explain simplex cycling, i.e. necessary and sufficient conditions for cycling will be de- rived.
16 pages matching variables in this book
Results 1-3 of 16
What people are saying - Write a review
We haven't found any reviews in the usual places.
Degeneracy problems in mathematical optimization
Theory of degeneracy graphs
Concepts to explain simplex cycling
3 other sections not shown
a x n-degeneracy graphs a x n-index graph anticycling rules Appendix bases basic solution biuniquely called cells characterization column vectors component computational connected construct cycling examples contains convex polyhedral set corresponding Definition degeneracy graph Gy degeneracy problems degenerate vertex denote determinant inequality system edge paths example with simplex Fernuniversitat Hagen graph theory graphs cf Gy be given Gy,d halfspace i-th index sets induced point set initial tableau integer programming isomorphic Kruse Legend Lemma Let the reduced line graph linear complementarity problem linear inequalities linear optimization problem linear programming Mathematical Programming matrix maximal modified Moreover node set nodes of G number of iterations Operations Research partition pivot step pivoting rules polynomial polytope positive degeneracy graph procedures Proof reduced linear optimization reduced problem 4.1.4 representation system Section set system shadow prices simplex algorithm simplex cycle simplex method solution set solving subspace Theorem variables zero