On Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs
Roberto Montemanni, Derek H. Smith · 2025
Read On Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs by Roberto Montemanni, Derek H. Smith (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14503.txt.
Introduction
Roberto Montemanni and Derek Smith revisit a hard network problem in a 2025 paper. The classic task is the minimum spanning tree: link all points in a graph at the lowest total cost. Their version adds conflict pairs, edges that cannot both appear in the tree, a twist that fits several real planning problems.
Earlier teams attacked the problem with clever search methods and exact solvers. Montemanni and Smith instead try a mixed integer linear program that no one had applied to this problem, and run it with a free, open solver. On the standard set of 230 test cases, their plain approach matched far fancier methods. It closed six cases for the first time and improved many best-known bounds.
Catalog record
| CREATOR | Roberto Montemanni, Derek H. Smith |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14503
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Solving the Minimum Spanning Tree Problem with Conflicting Edge Pairs Roberto Montemanni, Derek H. Smith Abstract The Minimum Spanning Tree with Conflicting Edge Pairs is a generalization that adds conflict constraints to a classical optimization problem on graphs used to model several real-world applications. In the last few years several approaches, both heuristic and exact, have been proposed to attack the problem. In this paper we consider a mixed integer linear program never approached before in the context of the problem under investigation, and we solve it with an open-source solver. Computational results on the benchmark instances commonly used in the literature of the problem are reported. The results indicate that the approach we propose, in its simplicity, obtains results aligned with those of the much more sophisticated approaches available. During the experimental campaign 6 instances have been closed for the first time, with 9 improved best-known lower bounds and 16 improved best-known upper bounds over the 230 instances considered. I Introduction The Minimum Spanning Tree Problem with Conflicting Edge Pairs (MSTC) is a very recent variant of the classical minimum spanning tree (MST) problem [ 1 ] . Given a connected undirected graph with costs on the edges and a set of edges pairs in conflict with each other, the MSTC consists of finding the spanning tree with minimum total cost that uses at most one of the edges of each conflicting pair. The MSTC was first introduced by Darmann et al. [ 2 ] . It was shown that under general settings the problem cannot be solved in polynomial time, although some special cases are shown to be polynomially-solvable. Several heuristics for the problem were subsequently proposed in [ 3 ] , while a branch-and-cut based on a mathematical programming model and some valid inequalities was presented in [ 4 ] . More recently, a metaheuristic method was designed and presented in [ 5 ] , while some new methods based on Lagrangian relaxations able to produce high-quality lower bounds for the optimal solution and heuristic solutions were introduced in [ 6 ] . Finally, a new branch-and-cut approach based on new valid inequalities was discussed in [ 7 ] , and shown to represent the state-of-the-art for exact solving methods. MSTC can be used to represent real problem arising in different domains. For example, the design of an offshore wind farm network, where the wind-turbines have to be connected together and the different possible point-to-point connections are characterized by different costs. Technical reasons prevent the use of overlapped cables in this domain [ 8 ] , and this generates conflict constraints. Other practical applications are in the design and installation of long-distance pipelines, where conflicts typically represent the impossibility of using infrastructures of competitor service providers, or crossing countries with reciprocal political issues with a same line [ 9 ] . In this paper, a compact mixed integer linear programming model for the problem is considered for the first time in the context of the MSTC and it is solved by the open-source solver CP-SAT, which is part of the Google OR-Tools [ 10 ] optimization suite. Successful application of this solver on optimization problems with characteristics similar to the problem under investigation, motivated our study [ 11 ] , [ 12 ] , [ 13 ] . A vast experimental campaign on the benchmark instances previously used to validate algorithms in the literature is carried out. The overall organization of the paper can be summarized as follows. Section II is dedicated to the formal introduction and definition of the Minimum Spanning Tree Problem with Conflicting Edge Pairs. Section III presents a compact mixed integer linear programming model to represent the problem. In Section IV the model proposed is analyzed from an experimental perspective. After the description of the benchmark instances considered and of the methods used for comparison purposes, the detailed results obtained by solving the new model are reported. Some conclusions about the work presented are drawn in Section V to close the paper. II Problem Description The Minimum Spanning Tree Problem with Additional Conflicts can be defined on an undirected graph G=(V,E) , with V denoting the set of nodes and E the set of edges. Each edge \{i,j\}\in E is associated with a cost u_{ij}\in\mathbb{N}^{+} . Moreover, two edges \{i,j\},\{k,l\}\in E are said to be in conflict if at most one of them can be included in a feasible solution. The set of edges in conflict with the edge \{i,j\}\in E is defined by the set \delta(i,j) . The objective of the MSTC is to identify a spanning tree (a tree including all nodes) fulfilling all the conflict constraints with minimum possible total cost. A small example of an MFPC instance and an optimal solution for the instance are provided in Figure 1 . f a b c d e g 3 6 1 2 1 4 3 2 4 3 5 7 f a b c d e g 3 1 1 3 2 3 3 Fig. 1 : On the left an example of a small MSTC instance is shown, where the edge capacities are placed by the edges. Edges in black are not affected by conflicts while any two edges sharing the same red, blue or green color are in conflict. On the right, an optimal solution that does not violate any conflict is shown. III A Mixed Integer Linear Programming Model In this section a model for the MSTC, obtained by extending a classical model for the Minimum Spanning Tree Problem [ 14 ] , is proposed. The model is based on multi-commodity flow and relies on a set A of (directed) arcs, obtained by including the two arcs (i,j) and ( j,i) for each edge \{i,j\}\in E . A node s is arbitrarily selected as the root (node 0 in our implementation) and the aim of the model is to send one unit of flow from s to any other node of V using the arcs of A . Formally, a variable x_{ij}\in\mathbb{Z}^{+}_{0} is introduced for each (i,j)\in A . It takes the value of flow transiting the arc (i,j)\in A . Another set of variables is required to match the multi-commodity flow problem back to the MSTC problem. Then a binary variable y_{ij} is defined for each edge \{i,j\}\in E . It takes value 1 if the edge is part of the solution, 0 otherwise. The resulting compact model is as follows. \displaystyle\min\ \ \sum_{\{i,j\}\in E}u_{ij}y_{ij} (1) \displaystyle s.t.\ \ \displaystyle\sum_{(j,i)\in A}\!\!\!\!x_{ji}-\!\!\!\!\sum_{(i,j)\in A}\!\!\!x_{ij}\!=\!\begin{cases}-|V|+1\ \!\text{if $i=s$}\\ +1\!\ \ \ \ \ \ \ \ \ \!\text{if $i\neq s$}\end{cases}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \displaystyle i\in V (2) \displaystyle x_{ij}\leq(|V|-1)y_{ij} \displaystyle\{i,j\}\in E (3) \displaystyle x_{ji}\leq(|V|-1)y_{ij} \displaystyle\{i,j\}\in E (4) \displaystyle{y_{ij}+y_{kl}\leq 1} \displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\{i,j\}\in E,(k,l)\in\delta_{ij} (5) \displaystyle x_{ij}\geq 0 \displaystyle(i,j)\in A (6) \displaystyle y_{ij}\in\{0,1\} \displaystyle\{i,j\}\in E (7) The objective function ( 1 ) minimizes the cost of the spanning tree. Constraints ( 2 ) implement a classical multi-commodity flow model on the directed network, and impose that one unit of the commodity has to exit the source s for each other node of V (case i=s ) and that each node different from s has to retain exactly one unit of the commodity (case i\neq s