A branch and bound algorithm for the acyclic subgraph problem
- 31 December 1981
- journal article
- Published by Elsevier BV in European Journal of Operational Research
- Vol. 8 (4), 355-362
- https://doi.org/10.1016/0377-2217(81)90005-9
Abstract
A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.Keywords
This publication has 6 references indexed in Scilit:
- A Consistent Extension of Condorcet’s Election PrincipleSIAM Journal on Applied Mathematics, 1978
- Lagrangean relaxation for integer programmingPublished by Springer Science and Business Media LLC ,1974
- A branch and bound algorithm for maximum likelihood paired comparison rankingBiometrika, 1972
- Maximum likelihood paired comparison ranking by linear programmingBiometrika, 1969
- Zwei Algorithmen zur Lösung eines komplexen ReihenfolgeproblemsMathematical Methods of Operations Research, 1968
- Optimal and Suboptimal Algorithms for the Quadratic Assignment ProblemJournal of the Society for Industrial and Applied Mathematics, 1962