A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%------------------------------------------------------------------------------%
2% Constrained Community Detection Problem
3%
4% The problem is to find communities in the graph with maximum modularity value
5% satisfying must-link and cannot-link constraints which indicate whether a
6% pair of vertices must assign to same or different communities.
7%------------------------------------------------------------------------------%
8% Includes
9
10% include "globals.mzn";
11include "global_cardinality_low_up.mzn";
12include "value_precede_chain.mzn";
13
14%------------------------------------------------------------------------------%
15% Input and Derived Parameters
16
17int:n;
18int:k;
19int:maxsize;
20%int:minsize;
21int: nML;
22int: nCL;
23set of int: must = 1..nML;
24set of int: cannot = 1..nCL;
25array[must,1..2] of int: ML;
26array[cannot,1..2] of int: CL;
27array[1..n,1..n] of int: W;
28array[1..n,1..n] of int: A;
29array[1..n] of int: deg;
30array[1..n] of set of 1..n: nbh =[ {j | j in 1..n where A[i,j] > 0} | i in 1..n];
31int: dum = sum(i in 1..n)(W[i,i]);
32
33%------------------------------------------------------------------------------%
34% Variables
35
36array[1..n] of var 1..k: x;
37var 1..k: kk = max(x);
38
39int: objub = 2*sum(i,j in 1..n where i < j)(W[i,j]) + dum;
40var 0..objub: objective;
41
42%------------------------------------------------------------------------------%
43% Constraints
44
45constraint value_precede_chain([i|i in 1..k], x);
46
47constraint forall(m in must)( x[ML[m,1]] = x[ML[m,2]] );
48
49constraint forall(c in cannot)( x[CL[c,1]] != x[CL[c,2]] );
50
51constraint
52 global_cardinality_low_up(
53 x,
54 [i | i in 1..k],
55 [0 | i in 1..k],
56 [n | i in 1..k]
57 );
58
59 % Objective
60 %
61constraint
62 objective = 2 * (
63 sum(i in 1..n)(
64 sum(j in 1..n where j < i)(
65 bool2int(x[i] = x[j]) * W[i,j]
66 )
67 )
68 ) + dum;
69
70%------------------------------------------------------------------------------%
71% Solve item and search
72
73solve
74 :: int_search(x,input_order,indomain_min, complete)
75 maximize objective;
76
77%------------------------------------------------------------------------------%
78% Output
79
80output [
81 "x = \(x);\n",
82% "kk = \(kk);\n",
83 "objective = \(objective);\n"
84];
85