DLP 2014 - Symposium on Degeneracy in Linear Programming

Organizer: Dr. Peter Zörnig, Associate Professor, Institute of Exact Sciences, Department of Statistics, University of Brasília, Brazil
E-mail: peter-AT-unb.br
Though there exist alternative procedures to solve Linear Programming Problems, the simplex method due to G.B. Dantzig is still the most powerful and most well-known solution method which has been refined and expanded over several decades.
The principal obstacle causing diverse problems is the phenomenon of degeneracy, which occurs when several bases are associated with the same basic solution. Geometrically a degenerate basic solution corresponds to an “overdetermined” vertex of the feasible solution space.
Degeneracy problems are not restricted to general linear problems but also occur in adaptations of the simplex method to specific linear problems (e.g. network problems) or in other linearly restricted problems.
The degeneracy problem has diverse aspects which can be roughly subdivided into the following:
efficiency problems in the determination of the optimal solution: Cycling, neighborhood problem (occurs when all neighbors of a degenerate vertex have to be determined), efficiency loss caused by weak redundancy.
problems in post-optimal analysis: Sensitivity analysis under degeneracy (define properly and to interpret economically the critical region for which the optimal solution remains unchanged), determination of shadow prices
Theory of degeneracy graphs (unified approach to tackle the problem of degeneracy)
For the symposium, contributions to any of the above topics are invited.
Selected References
Gal, T.: Shadow prices and sensitivity analysis in linear programming under degeneracy: A state-of-the-art survey. Operations Research Spektrum, 8, 59-71,1986.
Gal, T., Kruse, H.-J. and Zörnig, Peter: Survey of solved and open problems in the degeneracy phenomenon, Mathematical Programming, 42, 125-133, 1988.
Guerrero-García, P. and Santos-Palomo, Á: On Hoffman´s celebrated cycling LP example, Computers & Operations Research, 34 (9), 2709-2717, 2007.
Ho, J. K.: Computing true shadow prices in Linear Programming, INFORMATICA , Vol. 11, No 4, 421-434 , 2000.
Kruse, H.-J.: Degeneracy graphs and the neighbourhood problem, Lecture Notes in Economics and Mathematical Systems, 260, Springer publisher, Berlin, New York,
1986.
Szwarc, W.: On cycling in the simplex method of the transportation problem, CORE, 2008.
Zörnig, Peter: Degeneracy graphs and simplex cycling, Lecture Notes in Economics and Mathematical Systems, 357, Springer publisher, Berlin, New York, 1991.
Zörnig, Peter: Systematic construction of examples for cycling of the simplex method. Computers and Operations Research, Elsevier, Netherlands, v. 33, n.8, p. 2247-
2262, 2006.
Zörnig, Peter: A note on cycling LP examples with permutation structure. Computers & Operations Research, Elsevier, Netherlands, 35, 994-1002, 2008.