# Flow problem with side constraints: how to eliminate subtours?

I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the problem "hard", as the classic formulation for flows may leed to subtours.

The structure of my graph is such that the subtours can only have an even number of arcs larger than 4. So if I impose that I have exactly 5 arcs, with one leaving the source, and one entering the sink, I eliminate solutions with subtours.

I am interested in solutions with 7 arcs, and am trying to come up with a "simple" constraint (no MTZ constraints, nor typical subtour elimination constraints from the TSP, nor no-good cuts) that eliminates solutions with a subtour of 4 arcs, and a path from source to sink with 2 intermediate nodes.

Any ideas ?

For more clarity, here is an example of a solution that I would like to eliminate (the blue triangle indicates that I need a unit of flow on this arc): And here is a valid solution with 7 arcs: Let $$S$$ be the set of arcs in a subtour of size $$4$$. No-good cuts are simple but weak: $$\sum_{(i,j)\in S} x_{ij} \le 4 - 1$$
Depending on the objective, you might get by with instead imposing no-good cuts for $$3$$-arc paths $$P$$ that start at the head of a forced arc and end at the tail of that same forced arc: $$\sum_{(i,j)\in P} x_{ij} \le 3 - 1$$
For comparison, note that generalized subtour elimination constraints (GSEC), which you explicitly wanted to avoid, would cut off $$(4-1)!$$ subtours (instead of just $$1$$) at a time.
• Sorry, I may have been unclear, I do not want no-good cuts either. I was hoping I could find a constraint similar to the one for solutions with 5 arcs ($\sum_{i,j}x_{ij}\le 5$). Something that structurally characterizes a valid solution. Sep 15, 2022 at 12:42
• The number of GSECs is $O(n^4)$ (polynomial, not exponential) if your graph has $n$ nodes and you restrict to subtours of length $4$. Sep 15, 2022 at 13:17