# Mixed Integer Linear Programming Framework for SAT Variants of the Connected Flow Problem

Victor Epain, Kerian Thuillier

► To cite this version:

Victor Epain, Kerian Thuillier. Mixed Integer Linear Programming Framework for SAT Variants of the Connected Flow Problem. 2025. hal-05133695

HAL Id: hal-05133695

https://hal.science/hal-05133695v1

Preprint submitted on 27 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Mixed Integer Linear Programming Framework for SAT
## Variants of the Connected Flow Problem

Victor Epain¹ and Kerian Thuillier²

¹DISCo, Univ. Milano – Bicocca, Viale Sarca, Milano, 20126, Italy

²Laboratoire de Méthodes Formelles, Université Paris-Saclay, CNRS, ENS Paris-Saclay, Gif-sur-Yvette, France

27th June 2025

## Abstract

Some combinatoric optimization problems on graphs, such as graph partitioning or weighted vertex cover variants, can involve a flow formulation on a dedicated flow network wrapping the graph. Mixed Integer Linear Programming (MILP) is a flexible solution to model discrete optimization problems on graphs while focusing on the properties the solutions must satisfy. In this paper, we define additional connectivity properties the flow must satisfy. For each of these, we propose variants of exploration tree descriptions through MILP formulations. We model fundamental bricks on which someone can build their own MILP formulation dedicated to their problem when they need the flow to respect particular connectivity properties.

**Keywords:** Discrete global combinatoric optimization problem — Graph algorithm — Exploration tree

## Contents

Prelude 2

1 Introduction 3

1.1 Flow MILP 4

2 Connected Flow Problem 5

3 Connected Intermediate Flow Problem 7

4 Directed Anchor Connected Flow Problem 11

5 Anchor Connected Flow Problem 12

6 Optimization problem examples 15

A Tutorial: ConFlow from primal-dual SAT I
# Prelude

<figure><img src="image_2.png" /></figure>

## To-do

Papers to read:

- [ ] 'A Mixed Integer Linear Programming Model and Variable Neighborhood Search for Maximally Balanced Connected Partition Problem' [Mat14]

- [ ] 'Partitioning a Graph into Balanced Connected Classes' [Miy+21]

- [ ] 'On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem' [Man+21]

<figure><img src="image_3.png" /></figure>

## To-do

- [x] Change vertex capacities to arc capacities

- [ ] Describe the primal-dual satisfiability without the arc choices

- [ ] Detail which constraints we add to model a subgraph

<figure><img src="image_4.png" /></figure>

## Question

Should we attack a generalization? Hypergraph?

<figure><img src="image_5.png" /></figure>

## Question

We get the constraints from the primal-dual SAT formulation. But some of the constraints can be simplified ($x_s = 1$ can be removed, and we can force $alpha_s$ minus the sum of betas to be equal to 1 instead of $\le 1$). Also, defining the $\beta$ (and $\zeta$) as negative reals complicate the understanding and the comprehension. We should think about that, perhaps it is better to simplify the variable definitions and the constraints.

<figure><img src="image_6.png" /></figure>

### Note

As the simplification can involve transforming inequalities into equalities, see this comment: https://or stackexchange.com/a/3172/12506

<figure><img src="image_7.png" /></figure>

### Idea

We can describe in appendix a tutorial how to get the CONFLOW model thanks to a Primal-Dual SAT model. Then, it would be sufficient to explain how we can adapt the variables and the constraint to get the current model.
# 1 Introduction

<figure><img src="image_8.png" /></figure>

**Note**

Remark that Ford Fulkerson can already ensure we are in the connected component.

<figure><img src="image_9.png" /></figure>

**Question**

Is there a FF execution such that we can find several components? If yes, declare that even the traditional algo does not ensure ...

<figure><img src="image_10.png" /></figure>

**To-do**

Give examples of optimization problems modelling in their core a flow:

* Haplotyping (Exact Minimum Flow Decompositions) [Dia+22]

* Regulatory flux balance analysis (rFBA) [TSP24]

* PlasBin-flow: binning plasmid sequences [Man+23]

* ...

## ■ Definition 1.1: Network

A network $G = (V, A, s, t, cap)$ is a directed graph with source $s$ and sink $t$ vertices, where the function $cap: A \to \mathbb{R}_{\ge 0}$ assigns a capacity to each arc.

At the opposite of some definitions in operational research, our network can be any directed graph so that $(u, v) \in A \Leftrightarrow (v, u) \in A$. Also note that there is neither incoming arcs to the source $s$, nor outgoing arcs from the sink $t$.

## ■ Definition 1.2: Feasible flow

A feasible flow, or a flow, is a map $flow: A \to \mathbb{R}_{\ge 0}$ on a network $G = (V, A, s, t, cap)$ such that:

**Capacity restriction**

$$flow(a) \le cap(a) \quad \forall a \in A$$

**Flow conservation**

$$\sum_{(u,v) \in A} flow(u, v) = \sum_{(v,w) \in A} flow(v, w) \quad \forall v \in V \setminus \{s, t\}$$

**The source flow equals the sink flow (total flow)**

$$\sum_{(s,w) \in A} flow(s, w) = \sum_{(u,t) \in A} flow(u, t) = TotalFlow$$
## Definition 1.3: Strict flow network

A strict flow network is a subgraph $G' = (V', A', flow)$ of a network $G = (V, A, s, t, cap)$ such that:

* $flow: A \to \mathbb{R}_{\ge 0}$ is a feasible flow for $G$

* $V'$ is the set of vertices present in $A'$

* $A' = \{a \in A | flow(a) > 0\}$

Note that in Definition 1.3, the source $s$ and the sink $t$ belong to $V'$.

## Definition 1.4: Intermediate strict flow network

The intermediate strict flow network $G'' = (V'', A'', flow)$ is the subgraph of a strict flow network $G' = (V', A', flow)$ such that:

* $V'' = V' \setminus \{s, t\}$

* $A'' = \{(u, v) \in A' | u \neq s \land v \neq t\}$

Sections 2 to 4 describe variants of the flow problem with additional constraints. In each of these sections, we define the variants and propose MILP formulations to solve them. For clarity's sake, we illustrate the variant with the Maximum Flow problem (MAXFLOW), although it does not directly motivate the variants. In Section 6 we give some optimization problem examples motivating these variants and show how we can simply add new MILP constraints and change the objective function to pass from the SAT variants to the optimization problems.

### Idea

Use the word "Flow problem framework" to motivate our article i.e. say we propose minimum description as brick to build optimization problem in MILP.

# 1.1 Flow MILP

Here we describe the MILP formulation serving as common MILP part for all the further variants.

## Definition 1.5: Flow MILP variables

* $f_a \in \mathbb{R}_{\ge 0} \forall a \in A$ corresponding to the flow amount passing through the arc $a$.

## Definition 1.6: Flow MILP constraints

The flow amount cannot exceed the capacity:

$$f_a \le cap(a) \quad \forall a \in A \qquad (C1)$$

The outgoing flow from the source equals the incoming flow to the sink:

$$\sum_{(s,w) \in A} f_{sw} = \sum_{(u,t) \in A} f_{ut} \qquad (C2)$$
For a given vertex that is neither the source nor the sink, the outgoing flow equals the incoming flow:

$$ \sum_{(u,v) \in A} f_{uv} = \sum_{(v,w) \in A} f_{vw} \quad \forall v \in V \setminus \{s,t\} \qquad (C3) $$

To model the well known MAXFLOW problem, it is sufficient to add the following objective function:

### Definition 1.7: MAXFLOW problem MILP objective function

$$ \max \ TotalFlow \qquad (O1) $$

Where

$$ TotalFlow = \sum_{(s,w) \in A} f_{sw} = \sum_{(u,t) \in A} f_{ut} $$

In this section and the following ones, we say a vertex, an arc, is active if, and only if, it participates in the solution graph $G'$.

## 2 Connected Flow Problem

### ■ Problem 2.1: (CONFLOW) Connected Flow SAT problem

The strict flow network $G'$ is (weakly) connected.

In the MAXFLOW problem, the aim is to maximize the total flow. In that context, it is not necessary to find a connected flow. The strict flow network can thus have cyclic connected components not connected to $s$ and $t$. These cycles respect the conservation constraints. Here, we want to avoid these autonomous cycles, otherwise consider them in $G'$ if, and only if they are connected to $s$ and $t$. One motivation to have a connected flow can be to find a flow maximizing the sum of vertices input flow. Without constraining the flow to be connected, solutions can profit from autonomous cycles to maximize the sum. For clarity's sake, we will only illustrate with the maximum flow problem, such that the constraints we describe in this article can directly be used and completed to create a motivated optimization problem. Figure 1 illustrates optimal solutions for the MAXFLOW problem for two different values of $\epsilon_F$ (2 and 10).

In the following, we say a vertex, an arc, is active if, and only if, it participates in the solution graph $G'$.

### ■ Definition 2.1: CONFLOW MILP variables

In addition to the variables in Definition 1.5:

* $x_v \in [0,1] \forall v \in V$ denoting whether the vertex $v$ is active or not. With the constraints it acts as a binary.

* $y_a \in \{0,1\} \forall a \in A$ denoting whether the arc $a$ is active or not.

* $\beta_a \in [0, |V| - 1] \forall a \in A$ is non-zero if the arc $a$ participates in the solution graph
exploration tree. It acts as an integer, where the value corresponds to the number of vertices in the subtree with root the successor.

## Definition 2.2: CONFLOW MILP constraints

In addition to the constraints in Definition 1.6:

A positive flow activates the corresponding arc:

$$f_a \le cap(a)y_a \quad \forall a \in A \quad (C4)$$

An arc is active only if there is a positive flow on it:

<figure><img src="image_11.png" /></figure>

### Warning

Give an example why this is necessary (because of loops).

$$y_a \le \frac{1}{\epsilon_F} f_a \quad \forall a \in A \quad (C5)$$

where $\epsilon_F > 0$ is the minimum positive flow amount.

An active arc activates the incident vertices:

$$y_{uv} \le x_u \quad \forall (u, v) \in A \quad (C6)$$

$$y_{vu} \le x_v \quad \forall (u, v) \in A \quad (C7)$$

An arc can participate in the tree only if it participates into the connected graph:

$$\beta_a \le y_a|V| \quad \forall a \in A \quad (C8)$$

<figure><img src="image_12.png" /></figure>

### Note

Vic: I removed the constraint forcing the source to be in the connected component.

<figure><img src="image_13.png" /></figure>

### Note

Vic: I removed the constraints $x_u - x_v \le 1 - y_{uv}$ because I find it redondant with the Constraints C6 and C7 when we set the upper bound for the x variables.

The number of vertices in the trees with roots the source's successors at least equals the number of vertices in $G'$ minus the source:

<figure><img src="image_14.png" /></figure>

### Note

Vic: I replaced alpha here, and change the inequality to put an equality

<figure><img src="image_15.png" /></figure>

### Question

Should we simplify the constraint (i.e. with removing the source from the sum, and/or say equals to 0)?
$$ \sum_{v \in V} x_v - \sum_{(s,w) \in A} \beta_{sw} = x_s \qquad (C9) $$

<figure><img src="image_16.png" /></figure>

### Warning

Find a better description?

<figure><img src="image_17.png" /></figure>

### Note

Vic: the inequality becomes an equality

<figure><img src="image_18.png" /></figure>

### Question

What can ensure us we have only one non-zero $\beta_{uv}$?

If a vertex $v$ is active, then one $\beta_{uv}$ corresponds to the number of vertices in the subtree with root $v$:

$$ \sum_{(u,v) \in A} \beta_{uv} - \sum_{(v,w) \in A} \beta_{vw} = x_v \quad \forall v \in V \setminus \{s\} \qquad (C10) $$

<figure><img src="image_19.png" /></figure>

### Question

Can we make $y_A$ variables in $[0, 1]$?

## 3 Connected Intermediate Flow Problem

### ■ Problem 3.1: (CONINTFLOW) Connected Intermediate Flow SAT problem

The intermediate strict flow network $G''$ is (weakly) connected.

CONINTFLOW is a direct adaptation of CONFLOW, where we extend the definition set of the $\beta$ variables, and we add new vertex variables $r$ to define which vertex will be the uniquely source-connected vertex in the tree.

### ■ Definition 3.1: CONINTFLOW MILP variables

Same variables as in Definition 2.1, with a modification of the definition set for the $\beta$ variables:

* $\beta_e \in [0, |V| - 1] \forall e \in E = A \cup A^{rev}$ is strictly positive if the arc-edge $e$ participates in the solution graph exploration tree. $A^{rev} = \{(v, u) | (u, v) \in A, u \neq s \land v \neq t\}$. It acts as an integer, where the value corresponds to the number of vertices in the subtree with root the successor.

* $r_v \in \{0, 1\} \forall v \in V | \exists (s, v) \in A$ defines whether the vertex $v$ is the source-connected
<figure><img src="image_20.png" /><figcaption>(a) Flow for $\epsilon_F = 2$</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(c) Tree for $\epsilon_F = 2$</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(b) Flow for $\epsilon_F = 10$</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(d) Tree for $\epsilon_F = 10$</figcaption></figure>

■ Figure 1 – Connected flow examples

For two different values of $\epsilon_F$ (2 and 10), we show one solution graph ((a) and (b)) and the associated exploration tree describing the connected flow ((c) and (d)). All the arcs have a capacity of 10, except for the source and the sink arcs where the capacity is unbounded. Dashed vertices and arcs do not participate in the solutions. (a), (b) The flow values on the arcs are in blue. In both cases, the total flow equals 20. However, in (b), because the minimum positive flow $\epsilon_F$ equals 10, the flow cannot pass through both (D, A) and (D, T) simultaneously. Without the connected flow constraints, a graph to which the autonomous cycle $A \leftrightarrow B$ had been added would have remained an optimal solution for the Max Flow Problem. (c), (d) The green arc values correspond to the non-zero $\beta_a$ variable values.
vertex in the tree or not.

### Question

Can we relax $r_v$ variables?

### Definition 3.2: CONINTFLOW MILP constraints

In addition to the constraints in Definition 2.2 (except Constraint C10):

The following constraint complete Constraint C8. The tree corresponds to the exploration tree of a weakly connected component, so an arc $(u, v)$ can be in the tree, or its reverse $(v, u)$:

$$ \beta_{uv} \le y_{vu} |V| \quad \forall (u, v) \in A^{rev} \qquad (C11) $$

Constraint C10 is specialized depending whether the vertex is the sink or not:

$$ \sum_{(u,v) \in E} \beta_{uv} - \sum_{(v,w) \in E} \beta_{vw} = x_v \quad \forall v \in V \setminus \{s, t\} \qquad (C12) $$

and for the sink:

$$ \sum_{(u,t) \in A} \beta_{ut} = x_t \qquad (C13) $$

The source is connected to only one vertex in the tree:

$$ \sum_{v \in V \setminus \{s,t\}} r_v = 1 \qquad (C14) $$

There is only one arc in the tree that connects the source:

$$ \beta_{sv} \le r_v |V| \quad \forall (s, v) \in A \qquad (C15) $$

Additional constraints can be added to give a priority to some vertices to connect the source in the tree. Let $v_s$ to be an arbitrary vector containing once all the vertices connected to the source (let assume their number equals to $n$). Then:

$$ r_w \le r_v + (1 - y_{sv}) \quad \forall k \in \{0, \dots, n-2\} \ v, w = v_s[k], v_s[k+1] \qquad (C16) $$

Thus, the first vertex in $v_s$ connected to the source in $G'$ is the one connected to the source in the tree.
<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

■ **Figure 2 – Connected intermediate flow examples**

Subfigures (a) and (b) represent the flow values in blue on two slightly different graphs, while (c) represents the tree associated to (b), where the $\beta$ variables non-zero values are in green. All the arcs have a capacity of 10, except for the source and the sink arcs where the capacity is unbounded. Dashed vertices and arcs do not participate in the solutions. (a) The total flow equals 10. The flow cannot pass through both (S, A) and (S, C) simultaneously, otherwise $G''$ would have had two connected components. (b) In the opposite, now the flow can pass through both the previous arcs because it can pass through the new arc (C, B) to augment the flow to 30. (c) The extension of the definition set for the $\beta$ variables enables to describe an oriented tree by choosing the arc (B, C) instead of the reverse (which do not enable to define a tree). Here, we assume that A comes before C in the vector $v_s$, so that A is the vertex to which the source connects in the tree.
# 4 Directed Anchor Connected Flow Problem

## ■ Problem 4.1: (DIRANCONFLOW) Directed Anchor Connected Flow SAT problem

Given a subset of vertices $V_{anc} \subseteq V \setminus \{s, t\}$ we denote as anchors, for all the connected subgraphs $G_i'' = (V_i, A_i)$ of the strict flow network $G''$, for all non-anchor vertices $v \in V_i$, there exists an anchor $v_a$ such that there is a directed path $v_a \rightsquigarrow v_i$ or $v_i \rightsquigarrow v_a$.

DIRANCONFLOW is an adaptation of CONFLOW, where we add constraints similar to the ones describing an exploration tree in order to describe a source anchor tree, and a sink anchor tree.

## ■ Definition 4.1: DIRANCONFLOW MILP variables

In addition to the variables in Definition 2.1:

* $\zeta_{uv}^s \in [0, |V_{anc}|] \forall (u, v) \in A$ equals to the number of anchors in the source subtree defined by the successor.

* $\zeta_{vu}^t \in [0, |V_{anc}|] \forall (u, v) \in A$ equals to the number of anchors in the sink subtree defined by the predecessor.

## ■ Definition 4.2: DIRANCONFLOW MILP constraints

In addition to the constraints in Definition 2.2:

An arc can be associated with a number of anchors in the subtree only if the arc participates into the connected graph:

$$ \zeta_{uv}^s \le y_{uv} |V_{anc}| \quad \forall (u, v) \in A \qquad (C17) $$

$$ \zeta_{vu}^t \le y_{uv} |V_{anc}| \quad \forall (u, v) \in A \qquad (C18) $$

The number of anchors in the trees with roots the source's successors equals the number of anchors in $G'$:

$$ \sum_{v \in V_{anc}} x_v - \sum_{(s,w) \in A} \zeta_{sw}^s = 0 \qquad (C19) $$

Symmetrically, the number of anchors in the trees with roots the sink's predecessors equals the number of anchors in $G'$:

$$ \sum_{v \in V_{anc}} x_v - \sum_{(u,t) \in A} \zeta_{tu}^t = 0 \qquad (C20) $$

### ▲ Warning

Find a better description?

$\zeta_{uv}^s$, respectively $\zeta_{uv}^t$, equals to the number of anchors in the source, respectively sink subtree
with root v:

$$ \sum_{(u,v) \in A} \zeta_{uv}^s - \sum_{(v,w) \in A} \zeta_{vw}^s = \begin{cases} x_v & \text{if } v \in V_{anc} \\ 0 & \text{otherwise} \end{cases} \quad \forall v \in V \setminus \{s\} \quad (C21) $$

$$ \sum_{(v,w) \in A} \zeta_{wv}^t - \sum_{(u,v) \in A} \zeta_{vu}^t = \begin{cases} x_v & \text{if } v \in V_{anc} \\ 0 & \text{otherwise} \end{cases} \quad \forall v \in V \setminus \{t\} \quad (C22) $$

A source arc is active if its successor is in a graph whether it participates into the source or into the sink anchor tree:

$$ y_{sv} \le \sum_{(u,v) \in A} (\zeta_{uv}^s + \zeta_{vu}^t) + \sum_{(v,w) \in A} (\zeta_{vw}^s + \zeta_{wv}^t) \quad \forall (s,v) \in A \quad (C23) $$

# 5 Anchor Connected Flow Problem

## ■ Problem 5.1: (ANCONFLOW) Anchor Connected Flow SAT problem

Given a subset of vertices $V_{anc} \subseteq V \setminus \{s, t\}$ we denote as anchors, each connected subgraph $G''_i = (V_i, A_i)$ of the strict flow network $G''$ contains at least one anchor.

ANCONFLOW is using the logics of CONINTFLOW to describe anchor trees. Each active anchor defines the root of an anchor tree, and each active vertex is in (only) one anchor tree. To simplify, we can not consider the source and the sink vertices in the anchor trees.

## ■ Definition 5.1: ANCONFLOW MILP variables

In addition to the variables in Definition 2.1:

* $\zeta_{uv} \in [0, |V|-2] \forall (u, v) \in E_{anc} = A_{anc} \cup A_{anc}^{rev}$ equals to the size of the anchor subtree with root v.

$$ - A_{anc} = \{(u, v) \in A \mid u \neq s \land v \neq t\} $$

$$ - A_{anc}^{rev} = \{(v, u) \mid (u, v) \in A \land u \neq s \land v \neq t \land v \notin V_{anc}\} $$

* $\gamma_v \in [0, |V|-2] \forall v \in V_{anc}$ equals to the size of the anchor tree with root v.

## ■ Definition 5.2: ANCONFLOW MILP constraints

In addition to the constraints in Definition 2.2:

An arc, or its reverse, can participate in one anchor tree if it is active:

$$ \zeta_{uv} \le y_{uv} |V| \quad \forall (u, v) \in A_{anc} \quad (C24) $$

$$ \zeta_{uv} \le y_{vu} |V| \quad \forall (u, v) \in A_{anc}^{rev} \quad (C25) $$
<figure><img src="image_26.png" /><figcaption>(a) Flow</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(b) Tree</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(c) Source anchor tree</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(d) Sink anchor tree</figcaption></figure>

■ Figure 3 – Directed anchor connected flow examples

All the arcs have a capacity of 10, except for the source and the sink arcs where the capacity is unbounded. Vertices with a double cycle border are anchors (B and E). Dashed vertices and arcs do not participate in the solutions. (a) The flow values on the arcs are in blue. Because the source arc (S, F) can only describe a subgraph containing no anchors, no flow value can pass through it. (b) The green arc values correspond to the $\beta$ variables non-zero values. (c) respectively (d) The red arc values correspond to the $\zeta^s$, respectively $\zeta^t$, variables non-zero values. The arcs in (d) are reversed to better illustrates the tree structure with root the sink T. Here we observe that the source anchor tree in (c) does not able to pass a flow on the source arc (S, C). This illustrates the need of the sink anchor tree in (d).
<figure><img src="image_30.png" /><figcaption>Figure 4 – Anchor connected flow examples</figcaption></figure>

All the arcs have a capacity of 10, except for the source and the sink arcs where the capacity is unbounded. Vertices with a double cycle border are anchors (A and F). Dashed vertices and arcs do not participate in the solutions. (a) The flow values on the arcs are in blue. Because vertex D is connected to no anchors, the flow cannot pass through its arcs, while vertex C is (weakly) connected to anchor A, so it can be active. (b) The green arc values correspond to the $\beta$ variables non-zero values. (c) The red arc values correspond to the $\zeta$ variables non-zero values. They describe two anchor trees: one with root A and one with root F. Here arc (C, B) is reversed in the anchor tree in order to satisfy the (weakly) connectivity of vertex C with the anchor A, so that C can be active. The same behaviour is observed for arc (E, F). The difference between DIRANCONFLOW and ANCONFLOW is that in the first problem, vertex E would be able to be active but not vertex C as there is no directed walk connecting C to A.

Variable $\gamma_v$ equals to the size of the anchor tree with root v:

$$ \gamma_v - \sum_{(v,w) \in E_{anc}} \zeta_{sw} = x_v \quad \forall v \in V_{anc} \qquad (C26) $$

<figure><img src="image_31.png" /></figure>

### Warning

Find a better description?

Variable $\zeta_{uv}$ equals to the size of the anchor subtree with root v:

$$ \sum_{(u,v) \in E_{anc}} \zeta_{uv} - \sum_{(v,w) \in E_{anc}} \zeta_{vw} = x_v \quad \forall v \in V \setminus (V_{anc} \cup \{s, t\}) \qquad (C27) $$

Variables $\gamma_v$ cover all the active vertices (except s and t):

$$ \sum_{v \in V_{anc}} \gamma_v = \sum_{v \in V \setminus \{s, t\}} x_v \qquad (C28) $$
# 6 Optimization problem examples

## To-do

Complete this section.

## Definition 6.1: Maximum Vertex Weight Usage MILP constraints

<figure><img src="image_32.png" /></figure>

### New feature

New constraint

The vertex incoming flow cannot exceed the vertex capacity:

$$ \sum_{(u,v) \in A} f_{uv} \le \omega_v \quad \forall v \in V \setminus \{s,t\} \qquad (1) $$

## Definition 6.2: MILP objective function

One objective function can be:

$$ \max \mathrm{VertexWeightUsage} \qquad (2) $$

$$ \text{where } \mathrm{VertexWeightUsage} = \sum_{v \in V \setminus \{s,t\}} \left( 2 \frac{\sum_{(u,v) \in A} f_{uv}}{\omega_v} - 1 \right). $$

## References

[Dia+22] Fernando H. C. Dias et al. 'Fast, Flexible, and Exact Minimum Flow Decompositions via ILP'. In: Research in Computational Molecular Biology. Ed. by Itsik Pe'er. Vol. 13278. Cham: Springer International Publishing, 2022, pp. 230-245. ISBN: 978-3-031-04748-0 978-3-031-04749-7. DOI: 10.1007/978-3-031-04749-7_14. URL: https://link.springer.com/10.1007/978-3-031-04749-7_14 (visited on 08/03/2025).

[Man+21] Isja Mannens et al. 'On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem'. In: Graph-Theoretic Concepts in Computer Science. Ed. by Łukasz Kowalik, Michał Pilipczuk and Paweł Rzążewski. Cham: Springer International Publishing, 2021, pp. 52-79. ISBN: 978-3-030-86838-3.

[Man+23] Aniket Mane et al. 'PlasBin-flow: A Flow-Based MILP Algorithm for Plasmid Contigs Binning'. In: Bioinformatics 39 (Supplement_1 1st June 2023), pp. i288-i296. ISSN: 1367-4811. DOI: 10.1093/bioinformatics/btad250. URL: https://doi.org/10.1093/bioinformatics/btad250 (visited on 21/11/2024).
[Mat14] Dragan Matić. 'A Mixed Integer Linear Programming Model and Variable Neighborhood Search for Maximally Balanced Connected Partition Problem'. In: *Applied Mathematics and Computation* 237 (15th June 2014), pp. 85-97. ISSN: 0096-3003. DOI: 10.1016/j.amc.2014.03.098. URL: https://www.sciencedirect.com/science/article/pii/S0096300314004603 (visited on 26/03/2025).

[Miy+21] Flávio K. Miyazawa et al. 'Partitioning a Graph into Balanced Connected Classes: Formulations, Separation and Experiments'. In: *European Journal of Operational Research* 293.3 (16th Sept. 2021), pp. 826-836. ISSN: 0377-2217. DOI: 10.1016/j.ejor.2020.12.059. URL: https://www.sciencedirect.com/science/article/pii/S0377221720311218 (visited on 26/03/2025).

[TSP24] Kerian Thuillier, Anne Siegel and Loïc Paulevé. 'CEGAR-Based Approach for Solving Combinatorial Optimization Modulo Quantified Linear Arithmetics Problems'. In: *Proceedings of the AAAI Conference on Artificial Intelligence* 38.8 (8 24th Mar. 2024), pp. 8146-8153. ISSN: 2374-3468. DOI: 10.1609/aaai.v38i8.28654. URL: https://ojs.aaai.org/index.php/AAAI/article/view/28654 (visited on 08/03/2025).
# A Tutorial: ConFlow from primal-dual SAT

## ⚠ Warning

I have put previous formulation here to not have to redo.

## ✏ Fix-me

The whole section has to be rewritten.

## ■ Definition A.1: CONFLOW MILP variables

In addition to the variables in Definition 1.5:

* $x_v \in \mathbb{R}_{\ge 0} \forall v \in V$ denoting whether the vertex $v$ is active or not. With the constraints it acts as a binary.

* $y_a \in \{0, 1\} \forall a \in A$ denoting whether the arc $a$ is active or not.

* $\alpha_s \in \mathbb{R}$ acts as the number of vertices in the solution connected graph.

* $\beta_a \in \mathbb{R}_{\le 0} \forall a \in A$ is strictly negative if the arc $a$ participates in the solution graph exploration tree. It acts as a negative integer, where the absolute value corresponds to the number of vertices in the subtree with root the successor.

## ■ Definition A.2: CONFLOW MILP constraints

In addition to the constraints in Definition 1.6:

A positive flow activates the corresponding arc:

$$f_a \le cap(a)y_a \quad \forall a \in A \qquad (3)$$

An arc is active only if there is a positive flow on it:

## ⚠ Warning

Give an example why this is necessary (because of loops).

$$y_a \le \frac{1}{\epsilon_F} f_a \quad \forall a \in A \qquad (4)$$

where $\epsilon_F > 0$ is the minimum positive flow amount.

An active arc activates the incident vertices:

$$y_{uv} \le x_u \quad \forall (u, v) \in A \qquad (5)$$

$$y_{vu} \le x_v \quad \forall (u, v) \in A \qquad (6)$$
### Question

Given the previous constraint: is forcing s to be in the connected component necessary?

The source is in the connected component:

$$x_s = 1 \qquad (7)$$

### Question

Is the following constraint necessary? Can be redundant to Equations (5) and (6)?

A positive flow implies the two incident vertices are in the component:

$$x_u - x_v \leq 1 - y_{uv} \quad \forall (u, v) \in A \qquad (8)$$

The number of vertices in the trees with roots the source's successors at least equals the number of vertices in $G'$ minus the source:

$$\alpha_s + \sum_{(s,w) \in A} \beta_{sw} \leq 1 \qquad (9)$$

### Warning

Find a better description?

$|\beta_{uv}|$ is at least equals to the number of vertices in the subtree with root u:

$$\sum_{(v,w) \in A} \beta_{vw} - \sum_{(u,v) \in A} \beta_{uv} \leq 1 \quad \forall v \in V \setminus \{s\} \qquad (10)$$

An arc can participate in the tree only if it participates into the connected graph:

$$\beta_a \geq -y_a|V| \quad \forall a \in A \qquad (11)$$

### Question

Perhaps we can simplify by not introducing a new variable, and directly replace $\alpha_{\text{alpha}}$ in the constraints?

$\alpha_s$ is the number of active vertices (SAT constraint):

$$\alpha_s = \sum_{v \in V} x_v \qquad (12)$$
Question

Can we make $y_A$ variables in $[0, 1]$?