7

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....

EhsanK
  • 5,864
  • 3
  • 17
  • 54
prakash gawas
  • 173
  • 4
  • 5
    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. – Marco Lübbecke Dec 04 '19 at 18:06

2 Answers2

4

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}

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Kuifje
  • 13,324
  • 1
  • 23
  • 56
4

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

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Oguz Toragay
  • 8,652
  • 2
  • 13
  • 41