Many problems in economics can be formulated as early constrained mathematical optimization problems, where the feasible solution set X represents a convex polyhedral set. In practice, the set X frequently contains degenerate vertices, yielding diverse problems in the determination of an optimal solution as well as in postoptimal analysis. Degeneracy graphs represent a useful tool for describing and solving degeneracy problems. The study of degeneracy graphs opens a new field of research with many theoretical aspects and practical applications. The present monograph pursues two aims. On the one hand, the theory of degeneracy graphs is developed generally, to serve as a basis for further applications. On the other hand, degeneracy graphs are used to explain simplex cycling, and necessary and sufficient conditions for cycling are derived.
1. Introduction.- 2. Degeneracy problems in mathematical optimization.- 2.1. Convergence problems in the case of degeneracy.- 2.1.1 Cycling in linear complementarity problems.- 2.1.2 Cycling in network problems.- 2.1.3 Cycling in bottleneck linear programming.- 2.1.4 Cycling in integer programming.- 2.2 Efficiency problems in the case of degeneracy.- 2.2.1 Efficiency loss by weak redundancy.- 2.2.2 Efficiency problems from the perspective of the theory of computational complexity.- 2.3 Degeneracy problems within the framework of postoptimal analysis.- 2.4. On the practical meaning of degeneracy.- Summary of Chapter 2.- 3. Theory of degeneracy graphs.- 3.1. Fundamentals.- 3.1.1 The concept of degeneracy.- 3.1.2 The graphs of a polytope.- 3.1.3 Degeneracy graphs.- 3.2 Theory of ? x n-degeneracy graphs.- 3.2.1 Foundations of the theory of finite sets.- 3.2.2 Characterization of ? x n-degeneracy graphs.- 3.2.3 Properties of ? x n-degeneracy graphs.- 3.3. Theory of 2 x n-degeneracy graphs.- 3.3.1 Characterization of 2 x n-degeneracy graphs.- 3.3.2 Properties of 2 x n-degeneracy graphs.- Summary of Chapter 3.- 4. Concepts to explain simplex cycling.- 4.1. Specification of the question.- 4.2 A pure graph theoretical approach.- 4.2.1 The concept of the LP-degeneracy graph.- 4.2.2 Characterization of simplex cycles by means of the LP-degeneracy graph.- 4.3 Geometrically motivated approaches.- 4.3.1 Fundamentals.- 4.3.2 Characterization of simplex cycles by means of the induced point set.- 4.3.3 Properties of the induced point set.- 4.3.4 Characterization of simplex cycles by means of the induced cone.- 4.4 A determinant approach.- 4.4.1 Terms and foundations.- 4.4.2 Characterization of simplex cycles by means of determinant inequality systems.- Summary of Chapter 4.- 5. Procedures for constructing cycling examples.- 5.1 On the practical use of constructed cycling examples.- 5.2 Successive procedures for constructing cycling examples.- 5.2.1 Modification of a row in the initial tableau.- 5.2.2 Modification of a column in the initial tableau.- 5.2.3 Addition of a column to the initial tableau.- 5.2.4 Addition of a row to the initial tableau.- 5.2.5 Combination of construction steps.- 22.214.171.124 Successive modification of rows.- 126.96.36.199 Successive addition of columns.- 5.2.6 Open questions in connection with the practical performance of the procedures.- 5.3 On the construction of general cycling examples.- Summary of Chapter 5.- A. Foundations of linear algebra and the theory of convex polytopes.- B. Foundations of graph theory.- C. Problems in the solution of determinant inequality systems.- References.
Series: Lecture Notes in Economic and Mathematical Systems
Number Of Pages: 196
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 24.41 x 16.99
Weight (kg): 0.35