OPTIMIZATION 3A GI

Chapter 1 Introduction to Network Programming

1.1 Introduction
Network programming is a field of mathematics, which constitutes one of the most
used instruments for solving a wide class of discrete optimization problems in the
domain of operations research. A network allows for representing, in a simple way, a
variety of problems. Generally, network programming is a tool for modeling problems
involving connections or transshipment in complex systems, through the expression of
the relations that exist between its components. Examples of applications include
transportation networks and communication networks.

Networks can also be used to model problems which do not appear to have a link to
physical networks, such as project scheduling, where nodes of a the networks
represent activities and the arcs represent the precedence relations between the
activities. Other examples include production and inventory planning, resource
management and financial planning.

We distinguish 5 major classes of network problems:

1. Shortest path (or chain),
2. Minimum cost spanning tree,
3. Maximum value flow,
4. Minimum cost flow,
5. Project scheduling: CPM and PERT.

Example:
Consider an amusement park with O as the entrance and T the tramway station.
Pb 1: shortest chain problem to go from O to T.
Pb 2: minmum spanning tree: design an electrical network using minimal cable
length.
Pb 3: maximum flow: transport the maximum of tramways from O to T.

3
OPTIMIZATION 3A GI

7
A
2 D 5
2 4
5
O B 3 1 T

1
E 7
4 C
4

Figure 1.1: Examples

1.2 Definitions and basic concepts

1.2.1 Networks
A network, G, is defined by:
ƒ A set N of points, also called vertices or nodes ;
ƒ A set A ⊂ N ×N of lines, called arcs, each joining a pair of nodes together with
some associated data. Nodes i and j are said to be adjacent if there is a line
joining them. Two lines are said to be adjacent if they share at least one
node.
The network is denoted G=(N, A).
Let ⏐N⏐= n: the number of nodes in G ; Then G is said to be of order n.

1.2.2 Arcs and directed networks

A line joining i and j that can only be used in the direction from i to j is called an arc,
and denoted by the ordered pair (i, j). It is incident out of i and into j. The arc (i,j)
has i as its tail and j as its head. If the arc is denoted by u=(i,j), then tail(u)=i and
head(u)=j. Graphically, the arc u is represented by an arrow:

u
i j

The node i is said to be a precedent or a predecessor of j ; and j is called a successor

of i. The set of successors of i is denoted by Γ(i) ; The set of predecessors of i is
denoted by Γ-1(i).

Rq: The arc (i,i) is called a loop.

4
OPTIMIZATION 3A GI

A line joining i and j that can be used either from i to j or from j to i is called an edge
and is denoted by the unordered pair (i;j). It is incident at i and j.
A network is said to be directed if it contains only arcs. It is undirected if all its lines
are edges.

The degree of a node i d(i) is the number of lines (arcs or edges) incident at it. In a
directed network, the indegree d-(i) (outdegree d+(i) ) of a node is the number of arcs
incident into (out of) it. We have then: d(i) = d+(i) + d-(i)

Rq: d-(i) = |Γ-1(i)| and d+(i) = |Γ(i)|.

A p-Network is a network in which there exist at most p lines between any pair of
nodes.

For a 1-network, G can be perfectly determined by the set of nodes and the set of
successors of each node.

1.2.3 Chains and Paths

A chain linking two nodes i1 (origin) and ik (destination) in G is a sequence of nodes
and lines alternately i1, u1, i2, u2, …, uk-1, ik, such that for each r=1 to k-1, ur is either
the arc (ir, ir+1) or the arc (ir+1, ir), or the edge (ir ; ir+1), with some orientation
selected for it. In the network represented in Figure 1.2, the arcs (A, B), (B, D) and
(E, D) constitute a chain from A to E.
An arc whose orientation coincides with (is opposite to) the direction of travel from
origin to destination is called a forward (reverse) arc of the chain.

A path is a chain which all the arcs are forward arcs. In Figure 1.2, the arcs (C, A), (A,
B) and (B, D) constitute a path from C to D.

5
OPTIMIZATION 3A GI

B
D

E
C

Figure 1.2 : Example of chains and paths

The length (or cardinality) of a chain or a path is the number of its arcs.
Rq: It is important to note that, in some references, the definitions of path and chain
are reversed.

1.2.4 Cycles and Circuits

A cycle (circuit) is a chain (path) whose end nodes coincide.
In Figure 1.2, the arcs (C, B), (B, D), (E, D) et (C, E) form a cycle; and the arcs (A, B),
(B, C) et (C, A) form a circuit.

1.2.5 Connected nodes and networks

Two nodes are said to be connected if the corresponding network contains at least
one chain linking them.
A network G is said to be connected (strongly connected) if there exists a chain (a
path) between every pair of nodes in it.

B
D

E
C

Figure 1.3: Example of a non connected network

1.2.6 Subnetworks and partial networks

A subnetwork of G = (N, A) is a network F = (N, A ) with the same set of nodes, but
with A ⊂ A. For example, If G is the network representing all the routes in Tunisia,
the network representing all the routes in the north of Tunisia is a subnetwork.

6
OPTIMIZATION 3A GI

1.3 Incidence and adjacency

To describe a network, a number of representations can be used. They are not all
equivalent with respect to algorithms’ efficiency.
There exist essentially two families of representations:
- Incidence matrices,
- Adjacency matrices.

1.3.1 Node-arc incidence matrix

The node-arc incidence matrix of a network G = (N, A) is the matrix E = (eij), i = 1, …,
n et j = 1,…, m=|A|, that has a row associated with each node in G, and a column
associated with each arc in G, and which coefficients are equal to 0, 1 or –1.

If u = (i, j) ∈ A, the column u has all its coefficients equal to zero except: eiu = +1 and
eju = -1.

Example:
The node-arc incidence matrix of the following network is given in Figure 1.4.

u1
1 2
u2 u4 +1 +1 0 0 0
u3 -1 0 +1 +1 0

4 3
0 -1 -1 0 +1
u5 0 0 0 -1 -1
Figure 1.4: Example of node-arc incidence matrix

1.3.2 Node-edge incidence matrix

The node-edge incidence matrix of a network G = (N, A) is the matrix E = (eij), i = 1,
…, n et j = 1,…, m, that has a row associated with each node in G, and a column
associated with each edge in G, and which cofficients are equal to 0 or 1.

7
OPTIMIZATION 3A GI

If u = (i, j) ∈ A, the column u has all its coefficients equal to zero except: eiu = +1 and
eju = +1.

Example:
The node-edge incidence matrix of the following network is:

u1
1 2 1 1 0 0 0
u2 u4
u3 1 0 1 1 0
0 1 1 0 1
4 3
0 0 0 1 1
u5

Figure 1.5: Example of node-edge incidence matrix

1.3.3 Node-Node adjacency matrix

The node-node incidence matrix of a network G = (N, A) is the matrix E = (eij),
i = 1, …, n and j = 1,…, n, that has one row and one column associated with each node
in G, and which coefficients are equal to 0 or 1.

In the case of an undirected network, we can define two arcs: (i,j) and (j,i) for each
edge (i ;j). In this case, the adjacency matrix is symmetric.

Example:
The node-node incidence matrix of the following network is:

u1
1 2 0 1 1 0
u2 u4
u3 0 0 1 1
0 0 0 1
4 3
0 0 0 0
u5

Figure 1.6: Example of node-node incidence matrix

8
OPTIMIZATION 3A GI

Chapter 2 The shortest path problem and its extensions

2.1 Introduction
Consider a directed network G = (N, A), with n nodes and m arcs. To each arc is
associated a real number cu called the length or weight of the arc u. If u = (i, j), the
arc length is denoted by cij. We define the length of a path as the sum of the lengths
of all its arcs.

The shortest path problem (SPP) consists of determining a path joining two given
nodes: an origin, or source S, and a destination, or sink T, with a minimal length.
The arc lengths may correspond to:
- distances,
- transportation costs,
- costs of constructing the arcs,
- travel times, …

The arc lengths can of arbitrary signs (+ or -). As a consequence, a path that contains
a circuit that has a strictly negative length is unbounded (as the cycle may be visited
an infinite number of times). A necessary condition for the existence of a shortest
path is the absence of circuits with negative lengths.

2.2 Applications

2.2.1 Equipment replacement problems

A mine having an exploitation horizon of T years uses specific expensive equipment.
At the first year, i = 0, a new equipment has to be purchased. At the beginning of
each year, there are two options: either keep the equipment during the year [i, i+1],
or trade it by reselling it for its salvage value v(x) where x est is the age of the
equipment (number of year it has been used), and buying a new equipment with a
cost of p(i). At the last year, T, the equipment in service has to be sold for its salvage
value. The annual operational cost, r(x), depends on the age of the equipment. The
values of p(i), v(x) et r(x) are supposed to be discounted to their present value at
year i = 0.

9
OPTIMIZATION 3A GI

The problem consists of finding a minimum cost equipment replacement.

We can show that this problem is equivalent to the shortest path problem in a
particular network. Let us define the network G = (N, A) as follows (see figure 2.1):
- A node is associated with each date, giving a total of T+1 nodes.
- An arc joins the nodes i and j if and only if i < j. This arc corresponds to the
decision of bying an equipment at year i and replacing it at year j.
- The length of each arc is the sum of purchasing and operational costs, from
which the selling price is subtracted :
cij = p(i) + ∑s=1,j-i r(s) - v(j-i)

0 1 2 T

Figure 2.1: Network associated with the equipment replacement problem

An optimal policy is given by the shortest path from 0 to T, in the constructed

network.

2.2.2 Replenishment optimisation

A company has to ensure the supply of a certain material during a horizon of T periods
in order to be able to execute its production plan. For each period t (t = 1, …, T) the
purchase cost p(t) is given.

In order to take advantage of price variabilities, the company may constitute a stock
of unused items for a cost of h(t) per unit during each period t. The company may
also backorder customer demands in the case of a shortage. However, in this case, a
penalty, µ per unit per period, has to be paid. We consider the problem of finding the
minimum cost supply (or replenishment) plan.

10
OPTIMIZATION 3A GI

We can show that this problem is equivalent to the shortest path problem in a
particular network. Let us define the network G = (N, A) as follows (see figure 2.2):
- N contains one particular node S and T nodes corresponding to each period;
therfore, a total of T+1 nodes.
- The node S is linked to each node t: the arc (S, t) is associated with the
decision of supplying the material at period t. The length of such arc is p(t).
- Each arc t (t = 1,…, T-1) is linked to the node t+1. An arc (t, t+1)
corresponds to the decision of storing during period t. The length of such
arc is h(t).
- Each arc t (t = 2,…, T) is linked to the node t-1. An arc (t, t-1) corresponds
to the decision of backorder during period t. The length of such arc is µ.

p(T)
p(1)
p(2) p(3)

1 2 3 T
h(1) h(2)
µ µ µ

Figure 2.2: Network associated with the replenishment optimisation problem

A path between S and t corresponds to a policy of supplying the material of period t.

Hence, an optimal supply policy can be found by determining the the shortest paths
between S and all the nodes of the constructed network.

2.3 The principle of optimality

This principle is due to R. Bellman, and allows for characterizing an optimal path
(shortest or longest).

Theorem 2.1
Any optimal path is composed by optimal sub-paths.
Proof
Let C = (i1, i2, …, ip-1, ip) be a shortest path from node i1 to ip. We will show that the
the sub-path C’ = (i1, i2, …, ip-1) is an optimal path from i1 to ip-1.

11
OPTIMIZATION 3A GI

If there exists another path C’’ linking the two nodes i1 and ip-1 and shorter than C’,
then the path obtained by adding the arc (ip-1, ip) to C’’ is shorter than C. This is a
contradiction with a fact that C is optimal. By induction over all the nodes in C, one
can show that all sub-paths in C are optimal.

Let N = {1, 2, …, n} and define for each node j a label πj equal to the length of the
shortest path from 1 to j. One immediate consequence of theorem 2.1 is the Bellman
equations:
π1 = 0
πj = mink≠j (πk + ckj) j = 2, …, n.

Example:
For the network in 2.3, π5 = min {π2 + c25 ; π3 + c35 ; π4 + c45}

2 3

4 5

Figure 2.3: Illustration of the principle of optimality of Bellman

Solving these equations for the case of a network without a negative circuit, gives the
shortest path between the node 1 and all other nodes of the network. The algorithms
presented next allows for solving these equations.

2.4 Shortest path algorithms

There are different algorithms depending on the nature of the network:
- Nonnegative length (or costs),
- Lengths of arbitrary signs,
- Network without negative cycles

and the problem at hand:

- Finding the shortest path from one node to another node,

12
OPTIMIZATION 3A GI

- Finding the shortest paths from one node to all other nodes,
- Finding the shortest paths between every couple of nodes.

All such algorithms are based on the principle of optimality of Bellman.

2.4.1 Networks with nonnegative lengths: Dijkstra’s algorithm (1959)

Dijkstra’s algorithm allows for finding shortest paths from one node (node 1) to each
other node of any network having nonnegative arc lengths.

A label is assigned to each node. The nodes are portioned into two subsets: P and T:
- P is the set of nodes each having a permanent label,
- T is the set of nodes each having a temporary label.

A permanent label represents the length of the shortest path from node 1 to the
considered node and a temporary label represents an upper bound on that length.

For a network having n nodes, the algorithm executes n-1 iterations: at each
iteration, one node is ransferred from T to P, and the temporary labels are updated.

Dijkstra’s algorithm (1959)

Step 1 : Initialization :
Define γ(j) as the precedent of node j in the shortest path from 1 to j.
π1 = 0
∀j≠1 πj = c1j and γ(j) = 1 if (1, j) ∈ N
πj = +∞ and γ(j) = - otherwise.
P = {1}, T = {2, …, n}

Step 2 : label fixing

Find i ∈ T, such that πi = minj∈T {πj}
Set: T = T\{i}
P = P ∪ {i}
If T = ∅ then terminate.

Step 3 : Update of temporary labels

13
OPTIMIZATION 3A GI

Set πj = min {πj, πi + cij} ∀ j∈T such that (i,j) ∈ N;

if πj changes, update γ(j) = i
Go to Step 2

Example: A transportation company has to distribute its client’s merchandise located

at node 1 to a number of sales points numbered from 2 to 6. The travel time between
each couple of nodes and the direction of travel are given by the following network:

4
4 5
2
2 5
7 1
3
1 5
2
3 6
1 4

Figure 2.4: Example

It is required to find the shortest path between node 1 and each of the sales points.

1 2 3 4 5 6
Itération
1 (0,1) (7,1) (1,1) +∞ +∞ +∞
2 - (6,3) - +∞ (3,3) (5,3)
3 - (5,5) - (8,5) - (5,3)
4 - - - (8,5) - (5,3)
5 - - - (8,5) - -

Step 1 : π1 = 0 π2 = 7 π3 = 1 π4 = π5 = π6 = ∞, P = {1}, T = { 2, 3, 4, 5, 6}
γ(2) = γ(3)= 1
Step 2 : i = 3, P = {1, 3}, T = {2, 4, 5, 6}
Step 3 : π2 = min {7, 1+5} = 6; γ(2) = 3 π5 = 3 π6 = 5; γ(5) = γ(6)= 3
Etc.

14
OPTIMIZATION 3A GI

Dijkstra’s algorithm is based on label fixing principle: at each iteration, it selects one
node and permanently fixes its label πj.

2.4.2 Case of arbitrary length signs: Ford-Bellman algorithm (1956)

This algorithm is applicable for general networks, having arbitrary signs of arc
lengths. In the absence of circuits of negative lengths, it finds the shortest path
from one node to all others by successively adjusting the Bellman equations.
Otherwise, it detects the presence of a negative circuit.

To each node j is associated a label πj(k) computed at iteration k :

Ford-Bellman algorithm (1956)

Step 1 : Initialization
π1(1) = 0
∀j≠1 πj(1) = c1j (and set γ(j) = 1) if (1, j) ∈ U
= +∞ otherwise.
k=1

Step 2 : Label update

For all j compute:
πj(k+1) = min {πj(k), mini≠j {πi(k) + cij}} ; update γ(j) if improvement occurs.

Step 3 : Test
If for all j πj(k+1) = πj(k), terminate
if k≤n-1, Go to Step 2 with k=k+1
If k=n, There exists a negative circuit; terminate.

This algorithm converges in at most (n-1) iterations.

Note: An improvement of this algorithm can be achieved by using the results of the
current iteration (i.e., using the updated labels of iteration k in the Bellman
equations).

15
OPTIMIZATION 3A GI

Example: A salesman currently at city O decides to participate in an international fair

organized in city T. To get to his destination, he has to use the network presented in
figure 2.5. He estimates the ransportation cost as well as the benefits he can earn by
selling his products at different intermediate cities along his route. In order to
minimize his expenses, the salesman seeks the minimal cost route from city O to city
T. Costs are benefits (negative data) are shown on the arcs.

A 7
2 -8 D
5
4
-5
O B -1 T
3
1 7
4 E
C
4

Figure 2.5 : Example

The shortest path from city O to city T has to be found. We have to use Ford-Bellman
algorithm because of the negative lengths:

O A B C D E T
Itération
1 (0,O) (2,O) (-5,O) (4,O) +∞ +∞ +∞
2 (0,O) (2,O) (-6,A) (4,O) (-1,B) (-2,B) +∞
3 (0,O) (2,O) (-6,A) (4,O) (-3,E) (-3,B) (4,D)
4 (0,O) (2,O) (-6,A) (4,O) (-4,E) (-3,B) (2,D)
5 (0,O) (2,O) (-6,A) (4,O) (-4,E) (-3,B) (1,D)

The shortest path from O to T is: O → A → B → E → D → T with a total cost of 1 unit.

The algorithm converges in 6 iterations.

16
OPTIMIZATION 3A GI

Ford algorithm is based on label corrections. It can change the label of any node until
the last iteration.

2.4.3 Case of a network with no circuit

For a network without any circuit, we can use a simple algorithm that finds the
shortest paths in just one iteration.
Note:
- Any network without circuits always has a particular node called the root, with no
predecessor (otherwise a circuit would exist).
- A network without circuits always has a terminal node (without any successor),
otherwise a circuit would exist.

♦ Finding the shortest path from one node to all others

Step 1 :
For a network of order n, without circuits, assign numbers 1 to n to the nodes such
that for each arc (i, j) of the network: i < j. To achieve this, one may proceed as
follows:
1. Assign the number 1 to the root node. Mark the node number 1 and delete
it from the graph and delete all arcs incident out of it.
2. If all nodes are numbered, terminate,
Otherwise, in the new network, find the nodes without any predecessors
and assign to them the following numbers, and delete them from the
network. Go to 2.
Step 2 :
The labels are recursively computed:
π1 = 0
πj = mini≠j (πi + cij) j = 2, …, n.

♦ Finding the shortest path from all nodes to one given node

Step 1 :
For a network without circuits, or order n, number the nodes such that for each arc
(i, j) of the network : i > j. To achieve this, one may proceed as follows:

17
OPTIMIZATION 3A GI

1. Assign the number 1 to the terminal node. Mark the node number 1 and
delete it from the graph and delete all arcs incident into it.
2. If all nodes are numbered, terminate,
Otherwise, in the new network, find the nodes without any successors
and assign to them the following numbers, and delete them from the
network. Go to 2.
Step 2 :
The labels are recursively computed:
π1 = 0
πj = mini≠j (πi + cji) j = 2, …, n.

Example : Find the shortest path from O to T in the following network :

10
A T

4 3 D
6 6
3 B 1
O 6
2 4
9 E
C
4

Figure 2.6: Example

♦ Step 1 : Numbering
O : 1, A : 2, C : 3, B : 4, E : 5, D : 6, T : 7.

Step 2 : Compute πi :
πO = 0
πA = min (0 + 6) = 6/O
πC = min (0 + 9) = 9/O
πB = min (0 + 3 ; 6 + 4 ; 9 + 2) = 3/O
πE = min (3 + 6 ; 9 + 4) = 9/B
πD = min (6 + 3 ; 9 + 1) = 9/A
πT = min (6 + 10 ; 9 + 6 ; 9 + 4) = 13/E

Particularly, the shortest path is: (O, B), (B, E) and (E, T) with a cost of 13.

18
OPTIMIZATION 3A GI

♦ Step 1 : Numbering
T : 1, D : 2, E : 3, B : 4, A : 5, C : 6, O : 7.

Step 2: Compute πi :
πT = 0
πD = min (0 + 6) = 6
πE = min (0 + 4 ; 1 + 6) = 4
πB = min (4 + 6) = 10
πA = min (0 + 10 ; 6 + 3 ; 10 + 4) = 9
πC = min (4 + 4 ; 10 + 2) = 8
πO = min (10 + 3 ; 9 + 6 ; 8 + 9) = 13

Particularly, the shortest path is: (O, B), (B, E) and (E, T) with a cost of 13.

Note: The numbering is not unique; for example, we could have inverted the numbers
of nodes A and C.

19