×

Bounds on the number of vertices of perturbed polyhedra. (English) Zbl 0786.90034

Summary: Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.

MSC:

90C05 Linear programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Armand and C. Malivert, Determination of the efficient set in multiobjective linear programming, J. Optim. Theory Appl. 70 (1991) 467–489. · Zbl 0793.90064 · doi:10.1007/BF00941298
[2] D. Barnette, P. Kleinschmidt and C.W. Lee, An upper bound theorem for polytope pairs, Math. Oper. Res. 11 (1986) 451–464. · Zbl 0604.52001 · doi:10.1287/moor.11.3.451
[3] M.L. Balinski, An algorithm for finding all vertices of convex polyhedral sets, SIAM J. Appl. Math. 9 (1961) 72–88. · Zbl 0108.33203 · doi:10.1137/0109008
[4] A. Brondsted,An Introduction to Convex Polytopes (Springer, New York/Heidelberg/Berlin, 1983).
[5] A. Charnes, Optimality and degeneracy in linear programming, Econometrica 20 (1952) 160–170. · Zbl 0049.37903 · doi:10.2307/1907845
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[7] G.B. Dantzig, A. Orden and P. Wolfe, The generalized simplex algorithm for minimizing a linear form under linear inequality restraints (RAND Corporation Report, 1954) Pacific J. Math. 5 (1955) 183–195. · Zbl 0064.39402
[8] H.E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983) 381–402. · Zbl 0531.90064 · doi:10.1287/moor.8.3.381
[9] T. Gal, Determination of all neighbors of a degenerate extreme point in polytopes, Discussion Paper 17b, Fern Universität Hagen, Germany (1978).
[10] T. Gal, On the structure of the set bases of a degenerate point, J. Optim. Theory Appl. 45 (1985) 577–589. · Zbl 0542.90091 · doi:10.1007/BF00939135
[11] T. Gal, Degeneracy graphs – Theory and application. A state-of-the-art survey, Diskussionsbeitrag 142, Fern Universität Hagen, Germany (1989).
[12] T. Gal, Degeneracy problems in mathematical programming and degeneracy graphs, Orion 6 (1990) 3–36.
[13] T. Gal, Weakly redundant constraints and their impact on postoptimal analyses in LP, Diskussionsbeitrag 151, Fern Universität Hagen, Germany (1990).
[14] T. Gal and F. Geue, The use of the TNP-rule to solve various degeneracy problems, Diskussionsbeitrag 149a, Fern Universität Hagen, Germany (1990).
[15] T. Gal, H.-J. Kruse and P. Zörnig, Survey of solved and open problems in the degeneracy phenomenon, Math. Progr. 42 (1988) 125–133. · Zbl 0641.90049 · doi:10.1007/BF01589397
[16] D. Gale, How to solve linear inequalities, Amer. Math. Monthly 76 (1969) 589–599. · Zbl 0205.04604 · doi:10.2307/2316658
[17] B. Grünbaum,Convex Polytopes (Wiley, London/New York/Sidney, 1967).
[18] G. Hadley,Linear Programming (Addison-Wesley, MA, 1962).
[19] V. Klee, Polytopes pairs and their relationship to linear programming, Acta Math. 133 (1974) 1–25. · Zbl 0307.90042 · doi:10.1007/BF02392139
[20] H.-J. Kruse,Degeneracy Graphs and the Neighbourhood Problem, Lecture Notes in Economics and Mathematical Systems 260 (Springer, Berlin, 1986). · Zbl 0587.90062
[21] T.H. Mattheiss, An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Oper. Res. 21 (1973) 247–260. · Zbl 0265.90024 · doi:10.1287/opre.21.1.247
[22] T.H. Mattheiss and B.K. Schmidt, Computational results on an algorithm for finding all vertices of a polytope, Math. Progr. 18 (1980) 308–329. · Zbl 0433.90045 · doi:10.1007/BF01588326
[23] K.G. Murty, Faces of a polyhedron, Math. Progr. Study 24 (1985) 30–42. · Zbl 0591.90082
[24] M.R. Osborne and D.M. Ryan, On the solution of highly degenerate linear programmes, Math. Progr. 41 (1988) 385–392. · Zbl 0651.90045 · doi:10.1007/BF01580776
[25] R.T. Rockafellar,Convex Analysis (Princeton, NJ, 1972). · Zbl 0224.49003
[26] P. Wolfe, A technique for resolving degeneracy in linear programming, SIAM J. 11 (1963) 205–211. · Zbl 0127.36903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.