Degeneracy Graphs and Simplex Cycling

ISBN-13: 9783540545934 / Angielski / Miękka / 1991 / 196 str.

Peter Zörnig

Opis

Based on author's doctoral thesis submitted to the Fernuniversit'at Hagen (FRG).

Spis treści

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 ? × n-degeneracy graphs.- 3.2.1 Foundations of the theory of finite sets.- 3.2.2 Characterization of ? × n-degeneracy graphs.- 3.2.3 Properties of ? × n-degeneracy graphs.- 3.3. Theory of 2 × n-degeneracy graphs.- 3.3.1 Characterization of 2 × n-degeneracy graphs.- 3.3.2 Properties of 2 × 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.- 5.2.5.1 Successive modification of rows.- 5.2.5.2 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.