Enumerating extreme points of a highly degenerate polytope

Computers & Operations Research - Tập 21 - Trang 397-410 - 1994
T. Yamada1, J. Yoruzuya1, S. Kataoka1
1Department of Computer Science, The National Defence Academy, Yokosuka, Kanagawa 239, Japan

Tài liệu tham khảo

Ecker, 1978, Finding all efficient extreme points for multiple objective linear programs, Mathl Program., 14, 249, 10.1007/BF01588968 Malakooti, 1989, Identifying nondominated alternatives with partial information for multi-objective discrete and linear programming, IEEE Trans. syst. man and Cybernet., 19, 95, 10.1109/21.24535 Dauer, 1990, Solving multiple objective linear programs in objective space, Europ. J. ops Res., 46, 350, 10.1016/0377-2217(90)90010-9 Edelsbrunner, 1987 Motzkin, 1973, The double description method, Vol. 2 Balinski, 1961, An algorithm for finding all vertices of convex polyhedral sets, J. SIAM, 9, 72 Manas, 1968, Finding all vertices of a convex polyhedron, Numer. Math., 12, 226, 10.1007/BF02162916 Mattheis, 1973, An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Ops Res., 21, 247, 10.1287/opre.21.1.247 Burdet, 1974, Generating all the faces of a polyhedron, SIAM J. appl. Math., 26, 479, 10.1137/0126045 Greenberg, 1975, An algorithm for determining redundant inequalities and all solutions to polyhedra, Numer. Math., 24, 19, 10.1007/BF01437214 Dyer, 1977, An algorithm for determining all extreme points of a convex polytope, Mathl Program., 12, 81, 10.1007/BF01593771 Chvatal, 1983 Gal, 1985, On the structure of the set bases of a degenerate points, J. optimiz. theory Appl, 45, 577, 10.1007/BF00939135 Gal, 1992, A new pivoting rule for solving various degeneracy problems, Ops Res. Lett., 11, 23, 10.1016/0167-6377(92)90058-B Tarjan, 1973, Enumeration of the elementary circuits of a directed graphs, SIAM J. Comput., 2, 211, 10.1137/0202017 Berge, 1965