3
$\begingroup$

For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just deleting edges)?

$\endgroup$
8
$\begingroup$

I believe you can represent node N as two nodes, A and B. Node A has all of the inbound flow edges of N, and Node B has all of the outbound flow edges of N. Nodes A and B are connected by a single edge which you can use to throttle the flow. The edge from A to B is the only edge out of A and the only edge into B.

$\endgroup$
  • $\begingroup$ This is possible, but you can achieve the same thing by summing over the set of arcs that lead to each node (or, similarly, the arcs that leave a given node). $\endgroup$ – Dylan Black Apr 3 '17 at 8:56
  • $\begingroup$ @DylanBlack while you can add additional constraints as you propose in your answer, the problem is then no longer solvable as a minimum cost flow problem. These flow problems can be solved by the efficient Network Simplex method (en.wikipedia.org/wiki/Network_simplex_algorithm) in polynomial time, while general MIP is NP-hard. $\endgroup$ – Fasermaler Apr 3 '17 at 9:36
  • 1
    $\begingroup$ @Fasermaler, thanks for the comment. My answer introduces integer variables, but this comment does not. If you want to restrict the flow through an arc, you are free to do so. I haven't come across a network-specific version of simplex before, but you can still implement the answer provided without introducing new nodes. A constraint on the flow variables $F_{i,j}$ can be introduced such that $\sum_{i} F_{i,j} \leq 1 $ where $i,j$ are arcs leading to $j$. Please correct me if I'm wrong! $\endgroup$ – Dylan Black Apr 3 '17 at 10:48
  • $\begingroup$ @DylanBlack you're not wrong, your answer/comment will work I think. My point is that by adding your constraint (no matter how valid), this is no longer a min cost flow problem (en.wikipedia.org/wiki/Minimum-cost_flow_problem) and it is no longer guaranteed to be solvable in polynomial time. With Matthew's answer you get to restrict flow and keep this guarantee, giving you an integer solution in polynomial time, which is somewhat magical. $\endgroup$ – Fasermaler Apr 6 '17 at 8:51
  • $\begingroup$ Interesting point. How can you be sure the answer will be integer? This answer only ensures that the maximum flow through the "node" is less than or equal to one. Unless formulated as an integer program, you can't guarantee that all flows along all arcs will be integer values. $\endgroup$ – Dylan Black Apr 6 '17 at 10:05
3
$\begingroup$

If you have represented this as a MIP you can restrict the flow to be on only one arc. Are you currently representing this as a linear program?

You can introduce a binary variable for each arc, $X_{i,j}$, and for each location $j$ you can introduce the constraint $$\sum_i X_{i,j} \leq 1 $$ where nodes i lead to node j. A similar constraint is required for the flow out of each node.

If you wish to solve as a linear program, you cannot restrict the flow to be on only one arc (though your objective function may achieve this) but you may restrict the total flow through a node by introducing a flow variable $F_{i,j}$ and restricting the sum over arcs that lead to node $j$: $$\sum_i F_{i,j} \leq 1 $$ where nodes i lead to node j.

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