Network Optimization Problem

Danu Hadi Syaifullah ST., MSc.

Introduction
• Networks arise in numerous settings and in a variety of guises.
Transportation, electrical, and communication networks pervade
our daily lives.
• Network representations also are widely used for problems in such
diverse areas as production, distribution, project planning, facilities
location, resource management, and financial planning—to name
just a few examples.
• In fact, a network representation provides such a powerful visual
and conceptual aid for portraying the relationships between the
components of systems that it is used in virtually every field of
scientific, social, and economic endeavor.
Introduction
• Many network optimization models actually are special types of linear
programming problems. For example, both the transportation problem
and the assignment problem discussed in the previous weeks fall into this
category because of their network representations presented in the
following figure:
Basic Definitions
• A graph or network is defined by two sets of symbols: nodes and arcs.
• A set of points, or vertices, of a graph or network are also called nodes.
• An arc consists of an ordered pair of nodes and represents a possible
direction of motion that may occur between nodes.
• The arcs of a network may have a flow of some type through them
Scope of Discussion
• In this chapter, we will discuss several topics below:
o Shortest-Path Problems
o Minimum Spanning Tree Problems
o Maximum Flow Problems
o Minimum Cost Network Flow Problems
Shortest-Path Problems
• In this section, we assume that each arc in the network has a
length associated with it.
• Suppose we start at a particular node (say, node 1). The problem
of finding the shortest path (path of minimum length) from node 1
to any other node in the network is called a shortest-path problem.
Shortest-Path Problems
• Let us consider the Powerco example. Suppose that when power is sent from
plant 1 (node 1) to city 1 (node 6), it must pass through relay substations (nodes
2–5). For any pair of nodes between which power can be transported, Figure
below gives the distance (in miles) between the nodes. Thus, substations 2 and 4
are 3 miles apart, and power cannot be sent between substations 4 and 5.
• Powerco wants the power sent from plant 1 To city 1 to travel the minimum
Possible distance, so It must find the shortest path In Figure below that joins node
1 to node 6.
Dijkstra’s Algorithm
• Assuming that all arc lengths are nonnegative, the following method,
known as Dijkstra’s algorithm, can be used to find the shortest path
from a node (say, node 1) to all other nodes.
• To begin, we label node 1 with a permanent label of 0. Then we label
each node i that is connected to node 1 by a single arc with a
“temporary” label equal to the length of the arc joining node 1 to
node i.
• Each other node will have a temporary label of ∞. Choose the node
with the smallest temporary label and make this label permanent.
Dijkstra’s Algorithm
• Now suppose that node i has just become the (k + 1)th node to be
given a permanent label. Then node i is the kth closest node to node
1. At this point, the temporary label of any node (say, node i’) is the
length of the shortest path from node 1 to node i’ that passes only
through nodes contained in the k - 1 closest nodes to node 1.
• For each node j that now has a temporary label and is connected to
node i by an arc, we replace node j’s temporary label with
Dijkstra’s Algorithm
• (Here, min{a, b} is the smaller of a and b.) The new temporary label for
node j is the length of the shortest path from node 1 to node j that
passes only through nodes contained in the k closest nodes to node 1.
• We now make the smallest temporary label a permanent label. The
node with this new permanent label is the (k + 1)th closest node to
node 1.
• Continue this process until all nodes have a permanent label.
Using Dijkstra’s Algorithm to Solve
Powerco example
• We begin with the following labels ( * represents a permanent label, and the
ith number is the label of the node i): [0* 4 3 ∞∞∞]. Node 3 now has the
smallest temporary label. We therefore make node 3’s label permanent and
obtain the following labels:

• We now know that node 3 is the closest node to node 1. We compute new
temporary labels for all nodes that are connected to node 3 by a single arc.
In Figure below that is node 5
Using Dijkstra’s Algorithm to Solve
Powerco example
• Node 2 now has the smallest temporary label; we now make node 2’s label
permanent. We now know that node 2 is the second closest node to node 1.
Our new set of labels is

• Because nodes 4 and 5 are connected to the newly permanently labeled

node 2, we must change the temporary labels of nodes 4 and 5. Node 4’s
new temporary label is min {∞, 4 + 3} = 7 and node 5’s new temporary label is
min {6, 4 + 2} = 6.
Using Dijkstra’s Algorithm to Solve
Powerco example
• Node 5 now has the smallest temporary label, so we make node 5’s label
permanent. We now know that node 5 is the third closest node to node 1.
Our new labels are

• Only node 6 is connected to node 5, so node 6’s temporary label will

change to min {∞, 6 + 2} = 8. Node 4 now has the smallest temporary label,
so we make node 4’s label permanent. We now know that node 4 is the
fourth closest node to node 1. Our new labels are
Using Dijkstra’s Algorithm to Solve
Powerco example
• Because node 6 is connected to the newly permanently labeled node 4, we
must change node 6’s temporary label to min {8, 7 + 2} = 8. We can now
make node 6’s label permanent. Our final set of labels is [0* 4* 3* 7* 6* 8*].
• Thus, 1–2–5–6 is a shortest path (of length 8) from node 1 to node 6.
• Observe that when we were at node 5, we could also have worked
backward to node 3 and obtained the shortest path 1–3–5–6
Algorithm for the Shortest-Path
Problem
• Objective of nth iteration: Find the nth nearest node to the origin (to
be repeated for n = 1, 2, . . . until the nth nearest node is the
destination.
• Input for nth iteration: n - 1 nearest nodes to the origin (solved for at
the previous iterations), including their shortest path and distance from
the origin. (These nodes, plus the origin, will be called solved nodes;
the others are unsolved nodes).
• Candidates for nth nearest node: Each solved node that is directly
connected by a link to one or more unsolved nodes provides one
candidate—the unsolved node with the shortest connecting link. (Ties
provide additional candidates).
Algorithm for the Shortest-Path
Problem
• Calculation of nth nearest node: For each such solved node and its
candidate, add the distance between them and the distance of the
shortest path from the origin to this solved node. The candidate with
the smallest such total distance is the nth nearest node (ties provide
additional solved nodes), and its shortest path is the one generating
this distance.
Algorithm for the Shortest-Path
Problem
• Example: Try to re do the problem below:
Exercise (1)
• SEERVADA PARK has recently been set aside for a limited amount of
sightseeing and backpack hiking. Cars are not allowed into the park, but
there is a narrow, winding road system for trams and for jeeps driven by the
park rangers. This road system is shown (without the curves) in Figure below,
where location O is the entrance into the park; other letters designate the
locations of ranger stations (and other limited facilities). The numbers give the
distances of these winding roads in miles. The park contains a scenic wonder
at station T. Find the shortest path between entrance and station T!
Exercise (2)
• Use the Dijkstra’s Algorithm to find the shortest path through each of
the following networks, where the numbers represent actual distances
between the corresponding nodes
Exercise (3)
• At a small but growing airport, the local airline company is purchasing
a new tractor for a tractor-trailer train to bring luggage to and from
the airplanes. A new mechanized luggage system will be installed in 3
years, so the tractor will not be needed after that. However, because
it will receive heavy use, so that the running and maintenance costs
will increase rapidly as the tractor ages, it may still be more
economical to replace the tractor after 1 or 2 years.
• The following table gives the total net discounted cost associated with
purchasing a tractor (purchase price minus trade-in allowance, plus
running and maintenance costs) at the end of year i and trading it in
at the end of year j (where year 0 is now).
Exercise (3)

• The problem is to determine at what times (if any) the tractor should
be replaced to minimize the total cost for the tractors over 3 years.
o Formulate this problem as a shortest-path problem.
o Use the Dijkstra’s Algorithm to solve this shortest-path problem.
Minimum Spanning Tree Problems
• Suppose that each arc (i,j) in a network has a length associated with it
and that arc (i,j) represents a way of connecting node i to node j.
• In many applications it must be determined that the set of arcs in a
network that connects all nodes such that the sum of the length of the
arcs is minimized. Clearly, such a group of arcs contain no loop.
• For a network with n nodes, a spanning tree is a group of n-1 arcs that
connects all nodes of the network and contains no loops.
Minimum Spanning Tree Problems
• A spanning tree of minimum length in a network is a minimum
spanning tree (MST).
• The minimum spanning tree problem bears some similarities to the
main version of the shortest-path problem presented in the preceding
section.
• Both problems also involve choosing a set of links that have the
shortest total length among all sets of links that satisfy a certain
property.
• For the shortest-path problem, this property is that the chosen links
must provide a path between the origin and the destination.
• For the minimum spanning tree problem, the required property is that
the chosen links must provide a path between each pair of nodes.
Minimum Spanning Tree Problems
The minimum spanning tree problem can be summarized as follows:
1. You are given the nodes of a network but not the links. Instead, you
are given the potential links and the positive length for each if it is
inserted into the network. (Alternative measures for the length of a link
include distance, cost, and time.)
2. You wish to design the network by inserting enough links to satisfy the
requirement that there be a path between every pair of nodes.
3. The objective is to satisfy this requirement in a way that minimizes the
total length of the links inserted into the network.
Minimum Spanning Tree Problems
Here is a list of some key types of applications of the minimum spanning
tree problem:
1. Design of telecommunication networks (fiber-optic networks,
computer networks, leased-line telephone networks, cable television
networks, etc.)
2. Design of a lightly used transportation network to minimize the total
cost of providing the links (rail lines, roads, etc.)
3. Design of a network of high-voltage electrical power transmission lines
4. Design of a network of wiring on electrical equipment (e.g., a digital
computer system) to minimize the total length of the wire
5. Design of a network of pipelines to connect a number of locations
Minimum Spanning Tree Problems
• The MST Algorithm may be used to find a minimum spanning tree.
o Begin at any node i, and join node i to the node in the network (call it
node j) that is closest to node i.
• The two nodes i and j now form a connected set of nodes C={i,j}, and
arc (i,j) will be in the minimum spanning tree. The remaining nodes in
the network (call them Ć) are referred to as the unconnected set of
nodes.
o Now choose a member of C’ (call it n) that is closest to set C. Let m
represent the node in C that is closest to n. Then the arc(m,n) will be in the
minimum spanning tree. Now update C and C’. Since n is now connected
to {i,j}, C now equals {i,j,n} and we must eliminate node n from C’.
o Repeat this process until a minimum spanning tree is found. Ties for closest
node and arc to be included in the minimum spanning tree may be
broken arbitrarily.
MST Algorithm: Example
• The State University campus has five computers. The distances
between each pair of computers are given.
• What is the minimum length of cable required to interconnect the
computers?

1 1
2
2
2
6
5 4
2 3
4
4
5 3
MST Algorithm: Example
We want to find the minimum spanning tree.
• Iteration 1: Following the MST algorithm discussed before, arbitrarily
choose node 1 to begin. The closest node is node 2. Now C={1,2},
Ć={3,4,5}, and arc(1,2) will be in the minimum spanning tree.

1 1
2
2
2
6
5 4
2 3
4
4
5 3
MST Algorithm: Example
• Iteration 2: Node 5 is closest to C. since node 5 is two blocks from node
1 and node 2, we may include either arc(2,5) or arc(1,5) in the
minimum spanning tree. We arbitrarily choose to include arc(2,5). Then
C={1,2,5} and Ć={3,4}.

1 1
2
2
2
6
5 4
2 3
4
4
5 3
MST Algorithm: Example
• Iteration 3: Since node 3 is two blocks from node 5, we may include
arc(5,3) in the minimum spanning tree. Now C={1,2,5,3} and Ć={4}.

1 1
2
2
2
6
5 4
2 3
4
4
5 3
MST Algorithm: Example
• Iteration 4: Node 5 is the closest node to node 4. Thus, we add arc(5,4)
to the minimum spanning tree.
• The minimum spanning tree consists of arcs(1,2), (2,5), (5,3), and (5,4).
The length of the minimum spanning tree is 1+2+2+4=9 blocks.

1 1
2
2
2
6
5 4
2 3
4
4
5 3
MST Algorithm: Exercise (1)
• The Seervada Park management (see Sec. 9.1) needs to determine
under which roads telephone lines should be installed to connect all
stations with a minimum total length of line
MST Algorithm: Exercise (2)
• The Wirehouse Lumber Company will soon begin logging eight groves
of trees in the same general area. Therefore, it must develop a system
of dirt roads that makes each grove accessible from every other
grove. The distance (in miles) between every pair of groves is as
follows:
MST Algorithm: Exercise (2)
• Management now wishes to determine between which pairs of groves
the roads should be constructed to connect all groves with a minimum
total length of road.
o Describe how this problem fits the network description of the
minimum spanning tree problem.
o Use the algorithm described previously to solve the problem
The End