A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%------------------------------------------------------------------------------%
2% Multi Dimensional Knapsack Problem
3%------------------------------------------------------------------------------%
4
5include "knapsack.mzn";
6
7%------------------------------------------------------------------------------%
8% Parameters
9
10int: N; % number of variables
11int: M; % number of constraints
12
13set of int: VRange = 1..N;
14set of int: CRange = 1..M;
15
16array[CRange,VRange] of int: a; % Weight of items per bin
17array[CRange] of int: b; % Sizes of bins
18array[VRange] of int: c; % Profit of items
19
20%------------------------------------------------------------------------------%
21% Ignored parameters
22
23int: z; % Normally the optimal value
24
25%------------------------------------------------------------------------------%
26% Variables
27
28array[VRange] of var 0..1: x; % Whether an item is packed
29array[CRange] of var 0..ub_array(b): bVar; % Total weight in a bin
30
31var 0..sum(c): objective;
32
33constraint objective = sum(i in VRange)(c[i] * x[i]); % Total profit
34
35%------------------------------------------------------------------------------%
36% Constraints
37
38 % Constraining the size of the bins
39 %
40constraint
41 forall(i in CRange)( bVar[i] >= 0 /\ bVar[i] <= b[i] );
42
43 % Knapsack constraints
44 %
45constraint
46 forall(i in CRange)(
47 knapsack([a[i,j] | j in VRange], c, x, bVar[i], z)
48 );
49
50%------------------------------------------------------------------------------%
51% Some integrety check for the (input) data
52
53constraint
54 forall(i in CRange,j in VRange)(
55 assert(a[i,j] >= 0, "negative values in a")
56 );
57constraint
58 forall(i in CRange)( assert(b[i] >= 0, "negative values in b") );
59constraint
60 forall(j in VRange)( assert(c[j] >= 0, "negative values in c") );
61constraint assert(z >= 0, "negative z");
62
63%------------------------------------------------------------------------------%
64% Search
65
66solve
67 :: int_search(x, input_order, indomain_max, complete)
68 maximize objective;
69
70%------------------------------------------------------------------------------%
71% Output
72
73output [
74 "x = ", show(x), ";\n",
75 "objective = ", show(objective), ";\n"
76];
77
78%------------------------------------------------------------------------------%