Network-Type Problems

Network-Type Problems

Professor: Farid Alizadeh

Scribe: Shuguang Liu

Lecture Date: December. 3 1998

Last week we have addressed the formulation of Network flow problem and introduced spanning tree to form solution basis of it. This time we go further to find an initial feasible solution and give a method to find the optimal solution. After that, we will discuss briefly other network-type problems.

1 Network flow model

We state the model from previous class here:

By denoting above model as AX=b, we have:

1)Matrix A is the node-arc incidence matrix of the network and is a n by m matrix

2)Matrix A is singular

3)There is a spanning tree of the undirected network graph corresponding to a basic solution

By removing any one redundant equation, we get a new system and a new matrix A:. Now,

1)The new A matrix corresponding a

2)The new matrix A corresponds to a cycle, which has linearly dependent columns

3)(n-1) columns of new A that forms a non-singular matrix ((n-1) by (n-1)) corresponds to a spanning tree

1.1 Finding an initial feasible solution

By using a spanning tree we can solve a system of equations to get an initial solution.

For example:

A spanning tree:

Notes: The first number of two numbers in an ellipse denotes the number of nodes; the second the demand of this nodes.

The corresponding system of equations:

The easy way to solve this system is to first find equation with only one variable; that is finding a leaf in the corresponding spanning tree.

We get the solution. But it is not feasible, because it violates the nonnegative constraints.

In fact, we need a procedure like phase 1 in the simplex method to get a feasible solution. This procedure can be described shortly as follows:

Find a node receiving from all supplying nodes and sending to all other non-supply nodes. If we can not find a qualified node, we can pick up a node and construct arcs sending from all supplying nodes to this node or sending from this node to other non supply nodes.

Then we solve the problem corresponding to this spanning tree. If this problem does not have zero objective value (cost), then the original problem is infeasible. If it does, we can obtain a feasible solution.

1.2 Using dual cost tree to find optimal solution

Dual problem of minimum network flow problem:

As to above system, we know that primal problem has n-1 nonbasic v

Suppose we have an initial primal flow solution:

The dual cost solution:

From dual cost solution, check the optimality of primal problem:

We see that arc 14 does not satisfy optimality, so this arc should enter into the spanning tree, which corresponds to a nonbasic variable. Now by adding arc 14 in primal flow tree, we have a cycle. In this cycle we need to drop an arc to retain a spanning tree. Here we back to primal flow tree:

From above, we set t=9. Then the whole primal flow tree:

Dual cost tree:

Check for optimality. All the arcs, which are off the spanning tree, satisfy the inequalities. So, we find the optimal solution.

2. Shortest path problem

In this section, we seek the shortest paths from a source to all other nodes in a network.

A label-setting algorithm

Label notes starting from the source node by (node, distance).

Step 1: label source node:

Step 2: separate labeled nodes from unlabeled nodes. And label node that has the shortest distance from separated labeled notes set.

Keep doing step2 until all nodes have been labeled.

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

Step 9:

Finally, we get the solution.

(s, a)=6

(s, b)=8

(s, c)=24

(s, d)=30

(s, e)=20

(s, f)=37

(s, g)=26

(s, h)=33

3 Maximum flow problem

Maximum flow problem is an another special type of network flow problem. This problem can be stated as follows:

Suppose we have a network, which has one supplying node and one demanding node, and the others are intermediate nodes. The objective is to push as much flow from the supplying node to demanding node as possible. And the capacities of the arcs connecting these nodes are not infinite (they are upper bounded).

We can construct this problem by introducing a dummy arc from demanding node t to supplying node s, and assuming cts negative (here it is set to -1). At the same time, we let all cij=0 (the cost of transporting through arc ij), and let all the demands of all nodes to be zero (bI=0).

Now since the only nonzero cost of the network is negative, we can transfer as much flow as possible from demanding node t to supplying node s, in order to get maximum profit.

Now the model is as follows: