Debian Codegraph @

tests/spec/examples/radiation.mzn

raw
1 /***
2 --- !Test
3 solvers: [gecode, chuffed]
4 expected: !Result
5 status: OPTIMAL_SOLUTION
6 solution: !Solution
7 Beamtime: 21
8 K: 7
9 N: [2, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
10 Q:
11 - - [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
12 - [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
13 - [0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
14 - [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
15 - [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
16 - - [1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
17 - [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
18 - [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
19 - [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20 - [2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
21 - - [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22 - [0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
23 - [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24 - [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
25 - [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26 - - [0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
27 - [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28 - [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
29 - [2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30 - [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
31 - - [0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
32 - [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
33 - [2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
34 - [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
35 - [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
36 objective: 175
37 --- !Test
38 solvers: [cbc]
39 check_against: [gecode]
40 expected: !Result
41 status: OPTIMAL_SOLUTION
42 solution: !Solution {}
43 ***/
44
45 %-----------------------------------------------------------------------------%
46 % Radiation problem, Minizinc version
47 %
48 % Sebastian Brand
49 % 05/2007
50 %-----------------------------------------------------------------------------%
51
52 %-----------------------------------------------------------------------------%
53 % Instances
54 %-----------------------------------------------------------------------------%
55
56 m = 5; % Rows
57 n = 5; % Columns
58
59 Intensity = [| % g5c
60 7, 2, 14, 8, 9 |
61 13, 4, 1, 2, 9 |
62 5, 12, 2, 11, 9 |
63 10, 2, 4, 9, 7 |
64 10, 2, 8, 11, 1 |];
65
66 %-----------------------------------------------------------------------------%
67 % Parameters
68 %-----------------------------------------------------------------------------%
69
70 int: m; % Rows
71 int: n; % Columns
72
73 set of int: Rows = 1..m;
74 set of int: Columns = 1..n;
75
76 % Intensity matrix
77 array[Rows, Columns] of int: Intensity;
78
79
80 set of int: BTimes = 1..Bt_max;
81
82 int: Bt_max = max(i in Rows, j in Columns) (Intensity[i,j]);
83 int: Ints_sum = sum(i in Rows, j in Columns) (Intensity[i,j]);
84
85 %-----------------------------------------------------------------------------%
86 % Variables
87 %-----------------------------------------------------------------------------%
88
89 % Total beam-on time
90 var 0..Ints_sum: Beamtime;
91
92 % Number of shape matrices
93 var 0..m*n: K;
94
95 % N[b] is the number of shape matrices with associated beam-on time b
96 array[BTimes] of var 0..m*n: N;
97
98 % Q[i,j,b] is the number of shape matrices with associated beam-on time
99 % b that expose cell (i,j)
100 array[Rows, Columns, BTimes] of var 0..m*n: Q;
101 %-----------------------------------------------------------------------------%
102 % Constraints
103 %-----------------------------------------------------------------------------%
104
105 % For FD/LP hybrid solving, all these should go the LP solver
106 % (with a suitable linearisation of the 'max' expressions).
107 constraint
108 Beamtime = sum(b in BTimes) (b * N[b])
109 /\
110 K = sum(b in BTimes) (N[b])
111 /\
112 forall(i in Rows, j in Columns)
113 ( Intensity[i,j] = sum([b * Q[i,j,b] | b in BTimes]) )
114 /\
115 forall(i in Rows, b in BTimes)
116 ( upper_bound_on_increments(N[b], [Q[i,j,b] | j in Columns]) );
117
118
119 predicate upper_bound_on_increments(var int: N_b, array[int] of var int: L) =
120 N_b >= L[1] + sum([ max(L[j] - L[j-1], 0) | j in 2..n ]);
121
122 %-----------------------------------------------------------------------------%
123 % Objective
124 %-----------------------------------------------------------------------------%
125
126 solve :: int_search(
127 [Beamtime] ++ N ++
128 [ Q[i,j,b] | i in Rows, j in Columns, b in BTimes ],
129 input_order, indomain_split, complete)
130 minimize (ub(K) + 1) * Beamtime + K;
131 % really: (Beamtime, K), i.e. in lexicographic order
132
133 %-----------------------------------------------------------------------------%
134
135 output ["radiation:\n",
136 "B / K = ", show(Beamtime), " / ", show(K), "\n",
137 % "N = ", show(N), "\n"
138 ];
139
140 %-----------------------------------------------------------------------------%
141 %-----------------------------------------------------------------------------%