64 lines
1.6 KiB
MiniZinc
64 lines
1.6 KiB
MiniZinc
%----------------------------------------------------------%
|
|
% Rehan Abdul Aziz <raziz@student.unimelb.edu.au>
|
|
%
|
|
% Road construction problem.
|
|
%
|
|
%----------------------------------------------------------%
|
|
|
|
%input
|
|
int: n;
|
|
set of int: N = 1..n;
|
|
array[N,N] of int: distance;
|
|
array[N,N] of int: cost;
|
|
int: budget;
|
|
int: M = 1000000;
|
|
|
|
%decision variables
|
|
array[N,N,N] of var 0..M: sp;
|
|
array[N,N] of var bool: construct;
|
|
|
|
constraint forall (x in N) (
|
|
construct[x,x] = false
|
|
/\ forall (s in N) (sp[x,x,s] = 0)
|
|
);
|
|
|
|
constraint forall (x,y in N where x<y) (
|
|
let { var 0..1: c = bool2int(construct[x,y]) } in
|
|
sp[x,y,1] = distance[x,y]*c + M*(1 - c)
|
|
);
|
|
|
|
constraint forall (x,y in N where x < y) (
|
|
construct[y,x] = construct[x,y]
|
|
/\ forall(s in N) (sp[y,x,s] = sp[x,y,s])
|
|
);
|
|
|
|
constraint forall (x,y in N, s in 1..n-1 where x<y) (
|
|
sp[x,y,s+1] =
|
|
min(
|
|
[sp[x,y,s]] ++
|
|
[ sp[x,z,s] + if y<z then sp[y,z,s] else sp[z,y,s] endif
|
|
| z in N where x<z /\ y!=z]
|
|
)
|
|
);
|
|
|
|
constraint sum (x,y in N where x<y)
|
|
(cost[x,y] * bool2int(construct[x,y])) <= budget;
|
|
|
|
int: obj_min = sum(x, y in N where x < y)( lb(sp[x, y, n]) );
|
|
int: obj_max = sum(x, y in N where x < y)( ub(sp[x, y, n]) );
|
|
var obj_min..obj_max: objective;
|
|
|
|
constraint objective = sum (x,y in N where x<y) (sp[x,y,n]);
|
|
|
|
solve
|
|
:: seq_search([
|
|
bool_search([construct[x,y] | x,y in N], input_order, indomain_max, complete),
|
|
int_search([objective], input_order, indomain_min, complete)
|
|
])
|
|
minimize objective;
|
|
|
|
output [
|
|
"construct = array2d(", show(N), ", ", show(N), ", ", show(construct), ");\n",
|
|
"objective = ", show(objective), ";\n"
|
|
];
|