A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1% Cardinality-constrained Multi-cycle Problem (CCMCP)
2%
3% This problem appears as one of the main optimization problems modelling
4% kidney exchange. The problem consists of the prize-collecting assignment
5% problem and an addition constraint stipulating that each subtour in the graph
6% has a maximum length K. If K = 2 or K = infinity, the problem is
7% polynomially-solvable. Otherwise, it is NP-hard.
8%
9% Further details on the problem can be found in:
10% On the kidney exchange problem: cardinality constrained cycle and chain
11% problems on directed graphs: a survey of integer programming approaches.
12% Vicky Mak-Hau, J Comb Optim (2017) 33:35–59
13%
14% Edward Lam <edward.lam@monash.edu>
15% Vicky Mak-Hau <vicky.mak@deakin.edu.au>
16
17include "all_different.mzn";
18include "bin_packing.mzn";
19include "seq_precede_chain.mzn";
20
21int: V; % Number of vertices
22int: K; % Maximum length of each subtour
23
24set of int: VERTICES = 1..V; % Set of vertices
25array[VERTICES,VERTICES] of int: edge_weight; % Weight of each edge
26
27array[VERTICES] of var VERTICES: succ; % Successor variable indicating next vertex in the cycle
28array[VERTICES] of var VERTICES: cycle; % Index of a cycle
29
30int: obj_ub = sum(i in VERTICES)(max(j in VERTICES)(edge_weight[i,j]));
31var 0..obj_ub: objective; % Objective variable
32
33% Check
34constraint forall(i in VERTICES)(assert(edge_weight[i,i] == 0, "Loop must have zero cost"));
35
36% Path in a cycle
37constraint alldifferent(succ); % Out-degree of two
38constraint forall(i in VERTICES)(cycle[i] == cycle[succ[i]]); % Connectivity
39constraint forall(i in VERTICES, j in VERTICES where i != j)(edge_weight[i,j] < 0 -> succ[i] != j); % Disable infeasible edges
40
41% Maximum cycle length
42constraint bin_packing(K, cycle, [1 | i in VERTICES]);
43
44% Objective function
45constraint objective = sum(i in VERTICES)(edge_weight[i,succ[i]]);
46
47% Symmetry-breaking
48constraint symmetry_breaking_constraint(seq_precede_chain(cycle));
49
50% Search strategy
51solve
52 :: seq_search([
53 int_search(succ, first_fail, indomain_median, complete)
54 ])
55 maximize objective;
56
57% Output
58output [
59 "succ = array1d(1..\(V), \(succ));\n",
60 "cycle = array1d(1..\(V), \(cycle));\n",
61 "objective = \(objective);\n"
62];