Find cycles with fixed number of edges without shared vertices in a directed graph

Question

I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, 10, 15, and 20 edges (so the edge number of each cycle is fixed), such that no vertices in each cycles would be the same (or each vertice can be included in at most one cycle), and the sum of weights on all selected edges should be minimised. Note that for each user, the weight on each edge is different (weight is non-negative), and self-loop is prohibited.

I find it difficult to solve the problem directly, so I formed a binary integer linear programming problem as attached, where $W^u_{i,j}$ is a non-negative constant for each edge ($i,j$) of each user $u$, and $X^u_{i,j}$ are binary varibles $\{0 , 1\}$, constraint 1 specifies flow conservation, constraint 2 is edge number constraint of each cycle, constraint 3 is to specify that each vertice is used by at most 1 user and each vertice can only have one outgoing flow.

BILP problem

Any idea to solve this problem in its original graph form or the optimization problem plz? I trid to use Mosek and Lingo to solve the BILP problem, it works fine for a small scale problem. But it takes a ridiculous amount of time to solve large scale problem. Any idea on problem decomposition ? Many thanks.

Answer 1

Here are three alternative approaches, with varying degrees of both performance and implementation effort:

1. Enumerate all directed cycles with the prescribed lengths and solve a set partitioning problem with a binary variable for each cycle and a constraint that each user selects exactly one cycle.
2. Same as the previous approach, but generate the directed cycles dynamically via column generation with an optimal cardinality-constrained subtour subproblem for each user.
3. Use an arc-based formulation with a binary variable for each arc-user pair, flow balance constraints, a cardinality constraint for each user, a set packing constraint for each node, and dynamically generated no-good constraints that prevent subtours for the same user. This is similar to what you proposed, but your formulation mistakenly allows, for example, the solution for user 2 to consist of a node-disjoint union of a 3-cycle and a 7-cycle.