3
$\begingroup$

I cannot find references for a Minimum Disjointed Path Cover ILP formulation.

Given a directed graph G=(V,A), a disjointed path cover is a path cover with no common nodes between paths. We want to find a path cover with the minimum number of paths.

My idea is to count nodes with no entering edges as the number of paths. That is $$z = \sum_{u \in V} \big(1 - \sum_{v \in V} x_{uv}\big)$$

Then we can add degree constraints $$\sum_{ (u,v) \in A}x_{uv} \leq 1 \ \ \ \forall u \in V$$ $$\sum_{ (v,u) \in A}x_{vu} \leq 1 \ \ \ \forall u \in V$$

And then subtour elimination constraints: $$\sum_{ (u,v) \in S}x_{uv} \leq |S|-1 \ \ \ \forall S \subseteq A |\ S\textrm{ is a cycle}$$

with binary vars that select edges $$x_{uv} \in \{ 0,1 \} \ \ \ \forall (u,v) \in A$$

I don't know how to properly break cycles except by manually checking them.

$\endgroup$

3 Answers 3

4
$\begingroup$

Here's a compact, MTZ-based formulation. In addition to your binary $x_{ij}$ variables, introduce binary variables $s_i$ and $t_i$ to indicate whether node $i$ is a source or sink, respectively. (A source is a node with no entering arcs, and a sink is a node with no leaving arcs.) Also let $u_i\in[0,|V|-1]$ be the MTZ variable that represents when node $i$ is visited. The problem is to minimize $\sum_{i\in V} s_i$ subject to \begin{align} \sum_{(i,j) \in A} x_{ij} - \sum_{(j,i) \in A} x_{ji} &= s_i - t_i &&\text{for $i \in V$} \tag1\label1 \\ \sum_{(i,j) \in A} x_{ij} + t_i &= 1 &&\text{for $i \in V$} \tag2\label2 \\ u_i - u_j + 1 &\le |V| (1 - x_{ij}) &&\text{for $(i,j) \in A$} \tag3\label3 \end{align} Constraint \eqref{1} enforces flow balance. Constraint \eqref{2} covers every node exactly once. Constraint \eqref{3} prevents subtours by enforcing the logical implication $x_{ij}=1 \implies u_i < u_j$.

If $(j,i)\in A$, you can strengthen \eqref{3} by lifting: $$u_i - u_j + 1 \le |V| (1 - x_{ij}) - (|V|-2)x_{ji}$$

$\endgroup$
3
$\begingroup$

Two more alternative solution approaches:

Approach 1 - convert problem to Vehicle routing problem.

Add a dummy vertex to the graph representing the depot. Add outgoing and incoming arcs from/to the depot to every other vertex. Solve the problem as a vehicle routing problem. When solving the VRP, minimize the number of routes ($K$) instead of the total arc cost. Once a solution is obtained, remove the depot and the resulting paths form a Minimum disjoint path cover. Note that, when solving the VRP, you can simply separate the stronger DFJ subtour constraints, so you don't have to rely on the MTZ constraints.

Approach 2

Construct an auxiliary undirected graph $G'$ as follows. For every vertex $i\in V$ in $G$, add two vertices $i^1$ and $i^2$ to $G'$. For every arc $(i,j)\in A$ in graph $G$, add undirected edge $(i^1,j^2)$ to $G'$. A Minimum disjoint path cover can now be found by solving a maximum matching in $G'$. Proof: see Chapter 11 of the book 'Algorithms' by Jeff Erickson.

To solve the max matching problem, you could use a MIP formulation, but in general a dedicated algorithm for the max matching problem is significantly faster(see: Dimitrios, Kinable, et al. 2020. JGraphT—A Java Library for Graph Data Structures and Algorithms. ACM Trans. Math. Softw. 46, 2.).

Final remark: if the input graph is a Directed Acyclic Graph (DAG), you can obtain the desired cover by solving a minimum flow problem.

$\endgroup$
1
  • 2
    $\begingroup$ +1 for VRP. To minimize the number of routes, you can use arc cost 1 out of the depot and 0 otherwise. $\endgroup$
    – RobPratt
    Oct 23, 2022 at 5:13
2
$\begingroup$

I like the MTZ formulation, so I vote for Rob's model. That said, MTZ is sometimes a bit weak, hurting solution speed. So here are a couple of other possibilities (which I personally would try only if MTZ let me down).

In the original formulation proposed, you can either add subtour elimination constraints for all possible cycles up front (practical only for really small graphs) or, if your solver supports callbacks, use a callback to inspect each candidate incumbent for any cycles and, when found, add the corresponding subtour elimination constraints (a "one tree logical Benders" approach).

Benders is basically a "row generation" approach. You can also use column generation. Let $\mathcal{N}$ and $\mathcal{P}$ be respectively the set of all nodes and the set of all paths in the graph, let $\hat{\mathcal{P}}\subseteq \mathcal{P}$ be some set of known paths, and let $a_{np}$ be 1 if node $n$ is on path $p$ and 0 if not. Our master problem is \begin{align*} \min\sum_{p\in\hat{\mathcal{P}}}x_{p}\\ \textrm{s.t. }\sum_{p\in\hat{\mathcal{P}}}a_{np}x_{p} & =1\quad\forall n\in\mathcal{N}\\ x_{p} & \in\left\{ 0,1\right\} \quad\forall p\in\hat{\mathcal{P}} \end{align*} where $x_p$ is an indicator for whether we use path $p$ and the lone constraint says that every node lives on exactly one chosen path. For a small graph, you can enumerate $\mathcal{P}$ manually, set $\hat{\mathcal{P}}=\mathcal{P},$ solve once and be done. For larger graphs, you can get an exact solution using branch-price-and-cut (starting with some arbitrary set $\hat{\mathcal{P}}$ of paths sufficient to get a feasible solution and generating new paths on the fly in a pricing problem) or a heuristic solution by solving the LP relaxation of the master problem, using the dual values for the equation constraints to set prices in a path generating subproblem (looking for a path with a negative reduced cost in the master), adding any such path found to the master, and repeating until you don't find any more attractive paths. At that point, you restore integrality, solve the now IP master problem one last time, and hope for the best.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.