- Fact:
- A network flow problem can be easily formulated as a Linear Optimization problem (LP)
Therefore:
- One can use the Simpelx Method to solve a maximum network flow problem
- Network
Simplex Algorithm:
- The Linear Program (LP)
that is derived from
a maximum network flow problem
has a large number of constraints
- There is a
"Network" Simplex Method
developed just for
solving
maximum network flow problems
We will not cover this algorithm
If you want to learn more: click here
Look for: "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming 78: pages 109-129
- The Linear Program (LP)
that is derived from
a maximum network flow problem
has a large number of constraints
- Recall the general form of a
Linear Program:
max: c1x1 + c2x2 + ... + + cnxn s.t.: a11x1 + a12x2 + ... + + a1nxn ≤ b1 a21x1 + a22x2 + ... + + a2nxn ≤ b2 ... am1x1 + am2x2 + ... + + amnxn ≤ bm
- How to formulate
a max flow problem as
an LP:
- Introduce variables
to represent
flow over
each edge of the network
- Formulate the
capacity
constraints
and
conservation
constraints
- Add an
artificial feedback link from
sink → source
to represent the
totalflow
- The objective function of the LP is the total flow (over the artificial feedback link)
- Introduce variables
to represent
flow over
each edge of the network
- The key to convert
a max flow problem
into a Linear Program is
the use of:
- Flow variables
- Flow variable:
how much flow over a link:
xij = amount of flow from i → j
- Example:
- Consider the following basic network:
- In order to formulate
the max flow problem as an LP,
we will need to introduce the following
flow variables:
x01 x02 x03 x14 x15 x24 x25 x26 x35 x47 x57 x67
- Consider the following basic network:
- There are 2 types of
constraints in a basic network
- Capacity constraints
- Flow conservation constraints
- Capacity constraints
- Capacity constraints:
- The flow over
any lonk
cannot exceed
the capacity of that link
- ∀ link e: f(e) ≤ c(e)
- The flow over
any lonk
cannot exceed
the capacity of that link
- Example:
given basic network
- Flow capacity constraints:
x01 ≤ 3 x02 ≤ 2 x03 ≤ 2 x14 ≤ 5 x15 ≤ 1 x24 ≤ 1 x25 ≤ 3 x26 ≤ 1 x35 ≤ 1 x47 ≤ 4 x57 ≤ 2 x67 ≤ 4
- Flow conservation constraints:
- The flow conservation constraint
is valid
for nodes
other than the
source S and
sink T !!!
- Total flow flowing
into a node =
Total flow flowing
out of a node
- ∀ node n (n ≠ S and n ≠ T): ∑(flow into n) = ∑(flow out of n)
- The flow conservation constraint
is valid
for nodes
other than the
source S and
sink T !!!
- Example:
- Flow conservation constraints:
node 1: x01 = x14 + x15 node 2: x02 = x24 + x25 + x26 node 3: x03 = x35 node 4: x14 + x24 = x47 node 5: x15 + x25 + x35 = x57 node 6: x26 = x67
- The objective is to
maximize the flow
from source node 0 to
sink node 7
- Direct Method:
- Objective function = sum of all flows eminating from the source S
Example:
Objective function:
max: x01 + x02 + x03
- Example Program:
(Demo the lp_solve code)
- lp_solve input file: click here
How to run the program:
- Right click on link(s) and
save in a scratch directory
- To run: lp_solve lp2
Output:
Value of objective function: 6.00000000 Actual values of the variables: x01 3 x02 2 x03 1 x14 3 x15 0 x24 1 x25 1 x26 0 x35 1 x47 4 x57 2 x67 0
Corresponding max flow:
- The following is a
popular way to
introduce
the objective function:
- We introduce an
artificial flow
from
sink T back to
source S:
I.e.:
- We make a closed network
- We can now add the following
flow conservation constraints
to the
source S and
the
sink T:
flow into source = flow out of source: x70 = x01 + x02 + x03 flow into sink = flow out of sink: x47 + x57 + x67 = x70
- The objective function
is simply:
max: x70(Note: x70 = x01 + x02 + x03 --- so we are not doing anything different....)
- We introduce an
artificial flow
from
sink T back to
source S:
- Resulting Linear Program:
max: x70 s.t.: x01 - x14 - x15 = 0 x02 - x24 - x25 - x26 = 0 x03 - x35 = 0 x14 + x24 - x47 = 0 x15 + x25 + x35 - x57 = 0 x26 - x67 = 0 x70 - x01 - x02 - x03 = 0 x47 + x57 + x67 - x70 = 0 x01 ≤ 3 x02 ≤ 2 x03 ≤ 2 x14 ≤ 5 x15 ≤ 1 x24 ≤ 1 x25 ≤ 3 x26 ≤ 1 x35 ≤ 1 x47 ≤ 4 x57 ≤ 2 x67 ≤ 4
- Example Program:
(Demo above code)
- lp_solve input file: click here
How to run the program:
- Right click on link(s) and
save in a scratch directory
- To run: lp_solve lp1
- Solution:
>> lp_solve lp1 Value of objective function: 6.00000000 Actual values of the variables: x70 6 x01 3 x14 3 x15 0 x02 2 x24 1 x25 1 x26 0 x03 1 x35 1 x47 4 x57 2 x67 0