5
$\begingroup$

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):

enter image description here

And here is a valid solution with 7 arcs:

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Sep 15, 2022 at 12:42
  • $\begingroup$ The only reason I want to avoid GSEC is to avoid adding an index, and avoid having an exponential number of constraints. $\endgroup$
    – Kuifje
    Sep 15, 2022 at 12:46
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Sep 15, 2022 at 13:17
  • $\begingroup$ True, why not, its worth a try! (although not as good as the single constraint I was hoping for) $\endgroup$
    – Kuifje
    Sep 15, 2022 at 13:26

Your Answer

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

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