A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%----------------------------------------------------------%
2% Rehan Abdul Aziz <raziz@student.unimelb.edu.au>
3%
4% Road construction problem.
5%
6%----------------------------------------------------------%
7
8%input
9int: n;
10set of int: N = 1..n;
11array[N,N] of int: distance;
12array[N,N] of int: cost;
13int: budget;
14int: M = 1000000;
15
16%decision variables
17array[N,N,N] of var 0..M: sp;
18array[N,N] of var bool: construct;
19
20constraint forall (x in N) (
21 construct[x,x] = false
22/\ forall (s in N) (sp[x,x,s] = 0)
23);
24
25constraint forall (x,y in N where x<y) (
26 let { var 0..1: c = bool2int(construct[x,y]) } in
27 sp[x,y,1] = distance[x,y]*c + M*(1 - c)
28);
29
30constraint forall (x,y in N where x < y) (
31 construct[y,x] = construct[x,y]
32/\ forall(s in N) (sp[y,x,s] = sp[x,y,s])
33);
34
35constraint forall (x,y in N, s in 1..n-1 where x<y) (
36 sp[x,y,s+1] =
37 min(
38 [sp[x,y,s]] ++
39 [ sp[x,z,s] + if y<z then sp[y,z,s] else sp[z,y,s] endif
40 | z in N where x<z /\ y!=z]
41 )
42);
43
44constraint sum (x,y in N where x<y)
45 (cost[x,y] * bool2int(construct[x,y])) <= budget;
46
47int: obj_min = sum(x, y in N where x < y)( lb(sp[x, y, n]) );
48int: obj_max = sum(x, y in N where x < y)( ub(sp[x, y, n]) );
49var obj_min..obj_max: objective;
50
51constraint objective = sum (x,y in N where x<y) (sp[x,y,n]);
52
53solve
54 :: seq_search([
55 bool_search([construct[x,y] | x,y in N], input_order, indomain_max, complete),
56 int_search([objective], input_order, indomain_min, complete)
57 ])
58 minimize objective;
59
60output [
61 "construct = array2d(", show(N), ", ", show(N), ", ", show(construct), ");\n",
62 "objective = ", show(objective), ";\n"
63];