On Solving the Maximum Flow Problem with Conflict Constraints

Roberto Montemanni, Derek H. Smith · 2025

Read On Solving the Maximum Flow Problem with Conflict Constraints 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-2503-19685.txt.

Introduction

Network planners often ask how much flow can move from source to sink, but some pairs of routes cannot both be used. Roberto Montemanni and Derek Smith tackle this conflict version of the classic maximum flow problem in 2025. Earlier teams attacked it with both exact methods and shortcuts. The authors instead write it as a mixed integer linear program and hand it to an open-source solver.

The plain approach proved strong. All 160 standard benchmark cases were solved to proven optimality for the first time, twenty-eight of them closed for good. Along the way the solver also beat the best known shortcut answers on six cases. Simplicity, here, outperformed cleverness.

Catalog record

CREATORRoberto Montemanni, Derek H. Smith
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19685

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 Maximum Flow Problem with Conflict Constraints Roberto Montemanni, Derek H. Smith Abstract The Maximum Flow Problem with Conflict Constraints is a generalization that adds conflict constraints to a classical optimization problem on networks 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 and solve it with an open-source solver. Computational results on the benchmark instances commonly used in the literature of the problem are reported. All the 160 instances benchmark instances normally used in the literature are solved to optimality for the first time, with 28 instances closed for the first time. Moreover, in the process, 6 improvements to the best-known heuristic solutions are also found. I Introduction The study of maximum flow problems in network optimization has a long history starting in the 1950s [ 1 ] , with research driven by real applications in the transportation and communication fields. In this paper we consider the Maximum Flow Problem with Conflicts (MFPC), which consists of retrieving a maximum flow from a given source to a given sink in a given network, while complying with classical capacity constraints of the connections, but also preventing positive flow from being contemporarily carried out by the arcs of any conflicting pair. Notice that the latter restriction makes the problem considerably harder than the original version. The MFPC was first studied in [ 2 ] , where the authors considered both positive disjunctive constraints (at least one of two arcs has to be selected )and negative disjunctive constraints (at most one of two arcs can be selected), showing the NP-hardness of all the resulting variants. Later, the use of negative disjunctive constraints to model conflicts between arc pairs in order to model real-world applications, was studied in [ 3 ] , where some mixed-integer linear programming formulations and exact methods for the problem such as a Benders Decomposition, a Branch & Bound and a Russian Doll Search were provided. More recently, the authors of [ 4 ] proposed a heuristic approach for the problem called Kernousel, obtained by merging two metaheuristic approaches, one based on Carousel Greedy [ 5 ] and the other on Kernel Search [ 6 ] . Applications of the MFPC can be found in the routing of messages on telecommunication networks, where conflicts might be used to avoid the use of links of contractually-incompatible providers [ 7 ] , in the optimization of personnel scheduling [ 8 ] , in transportation, where conflicts constraints might be used to avoid paying alternative (cumulative) tolls while solving routing applications [ 7 ] . Other more specific applications can be found in the image segmentation domain [ 9 ] . In this paper a mixed integer linear programming model for the problem is considered and attacked by the open-source solver CP-SAT, part of the Google OR-Tools [ 10 ] suite for optimization. The experimental results on the benchmark instances previously adopted in the literature improve the state-of-the-art, with several improved heuristic solutions retrieved in very short time, and all the instances solved to proven optimality for the first time. This achievement is not unexpected, being in line with some recent results obtained on other combinatorial optimization problems [ 11 ] , [ 12 ] , [ 13 ] . The paper is organized as follows. In Section II the Maximum Flow Problem with Conflict Constraints is formally introduced and defined, while in Section III the mixed integer linear programming model adopted is discussed. Section IV is devoted to the description of the benchmark instances previously adopted in the literature and to the presentation of the experimental results obtained by the new model we propose. Finally, conclusions about the work presented are drawn in Section V . II Problem Description The Maximum Flow Problem with additional Conflict Constraints can be defined on a directed graph G=(V,A) , with V denoting the set of nodes and A the set of arcs. The node set includes a source node s and a sink node t , while each arc (i,j)\in A is associated with a capacity u_{ij}\in\mathbb{N}^{+} , indicating the maximum amount of flow that can be sent from node i to node j through the direct connection between them.Moreover, two arcs (i,j),(k,l)\in A are said to be in conflict if at most one of them can have positive flow in a feasible solution. The set of arcs in conflict with the arc (i,j)\in A is defined by the set \delta(i,j) . The objective of the MFPC is to identify the maximum flow from s to t that satisfies the capacity and the conflict constraints, and to route such a flow through the network. A small example of an MFPC instance (taken from [ 4 ] ) and an optimal solution for the instance are provided in Figure 1 . s a b c d e t 3 6 1 2 1 4 3 2 4 3 5 7 s a b c d e t 2/3 3/6 2/2 3/4 3/3 2/5 3 Fig. 1 : On the left an example of a small MFPC instance is shown, where the arc capacities are placed by the arcs. Arcs in black are not affected by conflicts while any two arcs sharing the same red, blue or green color are in conflict. On the right a feasible solution carrying the maximal possible flow from s to t without violating any conflict is shown. III A Mixed Integer Linear Programming Model In this section a model for the MFPC [ 3 ] is described. A variable f_{ij}\in\mathbb{Z}^{+}_{0} is introduced for each (i,j)\in A , and represents the flow carried by the arc in the solution under investigation. In order to model conflicts, a second set of variables is introduced. For each (i,j)\in A , a binary variable x_{ij} is considered, and takes value 1 if f_{ij}>0 , 0 otherwise. Finally, a variable z\in\mathbb{Z}^{+}_{0} is introduced to capture the total flow from s to t passing through the network in the solution under investigation. The resulting model is as follows. \displaystyle\max\ \ z (1) \displaystyle s.t.\ \ \displaystyle\sum_{(j,i)\in A}\!\!\!\!f_{ji}-\!\!\!\!\sum_{(i,j)\in A}\!\!\!f_{ij}\!=\!\begin{cases}-z\ \text{if $i=s$}\\ +z\ \text{if $i=r$}\\ 0\ \ \ \text{otherwise}\end{cases}\!\!\!\!\!\!\!\!\!\! \displaystyle i\in V (2) \displaystyle f_{ij}\leq u_{ij}x_{ij} \displaystyle(i,j)\in A (3) \displaystyle{x_{ij}+x_{kl}\leq 1} \displaystyle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(i,j)\in A,(k,l)\in\delta_{ij} (4) \displaystyle f_{ij}\geq 0 \displaystyle(i,j)\in A (5) \displaystyle x_{ij}\in\{0,1\} \displaystyle(i,j)\in A (6) The objective function ( 1 ) maximizes the total flow from s to t . Constraints ( 2 ) deal with flow conservation and set z at the same time. Notice that these constraints are the core, together with ( 5 ), of the classic formulation for the Maximum Flow Problem. Inequalities ( 3 ) regulate the activation of x variables as soon as the respective f variables carry some positive flow. Constraints ( 4 ) model conflicts and forbid conflicting edges to be active at the same time. Finally the domains of the variables are specified in constraints ( 5 ) and ( 6 ). IV Computational Experiments The benchmark instances adopted in the literature are introduced in Section IV-A , while a comparison of the

Read the complete text