| Article ID: | iaor2006955 |
| Country: | Canada |
| Volume: | 42 |
| Issue: | 2 |
| Start Page Number: | 107 |
| End Page Number: | 112 |
| Publication Date: | May 2004 |
| Journal: | INFOR |
| Authors: | Aneja Y.P., Sokkalingam P.T. |
| Keywords: | graphs, programming: integer |
Given a directed network G(N;A), the minimum feedback arc set problem is to find an optimal weighted subset of arcs A′ [is a subset of] A so that G(N;A\A′) is acyclic. We first provide a mixed 0–1 integer programming formulation whose LP relaxation can be solved by a strongly polynomial algorithm of complexity 0([the absolute of N] cubed log [the absolute value of N]. An enumerative framework is provided which makes use of this relaxation repeatedly. We also provide a result which gives rise to a heuristic algorithm.