Acyclic subdigraphs and linear orderings: Polytopes, facets, and a cutting plane algorithm. (English) Zbl 0565.90044
Graphs and order. The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 217-264 (1985).
[For the entire collection see Zbl 0549.00002.]
The acyclic subdigraph problem (ASP) can be formulated as follows. Given a digraph D with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. This problem is NP-hard. This paper is a study of the ASP and the directly equivalent linear ordering problem (LOP) from a polyhedral point of view. Insights into the facet structure of polytopes associated with these problems lead to the formulation and implementation of a cutting plane algorithm for the LOP. This is followed by some numerical results obtained with a computer implementation of the algorithm. Then there is a short discussion of some open problems associated with these polyhedral results. To conclude, there is a comprehensive bibliography of the ASP.
The acyclic subdigraph problem (ASP) can be formulated as follows. Given a digraph D with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. This problem is NP-hard. This paper is a study of the ASP and the directly equivalent linear ordering problem (LOP) from a polyhedral point of view. Insights into the facet structure of polytopes associated with these problems lead to the formulation and implementation of a cutting plane algorithm for the LOP. This is followed by some numerical results obtained with a computer implementation of the algorithm. Then there is a short discussion of some open problems associated with these polyhedral results. To conclude, there is a comprehensive bibliography of the ASP.
Reviewer: P.Avery
MSC:
| 90C10 | Integer programming |
| 52Bxx | Polytopes and polyhedra |
| 05C20 | Directed graphs (digraphs), tournaments |
