Graph Neural Networks with Triangle-Based Messages for the Multicut Problem Jannik Irmai1 , Lucas Fabian Naumann1 , and Bjoern Andres1,2 1
Faculty of Computer Science, TU Dresden Center for Scalable Data Analytics and AI, Dresden/Leipzig [email protected] [email protected] [email protected]
arXiv:2605.13673v1 [cs.LG] 13 May 2026
2
Abstract The multicut problem is an np-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constraints. In this article, we introduce such an adapted graph neural network architecture in which features are assigned only to edges, and the computation of messages is based on triangles in the underlying graph. Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.
1
Introduction
The multicut problem [Chopra and Rao, 1993] is a combinatorial optimization problem whose feasible solutions relate one-to-one to the clusterings of a graph. In particular, for any clustering, the corresponding multicut is the set of all edges that straddle distinct clusters. These edges are said to be cut by the multicut, the remaining edges are said to be joined. Given a graph with costs (real numbers) assigned to the edges, the goal of the multicut problem is to find a multicut such that the cost of the cut edges is minimized. The problem is equivalent to the correlation clustering problem [Bansal et al., 2004] and the clique partitioning problem [Grötschel and Wakabayashi, 1990], in the sense that they share optimal solutions. In prominent difference to other clustering formulations, the number of clusters is not fixed in advance, but inferred from the data. The multicut problem and its extensions are used in various fields such as bioinformatics [Wolny et al., 2020, Vergara et al., 2021], data mining [Shi et al., 2021, Kostyukhin et al., 2023] and computer vision [Tang et al., 2017, Nguyen et al., 2022]. Although the multicut problem is np-hard, there exist exact solvers that achieve feasible runtimes for relevant instances [Kappes et al., 2011, Andres et al., 2012, Letchford and Sørensen, 2024, Irmai and Andres, 2025]. For other instances where these are no longer feasible, a variety of heuristic solvers have been proposed that produce high-quality solutions empirically, but have no approximation guarantees [Beier et al., 2014, 2015, Keuper et al., 2015, Levinkov et al., 2017, Wolf et al., 2018, Abbas and Swoboda, 2022, 2023]. Since recently, graph neural networks (GNNs) [Scarselli et al., 2009] are used to solve combinatorial optimization problems, either directly [Selsam et al., 2019, Prates et al., 2019, Tönshoff et al., 2021], or by guiding existing solvers [Gasse et al., 2019, Labassi et al., 2022]. There are two approaches that focus specifically on heuristically solving the multicut problem [Jung and Keuper, 2023, Li et al., 2025]. Both use generic GNNs that primarily operate on node features, while the multicut problem is fundamentally edge-based.
1
k
k′
k
k′
i
j
i
j
hi = U mik + mik′ + mij
hij = U mijk + mijk′
Figure 1: Depicted on the left is an example of the standard message passing scheme. Each node i receives messages from its neighbors, which are aggregated to node features hi . Depicted on the right is an example of the triangle message passing scheme we propose. Each edge ij, receives messages from all triangles containing it (blue and green), which are aggregated to edge features hij .
In this article, we propose a GNN-based heuristic solver, where the GNN architecture is specifically adapted to the multicut problem. In particular, the architecture is based on the fact that each instance of the multicut problem w.r.t. a graph can be transformed to an equivalent instance on a complete graph [Chopra and Rao, 1993], for which the constraints that define feasible solutions are based exclusively on triangles. Utilizing this, the main building blocks of our GNN architecture are triangle message passing layers which operate only on edge features and compute messages based on triangles (see Figure 1). Thus, they directly capture the constraints of the problem. We use supervised learning to train our GNN to predict logits for edges being joined in an optimal solution. For inference, we construct a solution to the multicut problem by alternately applying our model and contracting the edge with the highest logit until all logits become non-positive. The edges in the remaining graph then correspond to a multicut of the original graph, which is returned as a solution. We evaluate our approach on random instances and instances from the CP-Lib benchmark [Sørensen and Letchford, 2024] with up to 200 nodes and demonstrate that it outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. Furthermore, we show that our model can find optimal solutions for specific instances in seconds, for which exact solvers require hours to find and certify optimality. The general idea of computing messages based on triangles is not novel in itself. It has been used for specific applications such as protein folding [Jumper et al., 2021] and neural algorithmic learning [Ibarz et al., 2022]. Furthermore, specific variants are formalized by simplicial [Bodnar et al., 2021] and hierarchical GNNs [Morris et al., 2019]. The triangle messages we propose here are different: Firstly, they are defined with respect to edge features only. Secondly, each edge receives messages only from those pairs of edges with which it forms a triangle. In particular, features or messages corresponding to nodes or structures like triangles and subgraphs are not considered. The experimental results demonstrate that, on small- and medium-sized instances, this adapted architecture and a simple supervised learning procedure are sufficient to outperform state-of-the-art heuristic solvers, and GNNs with standard architectures and more sophisticated training procedures.
2
Related Work
Exact Solvers: Branch-and-cut algorithms are the most commonly used exact solvers for the multicut problem. Although they have exponential worst-case time complexity, they can, depending on the cost structure, solve small- and medium-sized instances in feasible time [Kappes et al., 2011, Andres et al., 2012]. Branch-and-cut algorithms operate by solving linear programming (LP) relaxations, and adding cutting planes or branching on fractional variables to obtain an optimal integer solution. Although they are implemented by generic solvers, such as Gurobi [Gurobi Optimization, LLC, 2024] and CPLEX [IBM, 2022], they can be accelerated by adding problemspecific cutting planes, particularly those corresponding to facet-defining inequalities [Grötschel and Wakabayashi, 1989, Oosten et al., 2001, Sørensen, 2020, Letchford and Sørensen, 2024]. Recently,
2
Irmai and Andres [2025] implemented such a specialized branch-and-cut algorithm for the clique partitioning problem [Grötschel and Wakabayashi, 1990] using Gurobi as underlying LP solver. Their algorithm considers cutting planes for classes of inequalities that are not considered by any of the other solvers. It is also the most recent publicly available exact solver for the multicut (or clique partitioning) problem, we are aware of. Traditional Heuristic Solvers: Most heuristic multicut solvers are based on iteratively improving an initial solution through cost-reducing transformations. The Kernighan and Lin algorithm with joins [Keuper et al., 2015] searches locally for sequences of cost-reducing moves and joins. The greedy additive edge contraction (GAEC) algorithm [Keuper et al., 2015] contracts edges with the highest positive cost until all edge costs become non-positive. The greedy fixation algorithm [Levinkov et al., 2017] additionally fixes edges with large negative cost to be cut. The Mutex Watershed algorithm [Wolf et al., 2018] works similarly, but updates the costs after a contraction by taking the maximum rather than the sum. The Cut Glue & Cut algorithm [Beier et al., 2014] partitions and joins clusters of a given solution based on max-cut objectives. It is generalized by the fusion moves algorithm [Beier et al., 2015], which generates a proposal solution and fuses it with the current solution by solving the multicut problem instances obtained by contracting all edges joined in both solutions. Although the presented approaches can handle large instances infeasible for exact solvers, they perform transformations only sequentially and require storing the edge costs in memory, which are potentially quadratic in the number of nodes. For very large instances, where sequential processing is no longer feasible, Abbas and Swoboda [2022] introduce the rapid multicut algorithm. This primaldual, GPU-based algorithm simultaneously contracts edges and optionally uses message passing on a Lagrangian decomposition [Swoboda and Andres, 2017] to update edge costs. Furthermore, to reduce the space requirements, Abbas and Swoboda [2023] adapt the GAEC algorithm for instances whose costs are given as inner products of node features, such that only these node features must be stored. GNN-based Heuristic Solvers: Jung and Keuper [2023] train a GNN to predict the probability of edges being cut in an optimal solution to the multicut problem and round these to a feasible solution. The GNN is trained using supervised learning with a binary cross-entropy loss and an additional term that encourages the feasibility of the predicted solutions. Their approach is designed to solve large instances quickly, being significantly faster than traditional heuristic solvers like GAEC, at the cost of solution quality. Li et al. [2025] model the multicut problem as a Markov decision process, in which actions determine which edges to contract and states are learned by a GNN. After using Q-learning to obtain an edge selection policy, they apply this policy to iteratively contract edges. Their approach achieves high solution quality on the small- and medium-sized instances considered in their experiments, outperforming solvers like KL and GAEC. However, they train separate models for each test dataset and use ensemble inference, which increases both training and inference time. The approach, we present in this article combines elements of both works and introduces new ones. Similar to Jung and Keuper [2023], we train our GNN supervised to predict which edges to cut and join in an optimal solution. Similar to Li et al. [2025], we use an iterative inference procedure to contract edges in an autoregressive manner, and focus on obtaining high-quality solutions for smalland medium-sized instances. Different from both, we only operate on edge features and update them using triangle-based message passing layers, which we design specifically for the multicut problem.
3
−1 2 3
−4 1
−5 2
2 4 −1
Figure 2: Depicted above is an example of an instance of the multicut problem. The dotted edges form an optimal multicut with cost −6. The clustering induced by it is indicated by the shaded areas.
3
Preliminaries
3.1
Multicut Problem
Multicuts: Let G = (V, E) be a graph. A clustering of G is a partition Π of V such that for any U ∈ Π, any distinct i, j ∈ U are connected in G[U ]. A set of edges M ⊆ E is called a multicut of G if and only if there is a clustering Π of G such that M consists precisely of those edges that straddle distinct clusters of Π. Chopra and Rao [Chopra and Rao, 1993] show that there exists a one-to-one correspondence between the multicuts and the clusterings of a graph. In particular, φG (Π) = {ij ∈ E | ∀U ∈ Π : {i, j} ̸⊆ U } is a bijection from the clusterings to the multicuts of G. Problem Definition: Given a graph G = (V, E) with edge costs c ∈ RE , the multicut problem seeks a multicut that minimizes the cost of the cut edges (see Figure 2). It is formulated using binary variables x ∈ {0, 1}E , which indicate for every edge e ∈ E if it is cut, xe = 1, or joined, xe = 0: Definition 1. For any graph G = (V, E), any c ∈ RE and MCG := {x ∈ {0, 1}E | x−1 (1) is a multicut of G}, we call min{⟨c, x⟩ | x ∈ MCG } the instance of the multicut problem w.r.t. G and c. ⌟ The feasible solutions of the multicut problem, i.e. the characteristic vectors of multicuts, can be characterized by a system of linear inequalities w.r.t. to the chordless cycles of the underlying graph: Lemma 1 (Chopra and Rao 1993). For any graph G = (V, E) and any x ∈ {0, 1}E , x−1 (1) is a multicut of G if and only if X x e′ . ∀C ∈ chordless-cycles(G) ∀e ∈ C : xe ≤ (1) e′ ∈C\{e}
⌟ Graph Completion: The following lemma shows that, an instance of the multicut problem can be transformed into an equivalent instance on a complete graph by adding missing edges with cost 0. The chordless cycles of the resulting complete graph are precisely its triangles. Thus, the potentially exponential number of chordless cycle inequalities (1) reduces to 3 |V3 | -many triangle inequalities: Lemma 2 (Chopra and Rao 1993). Let G = (V, and let c ∈ RE . Let further E) be a′ graph V ′ ′ ′ E′ G = (V, E ) be the complete graph with E = 2 and let c ∈ R such that c′e = ce if e ∈ E and c′e = 0 otherwise. For any feasible solution x′ to the instance of the multicut problem w.r.t. G′ and c′ , the restriction x = x′ |E is a feasible solution to the instance w.r.t. G and c. Moreover, x′ is optimal if and only if x is optimal. ⌟ 4
Edge Contraction: Many heuristic solvers for the multicut problem are based on edge contractions [Beier et al., 2015, Keuper et al., 2015, Abbas and Swoboda, 2022, 2023, Li et al., 2025]. In particular, these solvers iteratively contract edges while updating the corresponding costs until a termination criterion is reached. The contraction of an edge ij thereby corresponds to fixing nodes i and j to be in the same cluster, i.e. joining the edge ij in the solution. Once the termination criterion is reached, the remaining graph corresponds to a clustering of the original graph, and the remaining edges correspond to a multicut. We now formalize this contraction operation for complete graphs: Definition 2. For any complete graph G = (V, E), any c ∈ RE and any edge ij ∈ E, the graph and costs obtained by contracting ij (and keeping i) are given by G′ = (V ′ , E ′ ) with V ′ = V \ {j}, ′ E ′ = E \ {e ∈ E : j ∈ e} and c′ ∈ RE such that c′kl = cki + ckj if l = i, and c′kl = ckl otherwise. ⌟ 3.2
Message Passing Neural Networks
Graph neural networks [Scarselli et al., 2009] iteratively update node features based on the features of their neighbors and the features of the edges connecting them. Message passing neural networks (MPNNs) [Gilmer et al., 2017] are a class of graph neural networks that implement these node updates in terms of a message passing scheme. This scheme is implemented in message passing layers, which are the main building blocks of MPNNs. In the following, we introduce the original formulation of message passing layers, which has since been extended [Morris et al., 2019, Bodnar et al., 2021]. Let G = (V, E) be a graph with initial node features {hi ∈ Rdin | i ∈ V } and initial edge features {hij ∈ Rdin | ij ∈ E} for some din ∈ N. Let further dout ∈ N be the dimension of the updated features. In the original formulation of message passing layers, each node i ∈ V receives messages mij ∈ Rdin from its neighbors j ∈ NG (i) based on a message function M : R3din → Rdin . The received messages are then aggregated to a single message mi ∈ Rdin , which is used to compute updated node features h′i ∈ Rdout based on an update function U : R2din → Rdout :
mij = M (hi , hj , hij ) ,
X
mi =
mij ,
h′i = U (hi , mi ) .
(2)
j∈NG (i)
4
Triangle Message Passing GNNs
To solve a given instance of the multicut problem w.r.t. a graph G = (V, E) and edge costs c ∈ RE , we train our model to predict logits for the edges to be contracted in an optimal solution. We then use the model to compute a feasible solution by iteratively contracting the edges with the largest logit in an autoregressive manner. In the following, we describe this process in detail, including preprocessing and training procedures. 4.1
Preprocessing
Graph Completion: Feasible solution to the multicut problem are characterized by the chordless cycle inequalities (1). These enforce that for every chordless cycle in the underlying graph, if an edge is cut, at least one other edge is also cut. The number of chordless cycles can be exponential. Furthermore, for large chordless cycles, this information requires many message passing layers to propagate around the cycle. To mitigate these problems, we complete the graph by adding missing edges with cost 0 as described in Lemma 2. By this lemma, the instance w.r.t. to the resulting ′ complete graph G′ = (V, E ′ ) and costs c′ ∈ RE is equivalent to the original one. Cost Normalization: It is easy to see that the multicut problem is invariant to scaling the costs ′ by a positive constant. To reflect this invariance, we consider normalized costs c̃′ ∈ RE obtained 5
by dividing the sum of absolute edge costs and multiplying by the number of edges: ∀e ∈ E ′ :
c̃′e = P
c′e
′ ′ |E | . e′ ∈E ′ |ce′ |
(3)
This normalization also ensures that the expected absolute cost of each edge is 1, stabilizing the training of our model and improving its generalization across instances of varying size. 4.2
Triangle Message Passing Layers ′
From the preprocessing, we obtain a complete graph G′ = (V, E ′ ) with normalized costs c̃′ ∈ RE . Thus, for any distinct nodes i, j ∈ V , there exists an edge ij ∈ E ′ . Furthermore, any other distinct node k ∈ V \ {i, j} forms a triangle with i and j. Since the objective function and constraints of the multicut problem are defined on edges, we assign features hij ∈ Rdin only to edges ij ∈ E ′ , avoiding ambiguities. For any distinct nodes i, j, k ∈ V , we define a message mijk ∈ Rdin from edges ik and jk to ij. For a fixed i and j, messages mijk are then aggregated to a single message mij ∈ Rdin , which is used to compute the updated features h′ij ∈ Rdout : mijk = M hij , hik + hjk , |hik − hjk | ,
mij =
1 |V | − 2
X
mijk ,
h′ij = U hij , mij . (4)
k∈V \{i,j}
Functions M : R3din → Rdin and U : R2din → Rdout are thereby multi-layer perceptrons with GELU [Hendrycks and Gimpel, 2023] activation functions. By construction, the messages mijk are invariant under the permutation of i and j. Furthermore, there exists a bijection between the message mijk and the triangle inequalities that characterize feasible solutions to the multicut problem for complete graphs. Thus, these messages directly capture the violation of triangle inequalities. 4.3
Model Architecture
Our model consists of 20 consecutive triangle message passing layers. We initialize the edge features hij ∈ R for each edge ij ∈ E ′ by the normalized cost c̃′ij . All intermediate layers have a hidden feature dimension of 64 and incorporate layer normalization and residual connections. The output layer projects the features to a dimension of 1 and omits the GELU activation function of U . We ′ interpret the output as logits z ∈ RE for the edges to be contracted in an optimal solution. With the specified number of triangle message passing layers and hidden feature dimension, our model has 403 719 learnable parameters. Since the number of triangles in a complete graph is 3 |V3 | , a pass of the model has a time complexity and a space complexity of O(|V |3 ). 4.4
Inference
We apply our model in an autoregressive manner to heuristically solve the multicut problem. ′ After preprocessing, we use our model to obtain edge logits z ∈ RE . We then select the edge e ∈ arg maxe′ ∈E ′ ze′ with the highest logit and contract it, updating the graph and the costs according to Definition 2. We repeat this process until all edge logits are non-positive. Finally, we return the obtained feasible solution. This autoregressive approach increases the worst-case time complexity to O(|V |4 ), but significantly improves the solution quality compared to a single pass as shown in Section 5.4. Like other heuristic solvers, this approach provides no approximation guarantees. 4.5
Training
We train our model supervised, on synthetic data. For each combination of graph size n ∈ {10, 15, 20, 25, 30} and costs sampled uniformly from integers in the range r ∈ 6
{[−1, 1], [−5, 5], [−100, 100]}, we generate 10 000 instances of the multicut problem. Thus, our training set consists of 150 000 instances in total. We then compute optimal solutions for these instances using an exact branch-and-cut algorithm [Irmai and Andres, 2025]. When sampling an instance from the training set, we further augment it by randomly contracting edges not cut in the optimal solution. This yields multiple training signals from the computation of a single optimal solution and further improves the generalization of our model. ′
As loss, we consider the mean binary cross-entropy between the logits z ∈ RE after applying the ′ sigmoid function σ : R → [0, 1], and the optimal solution x∗ ∈ {0, 1}E : L(z, x∗ ) = −
1 X ∗ ∗ x log(σ(z )) + (1 − x ) log(1 − σ(z )) . e e e e |E ′ | ′
(5)
e∈E
We train our model for 500 epochs using the Adam optimizer [Kingma and Ba, 2015], with a cosine annealing learning rate ranging from 10−4 to 10−6 and a batch size of 1.
5
Experiments
In this section, we evaluate our model against heuristic and exact solvers using synthetic and real-world data, and provide an ablation study. 5.1
Datasets and Experimental Setup
We primarily evaluate our model on the CP-Lib benchmark of Sørensen and Letchford [2024]. This benchmark comprises a diverse set of synthetic and real-world instances. The instances range in size from 30 to 2 500 nodes and are categorized into seven datasets based on their origin and characteristics. Not all instances of the benchmark have known optimal solutions. In these cases, the best known solutions from literature are reported. Due to the cubic time and space complexity of a model pass, we only consider instances with up to 200 nodes in our experiments. This results in a total of 152 instances from the CP-Lib benchmark for evaluation. To test the generalization capability of our model with respect to graph size, we additionally consider a dataset of random instances generated analogously to the training data. In particular, this dataset consists of 100 instances for each graph size n ∈ {10, 20, . . . , 200} with costs sampled uniformly from integers in range [−5, 5]. All experiments are performed on a machine with an Intel Core i9-12900KF CPU @ 5.20 GHz and an NVIDIA GeForce RTX 4080 Super GPU. Training with this setup and the procedure described in Section 4.5 has taken 12 hours. If an optimal solution is available, we evaluate the quality of a ∗ ) given solution by its optimality gap. The optimality gap is defined as c(x)−c(x |c(x∗ )| , where c(x) is the objective value of the obtained solution, and c(x∗ ) is the optimal objective value. For comparability, we solve each instance separately and do not parallelize over instances. 5.2
Heuristic Solvers
We compare our model against the greedy additive edge contraction algorithm (GAEC) [Keuper et al., 2015], the Kernighan and Lin algorithm with joins (KL) [Keuper et al., 2015], and the fusion moves algorithm (FM) [Beier et al., 2015] as implemented by the nifty library (MIT license). Furthermore, we compare against the deep graph reinforcement learning (DGRL) approach of Li et al. [2025], who make their code publicly available. We do not consider the solvers of Abbas and Swoboda [2022, 2023] and Jung and Keuper [2023], since they focus on solving large instances quickly, obtaining similar or worse objective values than GAEC for the instances considered in these articles. In contrast, our solver is designed to solve small- and medium-sized instances close to optimality. For FM, we use watershed-based proposals [Wolf et al., 2018] and the Kernighan and Lin algorithm with joins to solve the contracted instances. For DGRL, we use an ensemble of 10 models trained on the same data as our model.
7
Table 1: Mean optimality gaps and runtimes for solving datasets of the CP-Lib benchmark with up to 200 nodes with heuristic solvers.
Dataset ABR Artificial ClusEdit Correlation Equicut MCF Random
Optimality Gap [10−3 ] Ours KL FM GAEC DGRL Ours 3.44 0.01 85.91 0.00 0.22 0.22 1.43 33.43 61.27 6.21 18.22 52.45 4.62 33.44 38.05 1.19 5.16 5.35 1.27 0.65 0.68
91.22 0.22 85.99 64.31 67.09 14.30 1.01
Runtime [s] FM GAEC DGRL
78.26 13.10 0.0028 0.0348 0.0020 2308.85 0.21 25.78 0.0040 0.0998 0.0020 6370.35 66.02 1.42 0.0011 0.0182 0.0006 78.52 37.07 1.20 0.0011 0.0088 0.0006 28.20 46.74 0.64 0.0004 0.0076 0.0003 6.92 24.10 1.94 0.0004 0.0076 0.0003 20.25 0.95 1.86 0.0013 0.0090 0.0007 7.55 102
0 Ours KL GAEC
−1000
Ours KL GAEC
101
Runtime [s]
Objective Value
KL
−2000
100
O(|V |4) Reference
10−1 10−2 10−3
−3000
10−4 −4000 0
50
100
150
10−5
200
101
102
Graph Size
Graph Size
Figure 3: Depicted on the left are the median objective values of our model, KL and GAEC as a function of the graph size (number of nodes) for the dataset of random instances. Depicted on the right is the median runtime for these solvers on the same dataset. The error bars indicate the 0.25- and 0.75-quantile. The plot on the right uses a double logarithmic scale. The dotted line indicates the expected quartic growth of the runtime of our model.
Table 1 shows the results of the experiments on the CP-Lib benchmark. The numbers indicate mean values for the datasets. Only instances of the datasets for which an optimal solution is known are considered when computing the mean. Plots showing quantiles and per-instance results are provided in Section A. Section B contains a table with results for all instances of the CP-Lib benchmark with up to 200 nodes, including those for which no optimal solution is known. In this table, we report the best known objective value from the literature, the objective value of the solution computed by our model and its runtime. As evident from Table 1, our model significantly outperforms the considered heuristic solvers in terms of optimality gaps for all but the “ABR” and “Random” dataset. The reason for the worse performance of our model on these datasets might be related to the fact that their instances require more iterations to be solved, potentially leading to error accumulation. In terms of runtimes, our model is slower than GAEC, KL and FM on all considered datasets, but faster than DGRL. This is expected due to the quartic time complexity of our model. Still, its runtimes are in the order of seconds. The relative performance of DGRL compared to the other solvers is worse than what was originally reported by Li et al. [2025]. We believe that this is due to the hardness of the benchmark instances and insufficient generalization from out-of-distribution training data. Figure 3 shows median objective values and runtimes over the graph size for the dataset of random instances generated analogously to the training data. Given the results from Table 1, we only show values for our model, KL and GAEC.
8
Table 2: Runtimes of our model and the exact branch-and-cut solver of Irmai and Andres [2025] on selected instances of the CP-Lib benchmark, that our model solves to optimality. We provide both, the time needed by the exact solver to find the optimal solution (B&C) and the time needed to certify optimality (B&C∗ ).
Instance cars companies corr60-3 neg-c-70 ce50-40
Ours
Runtime [s] B&C B&C∗
0.18 0.008 0.016 20.64 0.039 0.117 0.81 0.008 252.898 0.44 30.148 30.148 0.47 8064.828 8064.828
Table 3: Mean optimality gaps and runtimes for solving datasets of the CP-Lib benchmark with up to 200 nodes. We compare our model with ablated versions where the key components of graph completion (Completion), triangle-based message passing (TMP) and autoregressive inference (Inference) are removed.
Dataset ABR Artificial ClusEdit Correlation Equicut MCF Random
Optimality Gap [10−3 ] Runtime [s] Ours Completion TMP Inference Ours Completion TMP Inference 3.44 0.00 1.43 6.21 4.62 1.19 1.27
14.76 0.00 2.93 7.39 6.67 4.42 1.47
6.78 0.38 11.50 31.05 24.73 9.67 2.49
0.33 13.10 0.10 25.78 94.82 1.42 36.80 1.20 158.97 0.64 14.58 1.94 5.78 1.86
13.77 25.78 1.25 1.16 0.56 1.80 1.87
17.07 28.05 1.36 1.27 0.56 1.99 2.13
0.393 0.691 0.076 0.074 0.068 0.081 0.083
As the plot on the left shows, our model achieves better optimality gaps than KL for graph sizes up to around 140. For larger graphs, its performance degrades, but still surpasses GAEC. This decrease is expected since our model is only trained on instances with up to 30 nodes, for which structures relevant to larger instances cannot occur. As seen in the plot on the right, our model is slower than KL and GAEC and exhibits the expected quartic growth in runtime. 5.3
Exact Solvers
In Table 2, we compare the runtimes of our model to the runtimes of the exact branch-and-cut algorithm of Irmai and Andres [2025] on selected instances of the CP-Lib benchmark, that our model solves to optimality. There is no correlation between the runtime of our model and that of the exact solver. This is to be expected, since the runtime of our model depends on the size of the graph and the number of edges that need to be contracted to obtain an optimal solution. In contrast, the runtime of the exact solver is dominated by the number of cutting planes that need to be added to the linear programming relaxation and the number of branching steps. Thus, for instances like “companies”, that have many nodes but an integer optimal solution in the linear programming relaxation, our model is slower than the exact solver. On the other hand, for instances like “ce50-40”, that have few nodes but are challenging for the exact solver, our model is significantly faster. Section A contains a figure visualizing the latent space of our model for the instances “cars”, “ce50-40” solved to optimality and the instance “CPn35-3” not solved to optimality. 5.4
Ablation Study
Table 3 shows the results of an ablation study evaluating the key components of our model. In the following, we briefly discuss each ablation.
9
Graph Completion: We remove the graph completion step from our preprocessing and compute messages based on individual edges if they are no longer part of a triangle. As shown in Table 3, this increases the optimality gaps on all datasets except “Artificial”. The effect is more pronounced for datasets containing sparse graphs such as “ABR”. It has no effect for the “Artificial” dataset, since all instances in this dataset are complete graphs. The runtimes decrease slightly, since fewer edges need to be considered for edge contraction. However, the time complexity of inference remain quartic in the number of nodes, since we do not adapt our architecture to sparse graphs. Triangle Message Passing: We replace our triangle message passing layers by standard edge message passing layers, in which messages are computed based on neighboring edges instead of triangles. Similar to the previous modification, this increases the optimality gaps on the datasets considered. The effect is thereby more pronounced than in the case of omitting graph completion. The runtimes show no significant change. Autoregressive Inference: We contract the edge with the largest logit, update the logits, and repeat this process until there are no positive logits remaining, without evaluating the GNN again. This approach is equivalent to GAEC when logits are considered instead of edge costs for contraction. As shown in Table 3, this modification significantly increases the optimality gaps for all but the “ABR” dataset. The improved optimality gaps for this dataset suggest again that error accumulation may be an issue for our model over the course of many iterations. Only evaluating a single pass of the network reduces the time complexity of inference to O(|V |3 ), leading to strongly reduced runtimes, as expected. However, since both solution quality and runtime lag behind that of KL, this approach is not competitive.
6
Conclusion
In this article, we introduce a GNN-based heuristic solver for the multicut problem. First, we preprocess the input graph by completing it and normalizing the edge costs. Then, we apply triangle message passing layers that operate on edge features and compute messages based on triangles. By construction, the messages computed in these layers correspond one-to-one to the triangle inequalities that define feasible solutions to the multicut problem on complete graphs. We train our model using supervised learning with randomly generated instances to predict which edges should be contracted in an optimal solution. We perform inference by iteratively contracting the edge with the largest logit in an autoregressive manner. We empirically demonstrate the effectiveness of our approach by comparing it with heuristic and exact solvers on synthetic and real-world instances with up to 200 nodes. Like other heuristic solvers for the multicut problem, our approach does not provide any approximation guarantees. One direction for future work is to adapt the training and inference procedures. Currently, the size of the instances in our training set is limited by the need to compute optimal solutions. Using reinforcement learning or self-training could allow scaling to larger training instances and potentially improve the performance of our model for larger instances. Furthermore, the inference procedure could be adapted by using more advanced techniques, such as beam search, top-k sampling, or top-p sampling, instead of deterministically sampling the edge with the highest logit. Another direction for future work is to adapt our architecture to sparse graphs. This could be accomplished by learning which edges to add during preprocessing, or by considering other graph structures, such as small chordless cycles, for message passing.
10
References Ahmed Abbas and Paul Swoboda. RAMA: A rapid multicut algorithm on GPU. In CVPR, 2022. doi:10.1109/CVPR52688.2022.00802. Ahmed Abbas and Paul Swoboda. ClusterFuG: Clustering fully connected graphs by multicut. In ICML, 2023. URL https://proceedings.mlr.press/v202/abbas23a.html. Bjoern Andres, Thorben Kroeger, Kevin L. Briggman, Winfried Denk, Natalya Korogod, Graham Knott, Ullrich Koethe, and Fred A. Hamprecht. Globally optimal closed-surface segmentation for connectomics. In ECCV, 2012. doi:10.1007/978-3-642-33712-3 56. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1): 89–113, 2004. doi:10.1023/B:MACH.0000033116.57574.95. Thorsten Beier, Thorben Kröger, Jörg H. Kappes, U. Köthe, and Fred A. Hamprecht. Cut, Glue, & Cut: A fast, approximate solver for multicut partitioning. In CVPR, 2014. doi:10.1109/CVPR.2014.17. Thorsten Beier, Fred A. Hamprecht, and Jorg H. Kappes. Fusion moves for correlation clustering. In CVPR, 2015. doi:10.1109/CVPR.2015.7298973. Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michael Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In ICML, 2021. URL https://proceedings.mlr.press/v139/bodnar21a.html. Sunil Chopra and M. R. Rao. The partition problem. Mathematical Programming, 59(1):87–115, 1993. doi:10.1007/BF01581239. Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In NeurIPS, 2019. URL https://papers.neurips.cc/paper files/paper/2019/hash/ d14c2267d848abeb81fd590f371d39bd-Abstract.html. Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263–1272, 2017. M. Grötschel and Y. Wakabayashi. A cutting plane algorithm for a clustering problem. Mathematical Programming, 45(1):59–96, 1989. doi:10.1007/BF01589097. M. Grötschel and Y. Wakabayashi. Facets of the clique partitioning polytope. Mathematical Programming, 47(1):367–387, 1990. doi:10.1007/BF01580870. Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2024. URL https://www.gurobi. com. Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs), 2023. URL https: //arxiv.org/abs/1606.08415. Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, Andreea Deac, Beatrice Bevilacqua, Yaroslav Ganin, Charles Blundell, and Petar Veličković. A generalist neural algorithmic learner. In Learning on Graphs Conference (LOG), 2022. URL https: //openreview.net/forum?id=FebadKZf6Gd. IBM. IBM ILOG CPLEX optimization studio, 2022. URL https://www.ibm.com/products/ ilog-cplex-optimization-studio. Jannik Irmai and Bjoern Andres. A state-of-the-art cutting plane algorithm for clique partitioning. In Pattern Recognition, pages 21–36, 2025. doi:10.1007/978-3-031-85181-0 2.
11
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žı́dek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino RomeraParedes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873):583–589, 2021. doi:10.1038/s41586-021-03819-2. Steffen Jung and Margret Keuper. Learning to solve minimum cost multicuts efficiently using edgeweighted graph convolutional neural networks. In Machine Learning and Knowledge Discovery in Databases, pages 485–501, 2023. doi:10.1007/978-3-031-26390-3 28. Jörg Hendrik Kappes, Markus Speth, Björn Andres, Gerhard Reinelt, and Christoph Schn. Globally optimal image partitioning by multicuts. In Energy Minimization Methods in Computer Vision and Pattern Recognition, 2011. doi:10.1007/978-3-642-23094-3 3. M. Keuper, E. Levinkov, N. Bonneel, G. Lavoue, T. Brox, and B. Andres. Efficient decomposition of image and mesh graphs by lifted multicuts. In ICCV, 2015. doi:10.1109/ICCV.2015.204. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015. URL http://arxiv.org/abs/1412.6980. Vadim Kostyukhin, Margret Keuper, Iskander Ibragimov, Nikolaus Owtscharenko, and Markus Cristinziani. Improving primary-vertex reconstruction with a minimum-cost lifted multicut graph partitioning algorithm. Journal of Instrumentation, 18(07):P07013, 2023. doi:10.1088/17480221/18/07/P07013. Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. In NeurIPS, 2022. URL http://papers.nips.cc/paper files/ paper/2022/hash/cf5bb18807a3e9cfaaa51e667e18f807-Abstract-Conference.html. Adam N Letchford and Michael M Sørensen. A separation algorithm for the clique partitioning problem. In International Symposium on Combinatorial Optimization (ISCO), 2024. URL https: //eventos.ull.es/ files/ event/ 111018/ editorFiles/file/ConferenceProgram/paper-010.pdf. Evgeny Levinkov, Alexander Kirillov, and Bjoern Andres. A comparative study of local search algorithms for correlation clustering. In GCPR, 2017. doi:10.1007/978-3-319-66709-6 9. Zhenchen Li, Xu Yang, Yanchao Zhang, Shaofeng Zeng, Jingbin Yuan, Jiazheng Liu, Zhiyong Liu, and Hua Han. Deep graph reinforcement learning for solving multicut problem. IEEE Transactions on Neural Networks and Learning Systems, 36(7):12707–12720, 2025. doi:10.1109/TNNLS.2024.3443413. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019. doi:10.1609/aaai.v33i01.33014602. Duy M. H. Nguyen, Roberto Henschel, Bodo Rosenhahn, Daniel Sonntag, and Paul Swoboda. LMGP: Lifted multicut meets geometry projections for multi-camera multi-object tracking. In CVPR, 2022. doi:10.1109/CVPR52688.2022.00866. Maarten Oosten, Jeroen H. G. C. Rutten, and Frits C. R. Spieksma. The clique partitioning problem: Facets and patching facets. Networks, 38(4):209–226, 2001. doi:10.1002/net.10004. Marcelo Prates, Pedro H. C. Avelar, Henrique Lemos, Luis C. Lamb, and Moshe Y. Vardi. Learning to solve NP-complete problems: A graph neural network for decision TSP. In AAAI, 2019. doi:10.1609/aaai.v33i01.33014731.
12
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. doi:10.1109/TNN.2008.2005605. Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT solver from single-bit supervision. In ICLR, 2019. URL https://openreview. net/forum?id=HJMC iA5tm. Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lăcki, and Vahab Mirrokni. Scalable community detection via parallel correlation clustering. In Very Large Data Base Conference (VLDB), 2021. doi:10.14778/3476249.3476282. Michael M. Sørensen. A separation heuristic for 2-partition inequalities for the clique partitioning problem, 2020. URL https://optimization-online.org/?p=16587. preprint. Michael M. Sørensen and Adam N. Letchford. CP-Lib: Benchmark instances of the clique partitioning problem. Mathematical Programming Computation, 16(1):93–111, 2024. doi:10.1007/s12532023-00249-1. Paul Swoboda and Bjoern Andres. A message passing algorithm for the minimum cost multicut problem. In CVPR, 2017. doi:10.1109/CVPR.2017.530. Siyu Tang, Mykhaylo Andriluka, Bjoern Andres, and Bernt Schiele. Multiple people tracking by lifted multicut and person re-identification. In CVPR, 2017. doi:10.1109/CVPR.2017.394. Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers in Artificial Intelligence, 3, 2021. doi:10.3389/frai.2020.580607. Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(86):2579–2605, 2008. URL http://jmlr.org/papers/v9/vandermaaten08a. html. Hernando M. Vergara, Constantin Pape, Kimberly I. Meechan, Valentyna Zinchenko, Christel Genoud, Adrian A. Wanner, Kevin Nzumbi Mutemi, Benjamin Titze, Rachel M. Templin, Paola Y. Bertucci, Oleg Simakov, Wiebke Dürichen, Pedro Machado, Emily L. Savage, Lothar Schermelleh, Yannick Schwab, Rainer W. Friedrich, Anna Kreshuk, Christian Tischer, and Detlev Arendt. Whole-body integration of gene expression and single-cell morphology. Cell, 184(18): 4819–4837.e22, 2021. doi:10.1016/j.cell.2021.07.017. Steffen Wolf, Constantin Pape, Alberto Bailoni, Nasim Rahaman, Anna Kreshuk, Ullrich Köthe, and Fred A. Hamprecht. The Mutex Watershed: Efficient, parameter-free image partitioning. In ECCV, 2018. doi:10.1007/978-3-030-01225-0 34. Adrian Wolny, Lorenzo Cerrone, Athul Vijayan, Rachele Tofanelli, Amaya Vilches Barro, Marion Louveaux, Christian Wenzl, Sören Strauss, David Wilson-Sánchez, Rena Lymbouridou, Susanne S Steigleder, Constantin Pape, Alberto Bailoni, Salva Duran-Nebreda, George W Bassel, Jan U Lohmann, Miltos Tsiantis, Fred A Hamprecht, Kay Schneitz, Alexis Maizel, and Anna Kreshuk. Accurate and versatile 3D segmentation of plant tissues at cellular resolution. eLife, 9:e57613, 2020. doi:10.7554/eLife.57613.
13
Additional Figures
Ours
KL
FM
GAEC
DGRL
ABR
Runtime [s]
10000 100 1 0.01 0.0001
0
200
400
600
800
1000
·10−3
Optimality Gap
Artificial
Runtime [s]
10000 100 1 0.01 0.0001
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
·10−3
300
·10−3
Optimality Gap
ClusEdit 10000
Runtime [s]
A
100 1 0.01 0.0001
0
50
100
150
200
Optimality Gap (continued on next page)
14
250
Correlation
Runtime [s]
10000 100 1 0.01 0.0001
0
20
40
60
80
100
120
·10−3 140
Optimality Gap
Equicut
Runtime [s]
10000 100 1 0.01 0.0001
0
20
40
60
80
100
·10−3
Optimality Gap
MCF
Runtime [s]
10000 100 1 0.01 0.0001
0
20
40
60
Optimality Gap (continued on next page)
15
80
·10−3
Random
Runtime [s]
10000 100 1 0.01 0.0001
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
·10−3
Optimality Gap Figure 4: Optimality gaps and runtimes for solving instances of the CP-Lib benchmark Sørensen and Letchford [2024] with up to 200 nodes and known optimal solutions with our model, KL Keuper et al. [2015], FM Beier et al. [2015], GAEC Keuper et al. [2015] and DGRL Li et al. [2025]. Each plot shows the instances of a different dataset. The markers correspond to values for the individual instances, while the error bars show the 0.25- and 0.75-quantile. Their intersection corresponds to the median. For datasets “ABR”, “Artificial” and “MCF”, no error bars with respect to the optimality gap are shown for some solvers since the 0.25- and 0.75-quantile are both 0. Note the logarithmic scale for the runtime and different scales for the optimality gap.
16
30
t-SNE Dimension 1
20
10
0 −10 −20 −30 −30
−20
−10
0
10
20
30
−30
t-SNE Dimension 0
−20
−10
0
10
20
30
t-SNE Dimension 0
t-SNE Dimension 1
40
20
0
−20
−40
−40
−20
0
−10
0
20
40
−40
t-SNE Dimension 0
−20
0
−10
0
20
40
t-SNE Dimension 0
30
t-SNE Dimension 1
20
10
0
−10 −20 −30
−30
−20
10
20
30
t-SNE Dimension 0
−30
−20
10
20
30
t-SNE Dimension 0
Figure 5: t-SNE plots [Van der Maaten and Hinton, 2008] of the edge features before the last triangle message passing layer for selected instance of the CP-Lib benchmark Sørensen and Letchford [2024]. In the plots on the left, each point is colored by whether the edge is cut (violet) or joined (yellow) in the same optimal solution. In the plots on the right, each point is colored based on the clusters of the corresponding nodes in an optimal solution. The top row shows features for the instance “cars”, the middle row for the instance “ce50-40” and the bottom row for the instance “CPn35-3”.
17
B
Additional Table
Table 4: Objective value and runtimes for solving instances of the CP-Lib benchmark Sørensen and Letchford [2024] with up to 200 nodes with our model. The column “Optimal Value” contains the best known objective value from literature. If it is not proven to be optimal, it is written in parentheses.
Instance
Optimal Value
Our Value
Runtime [s]
corr40-1 corr40-2 corr40-3 corr40-4 corr40-5 corr40-6 corr40-7 corr40-8 corr40-9 corr40-10 corr60-1 corr60-2 corr60-3 corr60-4 corr60-5 corr60-6 corr60-7 corr60-8 corr60-9 corr60-10 corr80-1 corr80-2 corr80-3 corr80-4 corr80-5 corr80-6 corr80-7 corr80-8 corr80-9 corr80-10
-2183 -2206 -2294 -2544 -2321 -1749 -2393 -2271 -2565 -2161 -3204 -2836 -4086 -3530 -4398 -3617 -4151 -3951 -3218 -3305 (-5026) (-4534) (-5003) (-5236) (-4443) (-5154) (-5389) (-3838) (-5336) (-3847)
-2183 -2185 -2284 -2544 -2311 -1749 -2393 -2271 -2565 -2158 -3200 -2780 -4086 -3512 -4372 -3588 -4141 -3871 -3136 -3250 -4974 -4475 -4986 -5170 -4374 -5068 -5325 -3741 -5255 -3837
0.502 0.277 0.237 0.259 0.253 0.254 0.248 0.246 0.234 0.285 0.852 0.810 0.808 0.840 0.815 0.797 0.793 0.792 0.801 0.811 2.537 2.476 2.485 2.544 2.484 2.484 2.480 2.526 2.486 2.480
18
Table 4. (Continuation)
Instance bridges cars cetacea companies hayes-roth lung-cancer lymphography micro soybean-21 soybean-35 sponge ta-evaluation uno uno 1a uno 1b uno 2a uno 2b uno 3a uno 3b wildcats workers zoo am-25-3 am-25-10 am-25-20 am-50-3 am-50-10 am-50-20 am-75-3 am-75-10 am-75-20 am-100-3 am-100-10 am-100-20 CPn35-1 CPn35-2 CPn35-3 CPn35-4 CPn45-1 CPn45-2 CPn45-3 CPn45-4 CPn50-1 CPn50-2 CPn50-3 CPn50-4
Optimal Value
Our Value
Runtime [s]
-12585 -185 -2757 -3254 -17524 -837 -8696 -1456 -3562 0 -5426 -20833 -1449 -19440 -13030 -45317 -20666 -15499 -1966 -606 -383 -1838 -697400 -1012225 -1461975 -10289800 -12861950 -16536450 -50574072 -59314800 -71801552 -178198912 -207897888 -157409600 -1094338 -1244149 -1254751 -1193970 -1892031 -1841718 -1931729 -2231594 (-2543544) (-2184771) (-2484518) (-2293499)
-12500 -185 -2757 -3254 -16943 -837 -8452 -1456 -3562 0 -5426 -20831 -1449 -19413 -13030 -45187 -20666 -15499 -1966 -606 -383 -1838 -697400 -1012225 -1461975 -10289800 -12861950 -16536450 -50574072 -59314800 -71801552 -178198912 -207897888 -157409600 -1093709 -1242595 -1252596 -1192788 -1888275 -1840790 -1929388 -2229841 -2540516 -2182940 -2482190 -2289125
8.345 0.178 0.185 20.636 35.988 0.171 26.410 0.236 0.367 0.379 2.039 28.495 0.541 34.381 23.286 34.222 24.369 34.223 25.725 0.158 0.190 6.625 0.393 0.341 0.383 5.924 6.025 6.562 25.967 25.970 25.966 74.535 74.374 74.375 0.214 0.188 0.196 0.210 0.387 0.386 0.389 0.377 0.513 0.474 0.441 0.451
19
Table 4. (Continuation)
Instance CPn65-1 CPn65-2 CPn65-3 CPn65-4 CPn100-1 CPn100-2 CPn100-3 CPn100-4 rand100-5 rand100-100 rand200-5 rand200-100 boc 1 boc 2 boc 3 boc 4 boc 5 boc 6 boc 7 boc 8 boc 9 boc 10 boe 91 bur 69 bur 73 bur 75 bur 91 can 97 cha 86 cha 87 gro 80 ira 95 kat 97 kin 80 lee 97 mas 97 mcc 72 mil 91 nai 96a nai 96b nai 96c nai 96d rog 05 sei 88 sul 91
Optimal Value
Our Value
Runtime [s]
(-3975105) (-4016487) (-3966284) (-4114808) (-9491009) (-9569436) (-9365902) (-9317302) (-24449) (-8744) (-4590) (-84667) -296 -329 -356 -308 -338 -354 -334 -313 -331 -334 -474 -532 (-2762) -503 -498 -696 -532 -3507 -287 -120 (-1108) -259 -1011 -167 -257 -749 -791 -815 -769 -792 -818 -142 -124
-3970775 -4012175 -3960474 -4109607 -9477322 -9555832 -9350392 -9303954 -1504 -30688 -3991 -76838 -296 -326 -356 -308 -338 -354 -334 -310 -331 -334 -473 -532 -2747 -502 -498 -696 -532 -3491 -285 -120 -1079 -259 -1011 -167 -257 -749 -791 -815 -769 -792 -816 -142 -124
1.568 1.221 1.314 1.194 6.472 6.581 6.443 6.302 5.968 6.429 79.716 79.755 0.341 0.621 0.316 0.308 0.330 0.321 0.337 0.321 0.347 0.441 0.555 0.567 14.720 0.993 0.707 1.302 0.573 22.819 0.256 0.146 8.032 0.191 1.442 0.175 0.205 0.725 1.387 1.608 1.344 1.165 1.102 0.212 0.191
20
Table 4. (Continuation)
Instance
Optimal Value
Our Value
Runtime [s]
neg-c-00 neg-c-10 neg-c-20 neg-c-30 neg-c-40 neg-c-50 neg-c-60 neg-c-70 neg-c-80 neg-s-80 neg-tt-80 ce50-20 ce50-30 ce50-40 ce50-50 ce50-60 ce60-20 ce60-30 ce60-40 ce60-50 ce60-60 ce70-20 ce70-30 ce70-40 ce70-50 ce70-60 ce80-20 ce80-30 ce80-40 ce80-50 ce80-60
-1102 -1158 -1154 -1106 -949 -851 -683 -548 -425 -576 (-728) -793 -570 -350 -164 -12 -1135 (-808) -505 (-200) -19 -1542 (-1095) (-660) (-267) -8 -2003 (-1421) (-859) (-325) -25
-1097 -1152 -1147 -1106 -943 -850 -682 -548 -424 -565 -719 -791 -568 -350 -164 -12 -1131 -801 -504 -194 -19 -1538 -1092 -652 -259 -8 -1997 -1415 -849 -318 -25
0.538 0.535 0.456 0.422 0.527 0.521 0.443 0.437 0.524 0.885 1.750 0.486 0.471 0.466 0.430 0.488 0.744 0.802 1.034 1.025 0.996 1.545 1.517 1.541 1.716 1.518 2.656 2.779 2.647 2.726 2.724
21