7
$\begingroup$

Since max flow formulation can be easily solved using LP, I wanted to ask the following:

I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The constraint is that the flow from any supply node '$a$' should not be split, i.e. suppose I have a supply at node '$a$' of 4 units and have arcs $(a,x)$, $(a,y)$, and $(a,z)$, then the entire 4 units of supply should go through one and only one arc.

Is there an LP formulation for this? I can model it using integer variables....

$\endgroup$
  • 5
    $\begingroup$ this "all-or-nothing" constraint makes the problem hard, so there is no hope (in the complexity theory sense) that there is a reasonable LP formulation for this. $\endgroup$ – Marco Lübbecke Dec 4 '19 at 18:06
4
$\begingroup$

If you define binary variables for each of the arcs let's say $$m_{ij} \ \ \forall i\in \text{supply}\ \ \text{and} \ \ j \in \text{demand}$$ then you can add the following constraint to the model: $$\sum_j m_{ij} = 1$$ and the shipment then can be limited as the following ($M$ is a large number to relax $s_{ij}$ if necessary): $$s_{ij} \le M \cdot m_{ij}$$ In this formulation $s_{ij}$ is still continuous variable

$\endgroup$
3
$\begingroup$

Add binary variables $y_{ai}$ and the following constraints: \begin{align} y_{ax}+ y_{ay} + y_{za} &\le 1\\ x_{ai} &\le 4 y_{ai} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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