| 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 |
%-----------------------------------------------------------------------------% |