Degeneracy Graphs and Simplex Cycling: 357 - Brossura

Zörnig, Peter

Brossura

ISBN 10: 354054593X ISBN 13: 9783540545934

Casa editrice: Springer Berlin Heidelberg, 1991

Riassunto

Many problems in economics can be formulated as linearlyconstrained mathematical optimization problems, where thefeasible 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 anoptimal 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 ofdegeneracy graphs is developed generally, which will serveas 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.

Su questo libro

Contenuti

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.

Product Description

Book by Zrnig Peter

Dettagli dell'edizione

• Editore: Springer Berlin Heidelberg
• Data di pubblicazione: 1991
• Lingua: Inglese
• ISBN 10: 354054593X
• ISBN 13: 9783540545934
• Rilegatura: Copertina flessibile
• Numero di pagine: 216
• Contatto del produttore: non disponibile
• Persona responsabile: CMN Printpool Inh. Mathis Neumann; https://www.also.com/ec/cms5/en_6000/6000/index.jsp; ; Friedrich-Karl-Str. 9; Hamburg; Germania