1 | /* MFASP, Minimum Feedback Arc Set Problem */ |
---|

2 | |
---|

3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|

4 | |
---|

5 | /* The Minimum Feedback Arc Set Problem for a given directed graph |
---|

6 | G = (V, E), where V is a set of vertices and E is a set of arcs, is |
---|

7 | to find a minimal subset of arcs, which being removed from the graph |
---|

8 | make it acyclic. |
---|

9 | |
---|

10 | Reference: |
---|

11 | Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability: |
---|

12 | A guide to the theory of NP-completeness [Graph Theory, Covering and |
---|

13 | Partitioning, Minimum Feedback Arc Set, GT9]. */ |
---|

14 | |
---|

15 | param n, integer, >= 0; |
---|

16 | /* number of vertices */ |
---|

17 | |
---|

18 | set V, default 1..n; |
---|

19 | /* set of vertices */ |
---|

20 | |
---|

21 | set E, within V cross V, |
---|

22 | default setof{i in V, j in V: i <> j and Uniform(0,1) <= 0.15} (i,j); |
---|

23 | /* set of arcs */ |
---|

24 | |
---|

25 | printf "Graph has %d vertices and %d arcs\n", card(V), card(E); |
---|

26 | |
---|

27 | var x{(i,j) in E}, binary; |
---|

28 | /* x[i,j] = 1 means that (i->j) is a feedback arc */ |
---|

29 | |
---|

30 | /* It is known that a digraph G = (V, E) is acyclic if and only if its |
---|

31 | vertices can be assigned numbers from 1 to |V| in such a way that |
---|

32 | k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number |
---|

33 | assigned to vertex i. We may use this condition to require that the |
---|

34 | digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is |
---|

35 | acyclic. */ |
---|

36 | |
---|

37 | var k{i in V}, >= 1, <= card(V); |
---|

38 | /* k[i] is a number assigned to vertex i */ |
---|

39 | |
---|

40 | s.t. r{(i,j) in E}: k[j] - k[i] >= 1 - card(V) * x[i,j]; |
---|

41 | /* note that x[i,j] = 1 leads to a redundant constraint */ |
---|

42 | |
---|

43 | minimize obj: sum{(i,j) in E} x[i,j]; |
---|

44 | /* the objective is to minimize the cardinality of a subset of feedback |
---|

45 | arcs */ |
---|

46 | |
---|

47 | solve; |
---|

48 | |
---|

49 | printf "Minimum feedback arc set:\n"; |
---|

50 | printf{(i,j) in E: x[i,j]} "%d %d\n", i, j; |
---|

51 | |
---|

52 | data; |
---|

53 | |
---|

54 | /* The optimal solution is 3 */ |
---|

55 | |
---|

56 | param n := 15; |
---|

57 | |
---|

58 | set E := 1 2, 2 3, 3 4, 3 8, 4 9, 5 1, 6 5, 7 5, 8 6, 8 7, 8 9, 9 10, |
---|

59 | 10 11, 10 14, 11 15, 12 7, 12 8, 12 13, 13 8, 13 12, 13 14, |
---|

60 | 14 9, 15 14; |
---|

61 | |
---|

62 | end; |
---|