A Message Passing Algorithm for the Minimum Cost Multicut Problem
Paul Swoboda and Björn Andres

arXiv:1612.05441v2 [cs.DS] 12 Jan 2017

Abstract

problem have been proposed. They are grouped below into
three categories: primal feasible local search algorithms,
linear programming algorithms and fusion algorithms.

We propose a dual decomposition and linear program
relaxation of the NP-hard minimum cost multicut problem.
Unlike other polyhedral relaxations of the multicut polytope,
it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened
efficiently by cutting planes. We define an algorithm that
alternates between message passing and efficient separation
of cycle- and odd-wheel inequalities. This algorithm is more
efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework
of leading commercial software, as we show in experiments
with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.

Primal feasible local search algorithms [35, 31, 20, 18,
19] attempt to improve an initial feasible solution by means
of local transformations from a set that can be indexed or
searched efficiently. Local search algorithms are practical
for large instances, as the cost of all operations is small
compared to the cost of solving the entire problem at once.
On the downside, the feasible solution that is output typically
depends on the initialization. And even if a solution is found,
optimality is not certified, as no lower bound is computed.
Linear programming algorithms [24, 25, 27, 32, 38] operate on an outer polyhedral relaxation of the feasible set.
Their output is independent of their initialization and provides a lower bound. This lower bound can be used directly
inside a branch-and-bound search for certified optimal solutions. Alternatively, the LP relaxation can be tightened
by cutting planes. Several classes of planes are known that
define a facet of the multicut polytope and can be separated
efficiently [14]. On the downside, algorithms for general
LPs that are agnostic to the structure of the multicut problem
scale super-linearly with the size of the instance.

1. Introduction
Decomposing a graph into meaningful clusters is a fundamental primitive in computer vision, biomedical image
analysis and data mining. In settings where no information is
given about the number or size of clusters, and information
is given only about the pairwise similarity or dissimilarity of
nodes, a canonical mathematical abstraction is the minimum
cost multicut (or correlation clustering) problem [14]. The
feasible solutions of this problem, multicuts, relate one-toone to the decompositions of the graph. A multicut is the set
of edges that straddle distinct clusters. The cost of a multicut
is the sum of costs attributed to its edges.
In the field of computer vision, the minimum cost multicut problem has been applied in [3, 4, 39, 6] to the task of
unsupervised image segmentation defined by the BSDS data
sets and benchmarks [30] . In the field of biomedical image
analysis, the minimum cost multicut problem has been applied to an image segmentation task for connectomics [5]. In
the field of data mining, applications include [7, 33, 12, 13].
As the minimum cost multicut problem is NP-hard [9, 16],
even for planar graphs [8] large and complex instances with
millions of edges, especially those for connectomics, pose a
challenge for existing algorithms.
Related Work. Due to the importance of multicuts for
applications, many algorithms for the minimum cost multicut

Fusion algorithms attempt to combine feasible solutions
of subproblems obtained by combinatorial or random procedures into successively better multicuts. The fusion process
can either rely on column generation [39], binary quadratic
programming [11] or any algorithm for solving integer
LPs [10]. In particular, [39] provides dual lower bounds
but is restricted to planar graphs. [11, 10] explore the primal solution space in a clever way, but do not output dual
information.
Outline. Below, a discussion of preliminaries (Sec. 2) is
followed by the definition of our proposed decomposition
(Sec. 3) and algorithm (Sec. 4) for the minimum cost multicut
problem. Our approach combines the efficiency of local
search with the lower bounds of LPs and the subproblems
of fusion, as we show in experiments with large and diverse
instances of the problem (Sec. 5). All code and data will be
made publicly available upon acceptance of the paper.
1

v1

v1

v2

v5

v2

v3

2.1. Minimum Cost Multicut Problem
A decomposition (or clustering) of a graph G = (V, E) is
a partition V1 ∪˙ . . .∪Vk of the node set V such that Vi ∩Vj =
∅ ∀i 6= j and every cluster Vi , i = 1, . . . , k is connected.
The multicut induced by a decomposition is the subset of
those edges that straddle distinct clusters (cf. Fig. 1). Such
edges are said to be cut. Every multicut induced by any
decomposition of G is called a multicut of G. We denote by
MG the set of all multicuts of G.
Given, for every edge e ∈ E, a cost ce ∈ R of this
edge being cut, the instance of the minimum cost multicut
problem w.r.t. these costs is the optimization problem (1)
whose feasible solutions are all multicuts of G. For any edge
{v, w} = e ∈ E, negative costs θe < 0 favour the nodes v
and w to be in distinct components. Positive costs θe > 0
favour these nodes to lie in the same component.
X
min
θe
(1)

k
X
i=1

x ∈ {0, 1}E

X

xe0

Figure 3. Odd Bicycle Wheel

xvi vi+1 −

k
X
i=1

xuvi ≤

k
2

with vk+1 := v1 . (5)

LP relaxations of the multicut problem can in principle be
solved with algorithms for general LPs which are available
in excellent software such as CPlex [2] and Gurobi [22].
However, these algorithms scale super-linearly with the size
of the problem and are hence impractical for large instances.
We define in Sec. 3 an LP relaxation of the multicut
problem in form of an IRPS-LP (Def. 1). IRPS-LPs are a
special case of dual decomposition [21]. In Def. 1, every
i ∈ V defines a subproblem, and every edge ij ∈ E defines
a dependency of subproblems. Def. 1 is more specific in that,
firstly, the subproblems are binary and, secondly, the linear
constraints (9) that describe the dependence of subproblems
are defined by 01-matrices that map 01-vectors to 01-vectors.
IRPS-LPs are amenable to efficient optimization by message
passing in the framework of [36].

e∈E

xe ≤

v4

2.2. Integer relaxed pairwise separable LPs

e∈M

subject to ∀C ∈ cycles(G) :

v3

For completeness, we note that other inqualities known
to further tighten the LP relaxation can be included in our
algorithm, e.g., the bicycle inequalities [14] defind on graphs
as in Fig. 3. We, however, do not consider inequalities other
than cycles and odd wheels in the algorithm we propose.

This problem is NP-hard [9, 16], even for planar
graphs [8]. Below, we recapitulate its formulation as a binary LP and then turn to LP relaxations: For any 01-labeling
x ∈ {0, 1}E of the edges of G, the subset x−1 (1) of those
edges labeled 1 is a multicut of G if and only if x satisfies
the system (3) of cycle inequalities [14]. Hence, (1) can be
stated equivalently in the form of the binary LP (2)–(4).
X
min
θ e xe
(2)
x∈RE

v4

k nodes all of which are connected to an additional node
u ∈ V that is not in the cycle and is called the center of
the k-wheel (cf. Fig. 2). For any odd number k ∈ N, any kwheel of G, the cycle C = (v1 v2 , . . . , vk v1 ) and the center
u of the k-wheel, every characteristic function x ∈ {0, 1}E
of a multicut x−1 (1) of G satisfies the odd wheel inequality

2. Preliminaries

M ∈MG

u1

Figure 2. Odd Wheel

Figure 1. Depicted above is a decomposition of a graph into three
components (green). The multicut induced by this decomposition
consists of the edges that straddle distinct components (red).

v5

u2

u

(3)

Definition 1 (IRPS-LP [36]). Let N ∈ N and let G = (V, E)
be a graph with V = {1, . . . , N }. For every j ∈ V, let
dj ∈ N, let Xj ⊆ {0, 1}dj , and let θj ∈ Rdj . Let Λ :=
conv(X1 ) × · · · × conv(XN ). For every {j, k} = e ∈ E, let
me ∈ N, A(j,k) ∈ {0, 1}me ×dj and A(k,j) ∈ {0, 1}me ×dk
such that

e0 ∈C\{e}

(4)

An LP relaxation is obtained by replacing the integrality
constraints (4) by x ∈ P with P ⊆ [0, 1]E . This results in
an outer relaxation of the multicut polytope, which is the
convex hull of the characteristic functions of all multicuts of
G. The LP relaxation obtained for P := [0, 1]E , i.e., with
only the cycle inequalities, will not in general be tight.
A tighter LP relaxation is obtained by enforing also the
odd wheel inequalities [14]. A k-wheel is a cycle in G with

∀x ∈ Xj :

∀x ∈ Xk :

A(j,k) x ∈ {0, 1}me
me

A(k,j) x ∈ {0, 1}

(6)
(7)

Then, the LP written below is called integer relaxed pairwise
2

v1

v1

v1
v1

v2

v5

v1

v1

v1
v5

u

v2

u
u

v3

v1

v2
u

u

u

v5

u

v4
v3

v3

v3

v4

v4

v4

Figure 5. Depicted above is a triangulation of the odd wheel from
Figure 2. It consists of the triangles uv1 v2 , uv1 v3 , uv1 v4 , uv1 v5
and the lollipop graphs (uv2 v3 , v1 ), (uv3 v4 , v1 ), (uv4 v5 , v1 ).

Figure 4. Depicted above is a triangulated cycle (black) covered by
three triangles (red, green and blue)

separable w.r.t. the graph G.
min
µ∈Λ

dj
XX

θjk µjk

feasible multicuts of the triangle times two for accounting
for the additional edge.

(8)

3.1. Dependencies

j∈V k=1

subject to ∀{j, k} ∈ E :

A(j,k) µj = A(k,j) µk

(9)

The dependency between triangle subproblems and edge
subproblems are expressed below in the form of a linear
system. It fits into thee form (9) of an IRPS-LP.

3. Dual Decomposition
A straight-forward decomposition of the minimum cost
multicut problem (2)–(4) in the form of an IRPS-LP (Def. 1)
consists of one subproblem for every edge, one subproblem
for every cycle inequality and one subproblem for every oddwheel inequality. From a computational perspective, it is
however advantageous to triangulate cycles and odd wheels,
and to consider the resulting smaller subproblems. Below,
three classes of subproblems are defined rigorously.

µuv = µuvw (1, 1, 0) + µuvw (1, 0, 1) + µuvw (1, 1, 1)
µuw = µuvw (1, 1, 0) + µuvw (0, 1, 1) + µuvw (1, 1, 1)
µvw = µuvw (1, 0, 1) + µuvw (0, 1, 1) + µuvw (1, 1, 1)
The dependency between a lollipop subproblem with edge
set L = {e1 , e2 , e3 , e4 } and a triangle subproblem with edge
set T = {e01 , e02 , e03 } is stated below as a linear system with
sums over edges not shared between L and T . This linear
system has the form (9) of an IRPS-LP.
X
X
∀xL∩T :
µL (xL∩T , xL\T ) =
µT (xT ∩L , xT \C )

Edge Subproblems. For every edge e ∈ E, we consider
a subproblem e ∈ V with the feasible set Xe := {0, 1},
encoding whether edge e is cut (1) or uncut (0).

xL\T

Triangle Subproblems For every cycle C
=
{v1 v2 , v2 v3 , . . . vk v1 } ⊆ E, we consider the triangles v1 v2 v3 to vk−1 vk v1 , as depicted in Fig. 4. If some edge
uv of a triangle Ci is not in E, we add it to E with cost
zero, i.e., we triangulate the cycle in G. For each triangle
uvw, we introduce a subproblem uvw ∈ V whose feasible
set consists of the five feasible multicuts of the triangle, i.e.,
Xuvw := {(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.

xT \L

3.2. Remarks
Remark 1. The triangulation of cycles can be understood
as the constructing of a junction tree [37] in such a way that
the minimum cost multicut problem over the cycle can be
solved by dynamic programming. The triangulation of cycles
can also be understood as a tightening of an outer polyhedral
relaxation of the multicut polytope: A cycle inequality (3)
defines a facet of the multicut polytope if and only if the
cycle is chordless [14]. By triangulating a cycle, we obtain
a set of minimal chordless cycles (triangles) whose cycle
inequalities together imply that of the entire cycle.
Remark 2. Technically, we would not have needed to
include triangle subproblems for odd wheels. Instead, we
could have introduced dependencies between lollipops directly in the form of an IRPS-LP. However, by introducing
triangle factors in addition and by expressing dependencies
between lollipops and triangles, we couple lollipop factors
from different odd wheels more tightly whenever they share
the same triangles.

Lollipop Subproblems For every odd number k ∈ N and
every k-wheel of G consisting of a center node u and cycle
nodes v1 , . . . , vk , we introduce two classes of subproblems.
For the 5-wheel depicted in Fig. 2, these subproblems are
depicted in Fig. 5.
For every j ∈ {2, . . . , k}, we add the triangle subproblem
uv1 vj ∈ V, as described in the previous section.
For every j ∈ {2, . . . , k − 1}, we add the subproblem
uvj vj+1 , v1 ∈ V for the lollipop graph that consists of the
triangle uvj vj+1 and the additional edge uv1 . The feasible
set Xuvw,s of a lollipop graph uvw, s has ten elements, five
3

4. Algorithm

Algorithm 1: Message passing for the multicut problem
Data: {i1 , . . . , ik } = V, (θi )i∈V , (A(j,i) , A(i,j) )ij∈E
for i = i1 , . . . , ik do
if i is an edge subproblem uv: then
Receive messages:
for w ∈ V : uvw ∈ T do
δ := minxuw ,xvw θuvw (1, xuw , xvw )
− minxuw ,xvw θuvw (0, xuw , xvw )
θuv += δ
∀xuw , xvw : θuvw (1, xuw , xvw ) -= δ
end
Send messages:
δ := |{w ∈ V : uvw ∈ T }|−1 θuv
θuv := 0
for w ∈ V : uvw ∈ T do
∀xuw , xvw : θuvw (1, xuw , xvw ) += δ
end
end
if i is a triangle subproblem uvw with edges C:
then
Receive messages:
for lollipops L with L ∩ C 6= ∅ do
δ(xL∩C ) := minxL\C θL (xL∩C , xL\C )
θC (xL∩C , xC\L ) += δ(xL∩C )
θL (xL∩C , xL\C ) += δ(xL∩C
end
Send messages:
α := |{L a lollipop : L ∩ C 6= ∅}|
for lollipops L with L ∩ C 6= ∅ do
δL (xL∩C ) :=
minxC\L θuvw (xL∩C , xC\L )
θL (xL∩C , xL\C ) += α1 δL (xL∩C )
end
for lollipops L with L ∩ C 6= ∅ do
θC (xL∩C , xC\L ) += α1 δL (xL∩C )
end
end
end

We now define an algorithm for the minimum cost multicut problem (2)–(4). This algorithm takes an instance of
the problem as input and alternates for a fixed number of
iterations between two main procedures.
The first procedure, defined in Sec. 4.1, solves an instance of a dual of the IRPS-LP relaxation defined in the
previous section. The output consists in a lower bound and
a re-parameterization of the instance of the minimum cost
multicut problem given as input. The second procedure tightens the IRPS-LP relaxation by adding subproblems for cycle
inequalities (3) and odd wheel inequalities (5) violated by
the current solution. Separation procedures for finding such
violated inequalities, more efficiently than in cutting plane
algorithms for the primal [24, 25, 27], are defined in Sec. 4.2.
To find feasible solutions of the instance of the minimum cost multicut problem given as input, we apply a
state-of-the-art local search algorithm on the computed reparameterizations, a procedure commonly referred to as
rounding (Sec. 4.3).

4.1. Message Passing
Like other algorithms based on dual decomposition, the
algorithm we propose does not solve the IRPS-LP directly,
in the primal domain, but optimizes a dual of (8)–(9). Specifically, it operates on a space of re-parametrizations of the
problem defined below: For any two dependent subproblems
jk ∈ E, we can change the costs θj and θk by an arbitrary
vector ∆ according to the update rules
θj0 := θj + A>
(j,k) ∆

(10)

θk0 := θk − A>
(k,j) ∆ .

(11)

We refer to any update of θ according to the rules (10)–(11)
as message passing. Message passing does not change the
cost of any primal feasible solution, as
hθj0 , µj i + hθk0 , µk i

>
= hθj + A>
(j,k) ∆, µj i + hθk − A(k,j) ∆, µk i

(12)

= hθj , µj i + hθk , µk i + h∆, A(j,k) µj − A(k,j) µk i (13)

(9)

= hθj , µj i + hθk , µk i .

L(θ). For the general IRPS-LP, a framework of algorithms
to achieve this goal is defined in [36]. For the minimum cost
multicut problem, we define and implement Alg. 1 within
this framework. The specifics of this algorithm for the minimum cost multicut problem are discussed below. General
properties of message passing for IRPS-LP s are discussed
in [36].

(14)

Message passing does, however, change the dual lower
bound L(θ) to (8) given by
X
L(θ) :=
min hθj , xj i .
(15)
j∈V

x∈Xi

The maximum of L(θ) over all costs obtainable by message passing is equal to the minimum of (8), by linear programming duality. We seek to alter the costs θ by means
of message passing so as to maximize the lower bound

Factor Order. Alg. 1 iterates through all edge and triangle
subproblems. The order is specified as follows: We assume
that a node order is given. With respect to this node order,
edges uv ∈ E are ordered lexicographically. For every
4

triangle and its edge set C = {e1 , e2 , e3 } ⊆ E with e1 <
e2 < e3 , we define the ordering constraint e1 < C < e3 .
For every lollipop graph and its edge set L = {e1 , e2 , e3 , e4 }
with e1 < e2 < e3 < e4 , we define the ordering constraint
e1 < L < e4 . The strict partial order defined by these
constraints is extended to a total order by topological sorting.

Algorithm 2: Separation of cycle inequalities (3)
Data: G = (V, E),  ≥ 0, θe ∈ R
l := 1
for uv ∈ E do
if θuv ≥  then
union(u, v)
end
end
for uv ∈ E do
if θuv ≤ − and find(u) = find(v) then
Cl := shortest-path(u, v, )
l := l + 1
end
end

Message Passing Description. When an edge subproblem uv ∈ E is visited, Alg. 1 receives messages from all
dependent triangle subproblems. Having received a message
from triangle uvw ∈ E, the costs θuvw satisfy the condition
min θuvw (0, xuw , xvw ) = min θuvw (1, xuw , xvw ) .

xuw ,xvw

xuw ,xvw

In other words, the cost of the triangle factor θuvw has no
preference for either xuv = 0 or xuv = 1. Sending messages
from θuv is analoguous: Having sent messages from uv, we
have θuv = 0, i.e., there is again no preference for either
xuv = 0 or xuv = 1.
When we visit a triangle subproblem uvw, we do the
analogous with all dependent lollipop subproblems: Once
messages have been received, lollipop subproblems have no
preference for incident edges. Once messages have been
sent, this holds true for the triangle subproblems.
Once Alg. 1 has visited all subproblems and terminates,
we reverse the order of subproblems and invoke Alg. 1 again.
This double call of Alg. 1 is repeated for a fixed number of
iterations that is a parameter of our algorithm.

4.2.1

Cycle Inequalities

We characterize those cycles whose subproblem increases
the dual lower bound L(θ) by at least .
Proposition 1. Let C = {e1 , . . . , ek } be a cycle with θe1 ≤
− and θel ≤  for l > 1. Then, the dual lower bound L(θ)
can be increased by  by including a triangulation of C.
In order to find such cycles, we apply Alg. 2. This algorithm first records in a disjoint set data structure whether
distinct nodes u, v ∈ V are connected via edges with weight
≥ . Then, it visits all edges e ∈ E with θe ≤ −. If the
endpoints of e are connected by a path along which all edges
have weight at least , it searches for a shortest such path by
means of breadth first search.
In the primal, finding a maximally violated cycle inequality (3) is more expensive, requiring, for every edge uv ∈ E,
the search for a uv-path with minimum cost x [14] by, e.g.,
Dijkstra’s algorithm.

4.2. Separation
Applying Alg. 1 with all cycles and all odd wheels of a
graph G is impractical, as the number of triangles for cycle
inequalities (3) is cubic, and the number of lollipop graphs
for odd wheels (5) is quartic in |E|. In order to arrive at
a practical algorithm, we take a cutting plane approach in
which we separate and add subproblems for violated cycle
and odd wheel inequalities periodically. Initially, V contains
only one element for every edge e ∈ E, and E is empty.
In the primal, given some fractional x ∈ [0, 1]E , it is common to look for maximally violated inequalities (3) and (5).
This is possible in polynomial time via shortest path computations [14, 17]. In our dual formulation, we have no primal
solution x to search for violated inequalities. Here, a suitable
criterion is to consider those additional triangle or lollipop
subproblems that necessarily increase the dual lower bound
L(θ) by some constant  > 0. Among these subproblems,
we choose those for which the increase is maximal and add
them to the graph (V, E). A similar dual cutting plane approach has shown to be useful for graphical models in [34].
As we discuss below, separation is more efficient in the dual
than in the primal.

4.2.2

Odd Wheel Inequalities

We characterize those odd wheels whose lollipop subproblem increases the lower bound L(θ) by at least .
Proposition 2. Let O an odd wheel with center node u and
cycle nodes v1 , . . . , vk . Adding the lollipop subproblems for
O increases L(θ) by at least  if the costs θuvi vi+1 of each
triangle uvi vi+1 are such that the minimal cost of any edge
labeling of the triangle cutting precisely one edge incident to
u is smaller by  than the minimal cost of any edge labeling
of the triangle cutting 0 or 2 edges incident to u. That is:
min

θuvi vi+1 (x) + 

min

θuvi vi+1 (x) .

{x: xuvi +xuvi+1 =1}

≤
5

{x: xuvi +xuvi+1 6=1}

(16)

Algorithm 3: Separation of odd wheel inequalities (5)
Data: Triangles uvw, costs θuvw ,  ≥ 0
l := 0
for u ∈ V do
G0 = (V 0 , E 0 ), V 0 = ∅, E 0 = ∅, Connect = ∅
for triangles uvw do
if (16) holds true then
V 0 := V 0 ∪ {v, v 0 , w, w0 }
E 0 := E 0 ∪ {vw0 , v 0 w}
union(v, v 0 )
union(w, w0 )
end
end
for v ∈ V 0 ∩ V do
if find(u) = find(v) then
P 0 := shortest-pathG0 (u, v, )
C = {uv ∈ E | uv 0 ∈ P 0 ∨ u0 v ∈ P 0 }
if C is a simple cycle in G then
Ol := {u, P }
l := l + 1
end
end
end
end

v10

v20

v30

v40

v50

v1

v2

v3

v4

v5

Figure 6. Depicted above is the bipartite graph G0 constructed by
Alg. 3 for separating the 5-wheel depicted in Fig. 2.

algorithm defined in [26], namely greedy additive edge contraction (GAEC), followed by Kernighan-Lin with joins
(KLj). GAEC computes a multicut by greedily contracting
those edges for which the join decreases the cost maximally.
It stops as soon as no contraction of any edge strictly decreases the cost. KLj attempts to improve a given multicut
recursively by applying transformations from three classes:
(1) moving nodes between two components, (2) moving
nodes from a given component to a newly forming one or
(3) joining two components. GAEC and KLj are local search
algorithms that output a feasible multicut that need not be
optimal.
We apply GAEC and KLj not only to the instance of the
minimum cost multicut problem given as input but also to
the re-parameterization of this instance output by Alg. 1.
The rationale for doing so comes from LP duality:
Proposition 3. Assume θ maximizes the dual lower bound
L(θ) and the relaxation is tight, i.e.

In order to find such odd wheels, we apply Alg. 3. This
algorithm builds on our observation that we need to look
only at triangles whose subproblem has already been added.
Hence, Alg. 3 visits each node u ∈ V and builds a bipartite
graph G0 = (V 0 , E 0 ) as follows. (An example is depicted in
Fig. 6 for a 5-wheel and (16) holding true for all triangles of
the wheel.) For each triangle uvk such that (16) holds true,
four nodes v, v 0 , k, k 0 ∈ V 0 are added to V 0 , two copies of
each original node. These are joined by edges uv 0 , u0 v ∈ E 0 .
If a path from u to u0 exists in G0 , we have found a violated
odd wheel inequality (5). As G0 is bipartite, a uu0 -path in
G0 corresponds to an odd cycle in G. As before, the search
for paths is accelerated by connectivity tests via a disjoint
set data structure and is carried out by breadth first search.
In the primal, finding a maximally violated odd wheel
inequality (5) entails the same construction of the bipartite
graph G0 for each node u ∈ V [17]. However, a shortest
path search w.r.t. edge costs 12 − xvw + 21 (xuv + xuw ) needs
to be carried out by Dijkstra’s algorithm instead of breadth
first search. Further complication in the primal comes from
the fact that a separation algorithm needs to visit all v ∈ V 0
in order to compute the shortest vv 0 -path in G0 .

L(θ) =

min

{x∈{0,1}E | x−1 (1)∈MG }

hθ, xi .

(17)

Moreover, let x̂ ∈ {0, 1}E such that x̂−1 (1) is an optimal
multicut of G. Then,
(
≤ 0 if x̂e = 1
θe
(18)
≥ 0, if x̂e = 0
Having run Alg. 1 for a while, we expect θ to fulfill the
sign condition of Prop. 3 approximately. Therefore, the sign
of θe will be a good hint of the edge e being cut. Thus,
informally, we expect local search algorithms operating on
the re-parameterized instance of the problem to yield better
feasible multicuts than local search algorithms operating on
the given instance.
For MAP-inference in discrete graphical models, it is
known from [28, 29] that primal rounding can be improved
greatly when applied to cost functions re-parameterized by
message passing.

5. Experiments

4.3. Rounding

Solvers We compare against several state of the art algorithms.
• The algorithm MC-ILP [25] is an efficient implementation of a cutting plane algorithm solving (2) using cycle

Our message passing Alg. 1 improves a dual lower bound
on (2), but does not provide a feasible solution of (2)–(4). In
order to obtain a feasible multicut, we apply a local search
6

inequalities (3) in a cutting plane fashion. CPlex [2] is
used to solve the underlying ILP problems. The integrality conditions in (4) are directly given to the solver.
According to [25] this is beneficial due to the excellent
branch and cut capabilities of CPlex [2].

network into subgroups based on affinity between individual persons.
• CREMI-{small|large} datasets were constructed as
part of the CREMI [1] challenge, which aims to reconstruct neural circuits of the adult fly brain. The images are
taken by electron microscopy. The -small instances are
cropped versions of the -large ones. To our knowledge,
the CREMI-large dataset contain the largest multicut
problems approached with LP-based methods.
The image-seg, knott-3d and modularity
clustering datasets were taken from the OpenGM
benchmark [23], while the CREMI datasets were kindly
provided by their authors and are not yet published.
The dataset consists of 100, 8, 8, 8, 8, 6, 3 and 3 instances,
in total 144. Dataset details can be found in Table 1.

• Cut, Glue & Cut [11], abbreviated as CGC, is a move
making algorithm using planar max-cut subproblems to
improve multicuts.
• Fusion moves for correlation clustering [10], abbreviated as CC-Fusion, fuses multicuts generated by various
proposal generator with the help of auxiliary multicut
problems, solved in turn by MC-ILP. We use randomized hierarchical clustering and randomized watersheds as
proposal generators, identified by the suffixes-RHC and
-RWS. We use parameters for the proposal generators as
recommended by the authors [10].

Evaluation We have set a timelimit of one hour for all
algorithms. In Table 1 results averaged over all instances in
specific datasets are reported. In Figure 7 primal solution energy and dual lower bound (where applicable) averaged over
all instances in specific datasets are drawn against runtime.
As can be seen from Table 1, except for dataset
CREMI-large, our solver MP-COW gives dual bounds
that are within 0.0045%, 1.9%, 0.0061%, 0.0068%,
0.0017%, 0.0007% and 0.0083% of the dual lower bound obtained by MC-ILP, which uses the advanced branch-and-cut
facilities CPlex [2] provides. For CREMI-large only our
solvers MP-C and MP-COW output dual lower bounds, as
MC-ILP did not finish a single iteration after one hour. As
can be seen from Fig. 7 our lower bound usually converges
faster than MC-ILP’s. We conjecture that MC-C and MPCOW inside a branch-and-bound solver can significantly
extend the reach of exact methods for the multicut problem.
Strangely, KL does not perform well on image-seg,
even though the lower bound we achieve with MPC and MP-COW are not far from the optimal lower
bounds computed by MC-ILP. On the other hand, MPC and MP-COW give much better dual and primal results for modularity-clustering early on. Generally, when compared to MC-ILP’s primal convergence, we give much lower values early on, and for
the large-scale datasets knott-3d-550, CREMI-small,
CREMI-large, MCI-ILP’s primal solutions are not useful
anymore.
Unlike MC-ILP, our reparametrized costs can be used to
improve heuristic primal algorithms. An example of this can
be seen in Fig. 8, where reparametrized costs improve KL’s
solutions.

• MP-C denotes Algorithm 1 when we only separate for
cycle inequalities (3) by Algorithm 2, while MP-COW
denotes that we additionally separate for odd wheel inequalities (5) by Algorithm 3. We search for triangles and
lollipops to add every 10th iteration.
• KL is the GAEC and KLj implementation [26] described
in Section 4.3 for computing multicuts. We let KL run
every 100th iteration of MP-C and MP-COW on the
current reparametrized edge costs.
MC-ILP, CGC and CC-Fusion are implemented as part of
the OpenGM suite [23]. Only MC-ILP and our solvers MPC and MP-COW generate dual lower bounds. CGC also
outputs dual lower bounds,
but these are equivalent to the
P
trivial lower bound e∈E min(0, θe ), where edge weights
θe are as given by the problem. It has been shown that CGC,
CC-Fusion and KL outperform other primal heuristics [10],
hence we do not compare to any other heuristic algorithm.
Also MC-ILP outperforms the LP-based solver [32], due
to the latter using the slower COIN-OR CLP [15] solver
internally, hence we exclude it from the comparison as well.
All solvers were run on a laptop computer with a i5-5200
CPU with 2.2 GHz and 8GB RAM.
Datasets We compare on 8 datasets of diverse origin.
• image-seg consists of images of the Berkeley segmentation dataset [30], presegmented with superpixels, for
which pairwise affinity values have been computed as
in [4].
• The knott-3d-{150|300|450|550} datasets
come from a neural circuit reconstruction problem of
tissue [5] with [150]3 , [300]3 , [450]3 and [900]3 voxels.
The data is presegmented into supervoxels.

Conclusion We have shown that LP-based methods are
feasible for solving large scale multicut problems on commodity hardware and one does not have to resort to heuristic

• modularity clustering aims to cluster a social
7

Dataset / Algorithm
#I
100
image-seg
#V
≤ 3764
#E
≤ 10970
#I
6
modularity
#V
≤ 115
clustering
#E
≤ 6555
#I
8
knott-3d-150
#V
≤ 972
#E
≤ 5656
#I
8
knott-3d-300
#V
≤ 5896
#E
≤ 36221
#I
8
knott-3d-450
#V
≤ 17074
#E
≤ 107060
#I
8
knott-3d-550
#V
≤ 31249
#E
≤ 195271
#I
3
CREMI-small
#V
≤ 35523
#E
≤ 235966
#I
3
CREMI-large
#V
≤ 623435
#E
≤ 4172314

MP-C
4730.66
4434.69
21.92
-0.49
-0.53
0.68
-4570.61
-4572.65
0.84
-27285.41
-27307.36
475.63
-78426.70
-78527.23
3649.05
-136439.78
-136814.88
3783.33
-213167.45
-213225.65
3645.51
-3886840.98
-3892753.21
3667.67

UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)
UB
LB
time(s)

MP-COW
4732.66
4434.71
41.35
-0.49
-0.53
0.80
-4570.26
-4571.97
3.81
-27285.15
-27304.64
747.81
-78426.70
-78523.89
3640.66
-136439.78
-136803.34
3745.76
-213167.45
-213225.67
3661.71
-3886840.98
-3893090.30
3806.33

CGC
4600.81
4129.70
0.14
-0.30
-0.79
0.15
-4220.66
-4855.18
0.04
-24864.59
-28901.58
2.73
-70865.27
-83272.85
31.56
-123841.47
-144703.64
102.42
-194616.60
-215473.98
319.01
†
†
†

MC-ILP
4434.91
4434.91
11.89
-0.44
-0.52
2911.10
-4571.69
-4571.69
2.37
-27302.78
-27302.78
227.33
-78391.32
-78522.51
1840.47
-135766.90
-136755.36
3683.22
-209594.49
-213208.94
2775.81
†
†
†

CC-Fusion-RWS
4447.06
‡
1.19
0.00
‡
0.00
-4534.76
‡
0.26
-27242.03
‡
2.96
-78386.14
‡
16.52
-136464.05
‡
72.94
-168905.17
‡
3543.61
-3772597.37
‡
5978.08

CC-Fusion-RHC
4436.33
‡
1.30
-0.44
‡
17.78
-4552.51
‡
0.53
-27247.29
‡
8.15
-78381.06
‡
119.23
-136395.89
‡
594.60
-213117.84
‡
2555.48
-3619190.20
‡
23139.40

Table 1. Primal solution energy (UB)/dual lower bound (LB)/runtime in seconds averaged over all instances of datasets. #I means number
of instances in dataset, #V and #E mean number of vertices and edges in multicut instances. † signifies method did not finish one iteration
after one hour, so was excluded from comparison. ‡ means method does not output dual lower bound. Bold numbers signify lowest primal
solution energy, highest lower bound, fastest runtime.
5,000
−0.35

−4,200

−2.71

−0.4

−4,400

−2.72

4,400

−0.45

−4,600

−2.73

4,200

−0.5

−4,800

−2.74

energy

4,800
4,600

10−2

10−1

100
runtime(s)
image-seg

101

102

·104

−0.55
10−3 10−2 10−1

0

1

2

10
10
10
10
runtime(s)
modularity clustering

−1.3

−5,000
10−3

3

10−2

10−1
runtime(s)
knott-3d-150

·105

·105

−1.4

100

101
runtime(s)
knott-3d-450

−1.45

102

100

101
runtime(s)
knott-3d-550

102

102

·106

−3.8

−2.14
10−1

100
101
runtime(s)
knott-3d-300

−3.6

−2.12

−8

10−1

−3.4

−2.1

−7.8

−2.75

−3.2

−2.08

−1.35

100

−3

−2.06

−7.6

energy

·104

−4,000

MP-C
MP-COW
CGC
MC-ILP
CC-Fusion-RWS
CC-Fusion-RHC

101

102
runtime(s)
CREMI-small

−4

101

102
103
runtime(s)
CREMI-large

Figure 7.
Averaged runtime plots for image-seg, modularity clustering, knott-3d-150, knott-3d-300,
knott-3d-450, knott-3d-550, CREMI-small and CREMI-large datasets. Continuous lines denote dual lower bounds and
dashed ones primal energies. Values are averaged over all instances of the dataset. The x-axis is logarithmic.
·104

primal algorithms. We achieve dual bounds very close to
those computed by state-of-the-art branch-and-cut solvers.
Additionally, our method usually gives much faster dual
bound convergence, resulting in superior solutions when terminated early. Also the primal heuristic GAEC + KLj can
be improved when run on costs as computed by our method.

−3.29

energy

−3.3
MPMC-C
MPMC-COW
CGC
MC-I
CC-Fusion-RWS
CC-Fusion-RHC

−3.31
−3.32
−3.33

100

101
102
runtime (s)

103

Figure 8.
Instance
gm_knott_3d_072
from
dataset
knott-3d-300 where
reparametrized
costs
improve KL’s solutions.

It remains an interesting task to integrate primal heuristics
more tightly into our message passing approach and further
improve the dual lower bound by e.g. embedding our solver
into branch and cut.
8

6. Acknowledgments
The authors would like to thank Vladimir Kolmogorov
for helpful discussions. This work is partially funded by the
European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant
agreement no 616160.

[14]
[15]
[16]

References
[1] CREMI MICCAI Challenge on circuit reconstruction from
Electron Microscopy Images. https://cremi.org.
[2] IBM ILOG CPLEX Optimizer. http://www-01.ibm.
com/software/integration/optimization/
cplex-optimizer/.
[3] A. Alush and J. Goldberger. Break and conquer: Efficient correlation clustering for image segmentation. In E. R. Hancock
and M. Pelillo, editors, SIMBAD, volume 7953 of Lecture
Notes in Computer Science, pages 134–147. Springer, 2013.
[4] B. Andres, J. H. Kappes, T. Beier, U. Köthe, and F. A. Hamprecht. Probabilistic image segmentation with closedness
constraints. In D. N. Metaxas, L. Quan, A. Sanfeliu, and
L. J. V. Gool, editors, ICCV, pages 2611–2618. IEEE Computer Society, 2011.
[5] B. Andres, T. Kröger, K. L. Briggman, W. Denk, N. Korogod,
G. Knott, U. Köthe, and F. A. Hamprecht. Globally optimal closed-surface segmentation for connectomics. In A. W.
Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid,
editors, ECCV (3), volume 7574 of Lecture Notes in Computer Science, pages 778–791. Springer, 2012.
[6] B. Andres, J. Yarkony, B. S. Manjunath, S. Kirchhoff,
E. Turetken, C. C. Fowlkes, and H. Pfister. Segmenting planar superpixel adjacency graphs w.r.t. non-planar superpixel
affinity graphs. Energy Minimization Methods in Computer
Vision and Pattern Recognition (EMMCVPR), 2013.
[7] A. Arasu, C. Ré, and D. Suciu. Large-scale deduplication with
constraints using dedupalog. In Y. E. Ioannidis, D. L. Lee,
and R. T. Ng, editors, ICDE, pages 952–963. IEEE Computer
Society, 2009.
[8] Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam. Optimal coalition structure generation in cooperative
graph games. In Proceedings of the Twenty-Seventh AAAI
Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA., 2013.
[9] N. Bansal, A. Blum, and S. Chawla. Correlation clustering.
Machine Learning, 56(1):89–113, 2004.
[10] T. Beier, F. A. Hamprecht, and J. H. Kappes. Fusion moves
for correlation clustering. In CVPR, pages 3507–3516. IEEE
Computer Society, 2015.
[11] T. Beier, T. Kröger, J. H. Kappes, U. Köthe, and F. A. Hamprecht. Cut, glue & cut: A fast, approximate solver for
multicut partitioning. In CVPR. Proceedings, 2014.
[12] Y. Chen, S. Sanghavi, and H. Xu. Clustering sparse graphs.
In P. L. Bartlett, F. C. N. Pereira, C. J. C. Burges, L. Bottou,
and K. Q. Weinberger, editors, NIPS, pages 2213–2221, 2012.
[13] F. Chierichetti, N. Dalvi, and R. Kumar. Correlation clustering
in mapreduce. In Proceedings of the 20th ACM SIGKDD

[17]

[18]

[19]

[20]
[21]

[22]
[23]

[24]

[25]

[26]

[27]

[28]

[29]

9

International Conference on Knowledge Discovery and Data
Mining, KDD ’14, pages 641–650, New York, NY, USA,
2014. ACM.
S. Chopra and M. R. Rao. The partition problem. Mathematical Programming, 59(1):87–115, 1993.
COIN-OR CLP, 2016. http://www.coin-or.org/
projects/Clp.xml.
E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theor. Comput.
Sci., 361(2):172–187, Sept. 2006.
M. M. Deza and M. Laurent. Geometry of Cuts and Metrics. Springer Publishing Company, Incorporated, 1st edition,
2009.
M. Elsner and E. Charniak. You talking to me? a corpus and
algorithm for conversation disentanglement. In K. McKeown,
J. D. Moore, S. Teufel, J. Allan, and S. Furui, editors, ACL,
pages 834–842. The Association for Computer Linguistics,
2008.
M. Elsner and W. Schudy. Bounding and comparing methods
for correlation clustering beyond ILP. In Proceedings of
the Workshop on Integer Linear Programming for Natural
Langauge Processing, ILP ’09, pages 19–27, Stroudsburg,
PA, USA, 2009. Association for Computational Linguistics.
A. Gionis, H. Mannila, and P. Tsaparas. Clustering aggregation. ACM Trans. Knowl. Discov. Data, 1(1):4, 2007.
M. Guignard and S. Kim. Lagrangean decomposition for integer programming: theory and applications. Revue française
d’automatique, d’informatique et de recherche opérationnelle.
Recherche opérationnelle, 21(4):307–323, 1987.
Gurobi Optimization, Inc., 2015. http://www.gurobi.
com.
J. H. Kappes, B. Andres, F. A. Hamprecht, C. Schnörr,
S. Nowozin, D. Batra, S. Kim, B. X. Kausler, T. Kröger,
J. Lellmann, N. Komodakis, B. Savchynskyy, and C. Rother.
A comparative study of modern inference techniques for structured discrete energy minimization problems. International
Journal of Computer Vision, 115(2):155–184, 2015.
J. H. Kappes, M. Speth, B. Andres, G. Reinelt, and C. Schnörr.
Globally optimal image partitioning by multicuts. In EMMCVPR. Springer, Springer, 2011.
J. H. Kappes, M. Speth, G. Reinelt, and C. Schnörr. Higherorder segmentation via multicuts. CoRR, abs/1305.6387,
2013.
M. Keuper, E. Levinkov, N. Bonneel, G. Lavoué, T. Brox,
and B. Andres. Efficient decomposition of image and mesh
graphs by lifted multicuts. In ICCV, 2015.
S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo. Higher-order
correlation clustering for image segmentation. In J. ShaweTaylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, and K. Q.
Weinberger, editors, NIPS, pages 1530–1538, 2011.
V. Kolmogorov. Convergent tree-reweighted message passing
for energy minimization. IEEE Trans. Pattern Anal. Mach.
Intell., 28(10):1568–1583, 2006.
V. Kolmogorov. A new look at reweighted message passing. IEEE Trans. Pattern Anal. Mach. Intell., 37(5):919–930,
2015.

[30] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database
of human segmented natural images and its application to
evaluating segmentation algorithms and measuring ecological
statistics. In Computer Vision, 2001. ICCV 2001. Proceedings.
Eighth IEEE International Conference on, volume 2, pages
416–423 vol.2, 2001.
[31] V. Ng and C. Cardie. Improving machine learning approaches
to coreference resolution. Proceedings of the 40th Annual
Meeting on Association for Computational Linguistics - ACL
’02, (July):104, 2001.
[32] S. Nowozin and S. Jegelka. Solution stability in linear programming relaxations: graph partitioning and unsupervised
learning. In A. P. Danyluk, L. Bottou, and M. L. Littman,
editors, ICML, volume 382 of ACM International Conference
Proceeding Series, pages 769–776. ACM, 2009.
[33] E. Sadikov, J. Madhavan, L. Wang, and A. Halevy. Clustering query refinements by user intent. In World Wide Web
Conference (WWW). ACM Press, April 2010.
[34] D. Sontag, D. K. Choe, and Y. Li. Efficiently searching for
frustrated cycles in MAP inference. In UAI, pages 795–804.
AUAI Press, 2012.
[35] W. M. Soon, H. T. Ng, and D. C. Y. Lim. A machine learning
approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544, 2001.
[36] P. Swoboda, J. Kuske, and B. Savchynskyy. A dual ascent
framework for Lagrangean decomposition of combinatorial
problems. CoRR, 2016.
[37] M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational inference. Foundations and
Trends in Machine Learning, 1(1-2):1–305, 2008.
[38] J. Yarkony, T. Beier, P. Baldi, and F. A. Hamprecht. Parallel multicut segmentation via dual decomposition. In New
Frontiers in Mining Complex Patterns - Third International
Workshop, NFMCP 2014, Held in Conjunction with ECMLPKDD 2014, Nancy, France, September 19, 2014, Revised
Selected Papers, pages 56–68, 2014.
[39] J. Yarkony, A. Ihler, and C. C. Fowlkes. Fast Planar Correlation Clustering for Image Segmentation, pages 568–581.
Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.

10

7. Apendix

Proof. Condition (16) means that in all triangles in the odd
wheel O, the minimal assignment with regard to the current
reparametrization, has exactl one edge incident to u. All
other assignment have cost greater by at least . As k is odd,
there is no possiblity to combine those local assignments to
a global assignment on O.
On the other hand, our construction of lollipop factors
ensures exactness on odd wheels. As at least one triangle
must then be assigned costs that are not locally optimal and
which is larger by  than its minimal reparametrized cost, the
result follows.

7.1. Proofs
Proof of Proposition 1
Proposition. Let C = {e1 , . . . , ek } be a cycle with θe1 ≤
− and θel ≥  for l > 1. Then, the dual lower bound L(θ)
can be increased by  by including a triangulation of C.
Proof. Let cycle C have vertices {v1 , . . . , vk } and assume that ei vi vi+1 with k + 1 = 1 for notational purposes. After triangulation, triangle factors on vertices
v1 v2 v3 , . . . v1 vk−1 vk will be present in the model. Let the
current reparametrization be θ.
The triangle factors corresponding to cycle C will enforce
the cycle inequality (3)
X

x e1 ≤

x ei .

Proof of Proposition 3
Proposition. Assume θ maximizes the dual lower bound
L(θ) and the relaxation is tight, i.e.
L(θ) =

(19)

i=1,...,k

k
X

min

xe1 ,...,xek ∈[0,1]

≤ − +

min

θ ei x ei

i=1

xe1 ,...,xek ∈[0,1]

≤+

k
X
i=1

 LC (θ)
θe1 ,...,θek

θv v v ,...,θv1 vk−1 vk
 1 2 3

a reparametrization

(20)

7.2. Detailed experimental evaluation



In Table 2 a detailed per instance evaluation of all algorithms considered in the experimental section can be found.

Pk
Pk−1
where LC (θ) = i=1 min(0, θei ) + i=2 min{θv1 vi vi+1 }
the dual lower bound on cycle C. The first inequality above
is due to either xe1 = 0 in the optimal solution or one
xe2 , . . . , xek being one due to (19). The second inequality is due to the fact that (i) maxθ a reparametrization L(θ) =
minµ∈Λ hθ, µi by linear programming duality and (ii) the
triangle factors enforce more inequalities than only (19).
Proof of Proposition 2
Proposition. Let O an odd wheel with center node u and
cycle nodes v1 , . . . , vk . Adding the lollipop subproblems for
O increases L(θ) by at least  if the costs θuvi vi+1 of each
triangle uvi vi+1 are such that the minimal cost of any edge
labeling of the triangle cutting precisely one edge incident to
u is smaller by  than the minimal cost of any edge labeling
of the triangle cutting 0 or 2 edges incident to u. That is:
min

θuvi vi+1 (x) + 

min

θuvi vi+1 (x) .

{x: xuvi +xuvi+1 =1}

≤

{x: xuvi +xuvi+1 6=1}

(22)

Proof. Follows from the complementary slackness conditions in linear programming duality.

θei xei s.t. (19)

max

hθ, xi .

Moreover, let x̂ ∈ {0, 1}E such that x̂−1 (1) is an optimal
multicut of G. Then,
(
≤ 0 if x̂e = 1
θe
(23)
≥ 0, if x̂e = 0

It holds that
− θ e1 =

min

{x∈{0,1}E | x−1 (1)∈MG }

(21)

11

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
MP-C

Instance

101087.bmp

102061.bmp

103070.bmp

105025.bmp

106024.bmp

108005.bmp

108070.bmp

108082.bmp

109053.bmp

119082.bmp

12084.bmp

123074.bmp

126007.bmp

130026.bmp

134035.bmp

14037.bmp

143090.bmp

145086.bmp

147091.bmp

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

2906.16
2788.69
0.31
3017.57
2932.80
3.26
4437.16
4196.88
11.84
6332.73
6045.21
33.75
1832.16
1597.07
0.64
6839.76
6567.48
4.58
9082.04
8414.64
28.23
5125.72
4786.46
6.85
4575.76
4412.45
20.74
4512.04
4526.91
0.10
7502.34
7276.26
3.48
4200.21
3829.51
35.27
2756.86
2677.02
0.23
6066.91
5331.00
36.91
6840.69
6562.20
8.44
1566.34
1375.55
0.09
1728.22
1712.44
0.43
3806.23
3319.36
0.32
4092.25
3968.35
1.50

MC-COW
CGC
image-seg
2906.16
2853.56
2788.95
2622.38
0.59
0.02
3017.57
3090.33
2933.39
2750.99
5.83
0.05
4444.27
4457.13
4196.94
3842.84
15.93
0.15
6333.88
6290.71
6046.08
5506.01
55.69
0.35
1832.16
1654.27
1597.21
1466.60
4.09
0.02
6841.08
6855.33
6569.63
6151.29
22.38
0.26
9083.42
8612.32
8414.99
7818.70
52.32
0.41
5127.99
5090.88
4789.19
4380.66
25.07
0.16
4579.97
4616.61
4413.08
4021.22
71.75
0.17
4512.04
4642.96
4526.91
4346.24
0.10
0.02
7502.34
7443.28
7277.38
6941.02
8.10
0.15
4204.24
4031.03
3829.04
3439.47
24.55
0.14
2760.64
2747.72
2677.08
2512.08
0.53
0.01
6066.91
5580.58
5336.93
4828.82
167.54
0.26
6840.69
6679.89
6565.03
6166.95
43.34
0.19
1582.13
1431.56
1375.55
1274.27
0.17
0.01
1728.22
1807.41
1712.26
1595.54
2.49
0.01
3808.75
3407.83
3319.34
3197.53
0.45
0.01
4092.25
4129.72
3970.58
3734.67
10.96
0.10

12

MC-ILP

CC-Fusion-RWS

CC-Fusion-RHC

2789.90
2789.90
5.11
2943.77
2943.77
8.75
4199.38
4199.38
6.97
6055.33
6055.33
32.15
1599.25
1599.25
4.76
6578.03
6578.03
10.86
8422.24
8422.24
26.67
4800.15
4800.15
13.51
4421.13
4421.13
9.64
4530.71
4530.71
0.48
7284.45
7284.45
2.47
3842.74
3842.74
23.01
2684.83
2684.83
0.79
5350.83
5350.83
19.66
6578.98
6578.98
28.82
1383.14
1383.14
0.25
1714.38
1714.38
0.56
3322.21
3322.21
0.83
3973.71
3973.71
13.24

2800.22
†
0.63
2963.42
†
0.61
4205.03
†
1.32
6070.84
†
1.91
1618.18
†
0.18
6584.62
†
2.49
8445.73
†
3.35
4815.78
†
1.20
4424.05
†
1.50
4535.85
†
1.53
7301.17
†
2.20
3856.82
†
0.47
2706.76
†
0.38
5369.95
†
0.99
6595.87
†
1.81
1393.66
†
0.13
1725.88
†
0.44
3329.14
†
0.41
3982.30
†
0.90

2789.90
†
0.81
2944.46
†
0.96
4200.64
†
0.98
6061.05
†
1.59
1599.83
†
0.25
6578.18
†
1.54
8424.36
†
1.75
4806.04
†
1.89
4421.13
†
0.84
4532.29
†
1.57
7287.68
†
3.99
3847.83
†
0.86
2685.26
†
0.82
5354.31
†
1.40
6579.62
†
1.33
1383.14
†
0.22
1715.76
†
0.34
3322.59
†
1.59
3975.15
†
0.83

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
Instance
148026.bmp

148089.bmp

156065.bmp

157055.bmp

159008.bmp

160068.bmp

16077.bmp

163085.bmp

167062.bmp

167083.bmp

170057.bmp

175032.bmp

175043.bmp

182053.bmp

189080.bmp

19021.bmp

196073.bmp

197017.bmp

208001.bmp

210088.bmp

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

MP-C
8411.55
8198.62
6.48
6680.96
6432.06
10.44
5798.42
5224.22
10.19
4797.86
4679.04
0.49
4688.87
4534.88
3.53
3263.91
3088.23
1.18
4440.51
4224.10
4.37
4493.17
4370.36
21.91
1623.20
1273.01
0.10
8979.42
8325.80
9.83
3602.31
3260.19
21.07
11863.40
11525.63
623.66
8022.65
7809.60
4.74
3700.96
3575.85
4.05
1152.76
1072.82
0.07
4717.39
4498.74
1.67
592.63
544.89
0.12
3207.33
2792.60
0.82
6533.30
6254.97
22.20
1954.78
1891.95
0.26

MC-COW
8411.55
8199.84
29.65
6682.82
6431.52
15.57
5801.59
5225.10
35.24
4798.32
4679.39
3.10
4694.40
4535.76
21.00
3265.02
3088.17
2.28
4443.05
4224.60
13.81
4493.17
4371.00
35.30
1623.20
1273.29
0.66
8979.42
8328.03
53.28
3602.31
3260.98
26.30
11863.40
11526.57
632.98
8033.50
7811.17
29.83
3700.96
3576.12
12.83
1155.19
1073.00
0.11
4718.32
4499.79
4.36
594.41
544.89
0.55
3207.33
2792.59
1.01
6533.30
6256.22
63.32
1956.20
1891.95
0.38

CGC
8436.70
7780.68
0.15
6666.83
6030.94
0.17
5429.45
4857.14
0.15
4768.87
4472.39
0.02
4814.85
4217.95
0.10
3264.31
2866.45
0.05
4408.62
3921.75
0.07
4577.62
3983.52
0.15
1281.48
1233.39
0.00
8545.37
7921.06
0.23
3355.95
2989.38
0.07
11926.00
10543.16
1.27
8224.34
7136.44
0.39
3714.59
3321.74
0.07
1095.38
972.41
0.00
4693.10
4178.50
0.08
572.73
508.04
0.00
2857.86
2663.98
0.01
6605.51
5773.37
0.25
2034.65
1726.75
0.02

13

MC-ILP
8205.98
8205.98
4.49
6439.58
6439.58
18.64
5234.15
5234.15
18.51
4685.17
4685.17
2.60
4540.87
4540.87
16.64
3089.32
3089.32
1.80
4227.88
4227.88
3.22
4381.13
4381.13
9.82
1273.72
1273.72
1.00
8331.63
8331.63
11.74
3266.17
3266.17
18.20
11542.63
11542.63
165.83
7816.92
7816.92
13.17
3579.24
3579.24
14.11
1077.47
1077.47
0.25
4515.08
4515.08
12.93
545.47
545.47
0.76
2798.77
2798.77
0.77
6272.68
6272.68
78.10
1895.44
1895.44
1.26

CC-Fusion-RWS
8226.20
†
3.10
6455.48
†
2.00
5248.18
†
1.49
4696.42
†
1.37
4569.12
†
0.83
3103.23
†
0.61
4236.46
†
1.18
4406.98
†
0.91
1275.87
†
0.11
8344.35
†
2.27
3273.20
†
0.53
11566.74
†
3.25
7844.49
†
4.30
3602.74
†
0.65
1086.93
†
0.11
4521.63
†
1.16
548.39
†
0.07
2801.34
†
0.38
6277.73
†
2.12
1901.54
†
0.49

CC-Fusion-RHC
8207.72
†
2.73
6440.33
†
1.53
5234.76
†
1.12
4685.17
†
1.48
4541.22
†
1.29
3089.32
†
1.07
4228.78
†
1.63
4384.59
†
1.30
1275.67
†
0.17
8331.90
†
1.80
3266.73
†
0.67
11547.67
†
3.98
7822.01
†
3.46
3582.99
†
0.92
1078.41
†
0.49
4515.27
†
1.41
545.47
†
0.24
2798.77
†
0.77
6275.37
†
1.69
1896.58
†
0.51

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
Instance
21077.bmp

216081.bmp

219090.bmp

220075.bmp

223061.bmp

227092.bmp

229036.bmp

236037.bmp

24077.bmp

241004.bmp

241048.bmp

253027.bmp

253055.bmp

260058.bmp

271035.bmp

285079.bmp

291000.bmp

295087.bmp

296007.bmp

296059.bmp

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

MP-C
3031.01
2944.67
1.42
4462.75
4155.98
0.34
2810.16
2499.72
0.16
3265.75
3110.83
0.16
6812.98
6565.07
89.00
2178.48
1986.49
13.93
6681.13
6115.98
4.32
9324.06
9047.32
62.98
4846.51
4760.74
3.06
1271.42
1056.38
0.18
4972.81
4719.03
4.69
6839.82
6603.97
18.42
1684.63
1497.70
0.30
1458.96
1082.23
0.03
3706.68
3613.78
0.65
6105.56
5603.39
9.30
10554.63
10199.14
13.41
4562.91
4288.00
3.71
2503.63
2290.91
0.32
2240.64
2039.19
0.57

MC-COW
3032.66
2944.60
3.86
4463.13
4156.01
0.60
2810.16
2499.93
0.55
3269.41
3111.22
1.46
6818.95
6566.44
248.06
2180.95
1986.11
26.75
6684.62
6116.08
12.41
9325.93
9048.52
166.69
4847.62
4760.88
5.78
1272.99
1056.34
0.92
4972.81
4719.99
26.23
6841.19
6604.66
49.86
1684.63
1497.78
0.99
1458.96
1082.23
0.05
3707.59
3614.44
3.19
6105.56
5603.74
28.78
10557.44
10200.78
44.85
4571.66
4287.83
12.35
2507.50
2290.91
0.63
2241.78
2039.18
0.99

CGC
3001.74
2793.10
0.01
4324.17
3952.38
0.03
2624.72
2379.46
0.02
3155.80
2939.67
0.01
6751.72
5983.87
0.34
2051.77
1816.59
0.03
6250.80
5729.80
0.09
9507.86
8261.54
0.75
4892.44
4531.31
0.03
1077.34
984.58
0.00
4945.52
4343.63
0.10
6950.82
6371.53
0.32
1549.84
1408.65
0.01
1091.96
1017.59
0.00
3875.99
3326.25
0.10
5773.41
5246.17
0.10
10401.10
9626.61
0.56
4509.08
3985.98
0.11
2384.77
2115.21
0.03
2160.60
1891.55
0.02

14

MC-ILP
2946.71
2946.71
4.60
4158.73
4158.73
1.37
2501.27
2501.27
0.14
3115.95
3115.95
0.38
6576.83
6576.83
37.60
1998.46
1998.46
4.25
6125.73
6125.73
4.83
9060.84
9060.84
20.14
4761.98
4761.98
5.10
1057.14
1057.14
0.15
4730.95
4730.95
17.26
6606.62
6606.62
7.39
1502.16
1502.16
1.31
1084.26
1084.26
0.18
3621.00
3621.00
12.45
5610.12
5610.12
26.96
10208.87
10208.87
39.32
4290.54
4290.54
6.34
2293.13
2293.13
0.34
2044.71
2044.71
1.14

CC-Fusion-RWS
2966.82
†
0.44
4176.92
†
1.13
2507.80
†
0.48
3124.04
†
0.75
6591.07
†
1.67
2001.58
†
0.37
6153.41
†
1.53
9071.82
†
5.02
4779.26
†
1.14
1060.90
†
0.13
4750.17
†
0.79
6614.15
†
2.90
1518.91
†
0.09
1085.01
†
0.10
3657.57
†
0.78
5640.22
†
1.30
10222.91
†
2.46
4299.90
†
1.43
2306.24
†
0.28
2045.98
†
0.27

CC-Fusion-RHC
2946.71
†
1.13
4158.73
†
1.08
2501.27
†
0.97
3115.95
†
1.65
6578.02
†
1.53
2001.19
†
0.34
6126.61
†
2.00
9060.84
†
4.38
4761.98
†
2.40
1057.42
†
0.26
4731.19
†
2.00
6606.62
†
2.36
1502.16
†
0.19
1084.26
†
0.15
3621.48
†
1.75
5612.68
†
2.02
10210.47
†
2.24
4291.66
†
1.83
2293.83
†
0.47
2044.71
†
0.24

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
Instance
299086.bmp

300091.bmp

302008.bmp

304034.bmp

304074.bmp

306005.bmp

3096.bmp

33039.bmp

351093.bmp

361010.bmp

37073.bmp

376043.bmp

38082.bmp

38092.bmp

385039.bmp

41033.bmp

41069.bmp

42012.bmp

42049.bmp

43074.bmp

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

MP-C
1570.66
1550.54
0.47
1839.69
1487.72
0.16
2616.47
2539.89
0.21
8090.64
7824.86
9.24
4490.66
3883.34
3.48
4683.24
4286.33
5.25
295.31
388.89
0.00
8286.04
8061.19
27.46
6152.76
6096.66
19.48
3500.13
3356.03
0.42
1991.36
1972.11
0.14
6549.11
5859.62
7.34
8324.62
8047.84
439.50
4501.49
4067.32
1.24
3995.35
3741.30
0.42
2585.71
1988.64
0.54
6685.12
5091.16
24.57
3561.54
3238.97
3.96
970.16
996.85
0.00
2864.46
2329.22
1.82

MC-COW
1570.84
1550.56
2.10
1839.69
1487.90
0.49
2616.47
2539.89
0.54
8090.64
7827.27
54.06
4497.86
3882.52
6.21
4690.02
4286.33
14.67
295.31
388.89
0.00
8286.04
8061.78
67.13
6155.04
6097.34
64.42
3503.88
3356.01
1.06
1991.36
1972.11
0.30
6557.74
5860.01
31.66
8324.62
8048.69
702.48
4511.20
4067.13
2.30
3995.35
3742.39
3.10
2585.71
1989.20
4.62
6685.12
5092.47
59.03
3561.54
3240.27
27.65
970.16
996.85
0.00
2871.95
2329.38
6.38

CGC
1650.07
1450.72
0.02
1508.08
1426.88
0.01
2583.88
2481.98
0.01
8159.63
7212.50
0.40
4138.04
3543.87
0.11
4497.63
4004.02
0.11
396.90
389.83
0.00
8555.09
7384.06
0.44
6342.60
5679.10
0.20
3459.05
3189.41
0.02
2044.68
1904.57
0.01
6054.26
5433.92
0.17
8492.54
7359.93
0.62
4213.16
3814.35
0.09
3876.12
3565.10
0.06
2050.50
1841.58
0.01
5182.46
4896.23
0.07
3524.18
3005.31
0.08
1098.96
997.53
0.00
2374.97
2166.88
0.03

15

MC-ILP
1557.24
1557.24
0.11
1495.10
1495.10
1.91
2543.23
2543.23
0.23
7835.47
7835.47
24.88
3891.88
3891.88
0.51
4290.25
4290.25
17.38
396.90
396.90
0.02
8069.67
8069.67
20.06
6105.28
6105.28
19.54
3361.02
3361.02
0.39
1975.00
1975.00
0.15
5863.83
5863.83
9.80
8060.34
8060.34
26.23
4071.86
4071.86
0.46
3745.53
3745.53
2.51
1994.24
1994.24
0.94
5110.96
5110.96
35.77
3248.70
3248.70
8.95
1069.22
1069.22
0.22
2332.83
2332.83
5.82

CC-Fusion-RWS
1561.49
†
0.29
1498.51
†
0.21
2557.22
†
0.17
7850.78
†
3.14
3897.33
†
0.83
4305.78
†
0.91
411.23
†
0.00
8082.04
†
3.61
6111.45
†
2.10
3368.12
†
0.91
1982.24
†
0.31
5872.57
†
1.32
8065.57
†
2.41
4085.14
†
0.91
3752.81
†
1.20
2001.06
†
0.28
5115.12
†
0.36
3252.28
†
0.59
1076.54
†
0.10
2340.46
†
0.32

CC-Fusion-RHC
1557.24
†
0.41
1495.10
†
0.16
2543.23
†
0.46
7836.49
†
2.05
3891.88
†
0.79
4290.25
†
0.98
396.90
†
0.06
8070.48
†
3.29
6107.08
†
2.30
3364.98
†
0.79
1975.00
†
0.49
5864.00
†
0.94
8066.62
†
2.49
4071.86
†
0.99
3745.53
†
0.81
1997.55
†
0.40
5122.63
†
0.54
3251.04
†
0.73
1069.22
†
0.31
2333.36
†
0.28

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
Instance
45096.bmp

54082.bmp

55073.bmp

58060.bmp

62096.bmp

65033.bmp

66053.bmp

69015.bmp

69020.bmp

69040.bmp

76053.bmp

78004.bmp

8023.bmp

85048.bmp

86000.bmp

86016.bmp

86068.bmp

87046.bmp

89072.bmp

97033.bmp

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

MP-C
1088.06
975.97
0.06
4075.17
3785.04
4.80
8445.42
7820.19
54.41
10196.99
9877.23
35.63
3915.47
3413.39
1.37
7766.31
7360.45
5.16
4871.59
4417.69
3.11
4378.98
4019.16
1.66
5828.19
5170.40
45.51
8240.10
7955.22
230.92
4625.92
4504.16
13.42
3394.42
3248.43
0.41
4385.74
4019.49
16.96
6056.07
5844.50
6.40
4628.18
4628.53
0.31
7930.26
6617.36
1.96
5870.65
5186.42
28.82
4641.36
4304.42
4.69
4096.15
3925.22
0.93
4594.50
4311.08
2.36

MC-COW
1092.36
975.97
0.12
4075.17
3785.94
36.47
8449.44
7822.05
159.67
10197.09
9878.45
155.56
3915.47
3412.83
5.87
7767.46
7360.57
15.77
4871.59
4418.10
7.20
4378.98
4019.52
4.08
5831.93
5170.63
84.91
8242.44
7958.22
371.04
4625.92
4505.47
35.32
3394.80
3248.75
1.67
4388.92
4019.76
56.59
6056.07
5845.08
18.79
4628.18
4628.53
0.33
7930.26
6617.46
5.10
5876.08
5185.40
75.20
4641.36
4305.38
9.11
4098.40
3925.52
3.41
4594.50
4312.65
9.46

CGC
1024.96
911.19
0.01
3914.51
3486.46
0.10
8179.32
7189.03
0.39
10133.69
9389.50
0.27
3485.31
3233.59
0.05
7647.20
6865.71
0.18
4522.25
4172.50
0.07
4183.41
3778.35
0.06
5527.82
4796.09
0.20
8255.62
7213.49
0.55
4823.04
4073.68
0.14
3380.61
3109.85
0.01
4108.08
3679.77
0.14
6186.51
5452.57
0.16
4769.21
4414.10
0.03
6654.84
6502.79
0.02
5289.20
4731.74
0.23
4470.22
3985.82
0.09
4159.28
3707.83
0.06
4583.48
3996.62
0.06

16

MC-ILP
977.78
977.78
0.10
3796.36
3796.36
5.80
7835.96
7835.96
13.66
9881.86
9881.86
20.02
3419.40
3419.40
5.70
7364.57
7364.57
11.87
4427.25
4427.25
4.29
4024.45
4024.45
6.14
5179.29
5179.29
12.34
7974.58
7974.58
31.49
4514.99
4514.99
18.85
3254.61
3254.61
2.70
4023.38
4023.38
32.67
5851.38
5851.38
8.07
4633.86
4633.86
4.90
6618.85
6618.85
2.62
5198.87
5198.87
9.72
4315.53
4315.53
11.52
3933.75
3933.75
3.69
4320.69
4320.69
1.62

CC-Fusion-RWS
1031.06
†
0.05
3806.52
†
0.43
7844.37
†
2.54
9891.88
†
4.15
3421.38
†
0.54
7372.11
†
2.04
4434.10
†
0.65
4032.54
†
1.00
5183.07
†
1.16
7994.72
†
2.16
4527.26
†
1.59
3271.58
†
0.34
4032.92
†
0.84
5863.69
†
2.03
4643.13
†
1.49
6619.75
†
0.36
5207.65
†
1.10
4321.55
†
1.14
3948.57
†
1.07
4336.56
†
0.83

CC-Fusion-RHC
977.78
†
0.25
3797.18
†
1.03
7838.99
†
1.67
9882.77
†
6.54
3420.03
†
0.56
7365.30
†
2.05
4427.25
†
0.80
4025.34
†
1.27
5179.29
†
0.97
7983.83
†
3.76
4516.03
†
1.21
3254.85
†
0.64
4026.67
†
0.60
5852.33
†
1.91
4633.96
†
1.76
6620.36
†
0.53
5205.68
†
0.60
4315.53
†
0.60
3934.47
†
1.00
4322.76
†
1.31

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
MP-C

Instance

adjnoun

dolphins

football

karate

lesmis

polbooks

gm_knott_3d_032

gm_knott_3d_033

gm_knott_3d_034

gm_knott_3d_035

gm_knott_3d_036

gm_knott_3d_037

gm_knott_3d_038

gm_knott_3d_039

gm_knott_3d_072

gm_knott_3d_073

gm_knott_3d_074

gm_knott_3d_075

gm_knott_3d_076

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-0.31
-0.46
1.10
-0.53
-0.55
0.24
-0.60
-0.62
1.99
-0.42
-0.43
0.03
-0.56
-0.57
0.18
-0.52
-0.56
0.86

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-5811.47
-5812.64
0.47
-2545.84
-2545.90
0.41
-4064.87
-4066.65
0.51
-4595.84
-4595.84
0.36
-5192.26
-5199.32
0.35
-4636.50
-4642.64
3.53
-4625.80
-4625.80
0.35
-5092.32
-5092.45
0.73

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-32986.39
-33006.26
1466.31
-25863.15
-25866.11
58.50
-25685.56
-25726.98
172.42
-30456.95
-30480.69
26.07
-27000.93
-27065.92
1456.89

MC-COW
CGC
modularity clustering
-0.31
-0.17
-0.46
-0.79
1.11
0.29
-0.53
-0.34
-0.55
-0.83
0.22
0.03
-0.60
-0.34
-0.62
-0.90
1.98
0.37
-0.42
-0.28
-0.43
-0.66
0.06
0.00
-0.56
-0.37
-0.57
-0.72
0.83
0.03
-0.52
-0.33
-0.56
-0.83
0.92
0.17
knott-3d-150
-5811.47
-5365.34
-5811.49
-6052.81
2.68
0.03
-2545.84
-2536.26
-2545.90
-3029.52
0.88
0.02
-4064.87
-3921.65
-4066.31
-4337.06
1.26
0.02
-4595.84
-4238.86
-4595.84
-4916.47
0.49
0.08
-5192.26
-4678.23
-5198.80
-5440.26
1.01
0.09
-4633.67
-4312.24
-4639.28
-4928.85
18.53
0.03
-4625.80
-4235.69
-4625.80
-4818.46
1.52
0.05
-5092.32
-4476.96
-5092.32
-5318.04
4.11
0.03
knott-3d-300
-32986.39
-29632.23
-33006.26
-34512.56
1574.69
4.60
-25863.15
-23433.69
-25863.69
-27464.92
81.89
3.24
-25685.03
-23513.94
-25723.03
-27196.88
229.99
1.19
-30455.38
-27294.35
-30478.37
-31854.88
46.55
2.89
-27000.93
-24789.93
-27060.80
-28550.56
2236.72
2.62

17

MC-ILP

CC-Fusion-RWS

CC-Fusion-RHC

0.00
-0.45
7288.07
-0.53
-0.53
44.61
-0.60
-0.60
71.91
-0.42
-0.42
0.40
-0.56
-0.56
3.77
-0.53
-0.54
10057.85

0.00
†
0.01
0.00
†
0.00
0.00
†
0.01
0.00
†
0.00
0.00
†
0.00
0.00
†
0.01

-0.29
†
92.48
-0.52
†
0.79
-0.49
†
7.63
-0.32
†
0.08
-0.50
†
0.72
-0.51
†
4.97

-5811.47
-5811.47
2.70
-2545.84
-2545.84
1.28
-4064.87
-4064.87
3.69
-4595.84
-4595.84
1.18
-5198.37
-5198.37
1.32
-4638.99
-4638.99
6.27
-4625.80
-4625.80
0.65
-5092.32
-5092.32
1.88

-5745.79
†
0.17
-2517.65
†
0.22
-3971.60
†
0.47
-4568.88
†
0.27
-5159.18
†
0.32
-4616.39
†
0.23
-4616.99
†
0.19
-5081.58
†
0.23

-5767.34
†
0.48
-2545.84
†
0.35
-3972.66
†
0.58
-4595.84
†
0.46
-5198.37
†
0.62
-4638.03
†
0.76
-4619.01
†
0.46
-5082.97
†
0.58

-32999.85
-32999.85
49.78
-25863.38
-25863.38
55.72
-25721.90
-25721.90
39.63
-30478.37
-30478.37
14.29
-27056.99
-27056.99
50.33

-32883.17
†
4.26
-25738.25
†
2.72
-25625.74
†
2.18
-30429.06
†
2.18
-27004.21
†
3.32

-32875.45
†
3.40
-25740.05
†
8.88
-25627.65
†
10.73
-30471.30
†
3.57
-27031.94
†
10.79

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

MP-C
-29482.24
-29482.55
170.01
-20206.78
-20217.62
350.20
-26601.32
-26612.76
104.62

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-89941.58
-89996.73
3643.00
-73473.47
-73516.42
3678.62
-86499.41
-86633.78
3648.34
-86177.37
-86320.89
3634.38
-76590.45
-76761.06
3628.67
-74508.29
-74544.89
3616.45
-66423.87
-66525.90
3680.72
-73799.17
-73918.13
3662.18

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-152854.11
-153124.66
3686.25
-135567.04
-135824.78
3657.02
-149545.82
-149831.75
3651.93
-149769.24
-150320.76
3647.68
-130577.35
-130910.50
4152.93
-123419.07
-123849.34
3860.97
-123467.39
-123720.59
3720.24
-126318.25
-126936.67
3889.64

Instance
gm_knott_3d_077

gm_knott_3d_078

gm_knott_3d_079

gm_knott_3d_096

gm_knott_3d_097

gm_knott_3d_098

gm_knott_3d_099

gm_knott_3d_100

gm_knott_3d_101

gm_knott_3d_102

gm_knott_3d_103

gm_knott_3d_112

gm_knott_3d_113

gm_knott_3d_114

gm_knott_3d_115

gm_knott_3d_116

gm_knott_3d_117

gm_knott_3d_118

gm_knott_3d_119

MC-COW
CGC
-29482.24
-27122.85
-29482.26
-31159.83
155.43
2.40
-20206.78
-19374.02
-20214.30
-22015.47
1193.95
1.56
-26601.32
-23755.71
-26608.39
-28457.54
463.29
3.37
knott-3d-450
-89941.58
-80280.68
-89996.38
-94633.08
3614.63
48.66
-73473.47
-67333.36
-73516.60
-78026.62
3674.28
26.83
-86499.41
-78396.23
-86632.24
-91051.86
3623.29
11.39
-86177.37
-78712.34
-86309.52
-91020.66
3639.38
34.96
-76590.45
-68324.61
-76758.81
-81763.95
3668.23
40.53
-74508.29
-66796.31
-74544.24
-79463.73
3620.81
33.62
-66423.87
-60651.60
-66524.32
-71160.72
3617.03
19.75
-73799.17
-66427.02
-73909.00
-79062.14
3667.64
36.71
knott-3d-550
-152854.11
-136448.39
-153124.66
-160981.94
3692.63
151.77
-135567.04
-122181.33
-135824.78
-144181.42
3650.21
105.96
-149545.82
-134889.26
-149831.31
-157228.92
3627.15
108.75
-149769.24
-135760.55
-150285.41
-158348.78
3746.48
111.32
-130577.35
-118822.35
-130894.84
-138934.59
3854.59
88.56
-123419.07
-112948.58
-123819.48
-131937.12
3778.57
90.49
-123467.39
-112812.30
-123709.54
-131313.86
3824.32
77.63
-126318.25
-116868.98
-126936.67
-134702.52
3792.14
84.92

18

MC-ILP
-29482.24
-29482.24
47.23
-20211.55
-20211.55
1451.04
-26607.98
-26607.98
110.62

CC-Fusion-RWS
-29476.76
†
4.12
-20189.82
†
2.44
-26589.21
†
2.46

CC-Fusion-RHC
-29481.33
†
10.59
-20157.27
†
10.97
-26593.33
†
6.24

-89959.41
-89959.41
1438.60
-73477.55
-73477.55
1075.22
-86593.97
-86593.97
1507.50
-85956.93
-86449.40
3732.50
-76699.37
-76699.37
1076.28
-74529.51
-74529.51
1149.05
-66482.68
-66482.68
907.64
-73431.17
-73988.21
3836.96

-89779.76
†
16.89
-73386.50
†
15.59
-86470.44
†
15.15
-86184.26
†
11.12
-76561.72
†
22.65
-74500.99
†
19.52
-66454.83
†
14.44
-73750.61
†
16.82

-89786.75
†
153.09
-73364.35
†
177.63
-86498.10
†
69.82
-86180.01
†
90.11
-76523.90
†
141.63
-74495.74
†
110.02
-66455.86
†
131.82
-73743.79
†
79.70

-153021.45
-153024.89
3716.74
-134820.65
-135924.12
3614.44
-149716.68
-149722.18
3614.56
-148726.82
-150325.94
3747.40
-130757.57
-130761.25
3688.88
-122646.08
-123810.61
3617.71
-122526.33
-123538.09
3777.86
-123919.61
-126935.77
3688.17

-152908.44
†
88.55
-135466.46
†
57.52
-149683.60
†
99.81
-149736.65
†
47.97
-130720.10
†
92.77
-123368.23
†
54.49
-123520.61
†
83.73
-126308.30
†
58.68

-152675.73
†
462.34
-135386.34
†
540.01
-149526.15
†
384.54
-149777.01
†
384.89
-130580.01
†
976.88
-123448.71
†
582.92
-123483.58
†
869.68
-126289.59
†
555.56

Table 2: Per instance evaluation of the considered eight datasets. UB means primal solution
energy, LB dual lower bound and runtime(s) the runtime in seconds. Bold numbers indicate
lowest primal energy, highest lower bound and smallest runtime. † means method not
applicable.
MP-C

Instance

gm_small_1

gm_small_2

gm_small_3

gm_large_1

gm_large_2

gm_large_3

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-301663.25
-301678.18
3638.89
-127448.90
-127545.97
3623.23
-210390.21
-210452.80
3674.40

UB
LB
runtime(s)
UB
LB
runtime(s)
UB
LB
runtime(s)

-5647807.76
-5648791.54
3672.44
-2368830.08
-2382103.57
3613.51
-3643885.09
-3648930.86
3717.06

MC-COW
CGC
CREMI-small
-301663.25
-278423.74
-301677.98
-302379.69
3686.59
56.18
-127448.90
-114182.56
-127545.60
-131075.52
3679.25
369.68
-210390.21
-191243.51
-210453.44
-212966.73
3619.29
531.16
CREMI-large
-5647807.76
0.00
-5648791.54
†
3629.77
0.00
-2368830.08
0.00
-2382103.57
†
4076.68
0.00
-3643885.09
0.00
-3648930.86
†
3712.53
0.00

19

MC-ILP

CC-Fusion-RWS

CC-Fusion-RHC

-301674.02
-301673.92
998.95
-116678.57
-127520.30
3722.33
-210430.88
-210432.60
3606.16

0.00
†
0.00
-127414.03
†
3607.92
-210396.31
†
3479.31

-301674.02
†
191.08
-127292.54
†
3752.86
-210386.96
†
3722.51

0.00
†
0.00
0.00
†
0.00
0.00
†
0.00

-5628646.55
0.00
3863.35
-1916548.20
0.00
8092.81
0.00
0.00
0.00

-5524856.64
0.00
10197.66
-1713523.77
0.00
36081.14
0.00
0.00
0.00

