Download
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
 
  SONET problem in Comet.
 
 
  Translation of 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'.
  """
 
  Compare with the MiniZinc model http://www.hakank.org/minizinc/sonet_problem.mzn
 
 
  This Comet model was created by Hakan Kjellerstrand (hakank@gmail.com)
  Also, see my Comet page: http://www.hakank.org/comet/
 
 */
 
// Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
import cotfd;
int t0 = System.getCPUTime();
 
 
int r = 4;  // upper bound for amount of rings
int n = 5;  // amount of clients
 
// original comment:
// """
// we have double entries here because of the symmetric structure!
// """
int demand[1..n, 1..n] =
  [
   [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]
   ]
  ;
 
int capacity_nodes[1..r] = [3,2,2,1];
 
Solver<CP> m();
var<CP>{int} rings[1..r, 1..n](m, 0..1);
var<CP>{int} z(m,0..sum(i in 1..r) capacity_nodes[i]);
 
Integer num_solutions(0);
 
// explore<m> {
// exploreall<m> {
minimize<m> z subject to {
 
  m.post(z == sum(ring in 1..r, client in 1..n) rings[ring, client]);
 
  // m.post(z <= 7); // for exploreall
 
  // original comment:
  // """
  // capacity of each ring must not be exceeded    
  // """
  forall(ring in 1..r)
    m.post(sum(client in 1..n)
           (rings[ring, client]) <= capacity_nodes[ring] );
 
  // original comment:
  // """
  // if there is a demand between 2 nodes, then there has to exist
  // a ring, on which they are both installed
  // """
  forall(client1 in 1..n,client2 in 1..n : client1 < client2)
    if(demand[client1,client2] == 1) {
      // tryall<m>(ring in 1..r)
      // var<CP>{int} ring(m, 1..r); // another solution, but slower
      // m.post(rings[ring,client1] + rings[ring, client2] >= 2);
      // This was suggested by Pierre Schaus instead of the tryall thing.
      m.post(or(ring in 1..r) (rings[ring,client1] + rings[ring, client2] >= 2));
    }
   
  
 
} using {
       
  label(m);
 
  num_solutions := num_solutions + 1;
 
  cout << "z: " << z << endl;
  forall(i in 1..r) {
    forall(j in 1..n) {
      cout << rings[i,j] << " ";
    }
    cout << endl;
  }
  cout << endl;
   
 
}
 
 
cout << "\nnum_solutions: " << num_solutions << endl;
     
int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;