Circulation problem: Difference between revisions

Revision as of 23:21, 5 October 2008

Revision as of 23:23, 5 October 2008

Line 6:

:{|

| <math>\,l(u,v,w)</math> || Lower bound on flow from node <math>uv</math> to node <math>vw</math>.

|-

| <math>\,u(u,v,w)</math> || Upper bound on flow from node <math>uv</math> to node <math>vw</math>.

|-

| <math>\,c(u,v,w)</math> || Cost of a unit of flow on <math>(u,v,w)</math>.

|}

Line 16:

:{|

| <math>\quad l(uv,vw) \leq f(uv,vw) \leq u(uv,vw)</math>

|-

| <math>\ \sum_{w \in V} f(u,w) = 0</math> || Flow cannot appear or disappear in nodes.

Line 25:

In the minimum cost variant of the problem, minimise

: <math>\sum_{(u,v,w) \in E} c(u,v,w) \cdot f(u,v,w)</math>

=== Multi-commodity circulation ===

Line 32:

:{|

| <math>\,f_i(u,v,w)</math> || The flow of commodity <math>\,i</math> from <math>\,uv</math> to <math>\,vw</math>.

|-

| <math>\,f(u,v,w) = \sum_i f_i(u,v,w)</math> || The total flow.

|}