1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | /* SONET problem in B-Prolog. From the ESSENCE' model in the Minion Translator examples: http://www.cs.st-andrews.ac.uk/~andrea/examples/sonet/sonet_problem.eprime "" " The SONET problem is a network design problem: set up a network between n nodes, where only certain nodes require a connection. Nodes are connected by putting them on a ring, where all nodes on a ring can communicate. Putting a node on a ring requires a so-called ADM, and each ring has a capacity of nodes, i.e. ADMs. There is a certain amount of rings, r, that is available. The objective is to set up a network by using a minimal amount of ADMs. About the problem model The problem model has the amount of rings ( 'r' ), amount of nodes( 'n' ), the 'demand' (which nodes require communication) and node-capacity of each ring ( 'capacity_nodes' ) as parameters. The assignement of nodes to rings is modelled by a 2-dimensional matrix 'rings' , indexed by the amnount of rings and nodes. The matrix-domain is boolean: If the node in column j is assigned to the ring in row i, then rings[i,j] = 1 and 0 otherwise. So all the '1' s in the matrix 'rings' stand for an ADM. Hence the objective is to minimise the sum over all columns and rows of matrix 'rings' . "" " Model created by Hakan Kjellerstrand, hakank @gmail .com */ % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ go :- R = 4, N = 5, Demand = [[0,1,0,1,0], [1,0,1,0,0], [0,1,0,0,1], [1,0,0,0,0], [0,0,1,0,0]], CapacityNodes = [3,2,2,1], % decision variables matrix(Rings,[R,N]), term_variables(Rings,Vars), Vars :: 0..1, % to optimize Z #= sum([(Rings[Ring,Client]) : Ring in 1..R, Client in 1..N]), % if there is a demand between 2 nodes, then there has to exist % a ring, on which they are both installed foreach (Client1 in 1..N, Client2 in Client1+1..N, [Ring,R1,R2], ( Demand[Client1,Client2] =:= 1 -> matrix_element(Rings,Ring,Client1,R1), matrix_element(Rings,Ring,Client2,R2), R1 + R2 #>= 2 ; true ) ), % original comment: % capacity of each ring must not be exceeded foreach (Ring in 1..R, sum([Rings[Ring,Client] : Client in 1..N]) #=< CapacityNodes[Ring] ), % Z #= 7, % for showing all 6 optimal solutions minof(labeling(Vars),Z), % labeling(Vars), writeln(z:Z), foreach (RR in Rings, writeln(RR)), nl. matrix_element(X, I, J, Val) :- nth1(I, X, Row), element(J, Row, Val). matrix(_, []) :- !. matrix(L, [Dim|Dims]) :- length (L, Dim), foreach (X in L, matrix(X, Dims)). |