0% found this document useful (0 votes)

27 views54 pages

Solution To Problem Set 1 Part I 1

The document provides solutions to various quantitative methods problems, including finding minimum spanning trees using Kruskal's and Reverse-delete algorithms, and determining longest paths in directed graphs using the Acyclic Digraph Method. It details the steps involved in each algorithm and presents specific examples, including a case study on Shell Petrochemical Corporation's pipeline planning. The document emphasizes the importance of graph theory in optimizing network connections and costs.

Uploaded by

limjocogabby

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

27 views54 pages

Solution To Problem Set 1 Part I 1

Uploaded by

limjocogabby

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Solution to Problem Set 1 (Part I)

Armin Paul D. Allado

Quantitative Methods and Information Technology
Ateneo de Manila University

QUANT 163: Advanced OR| Armin Paul D. Allado | 2nd Semester SY 2021-2022
Solution to Question 1

Given the network graph defined by the following nodes and edges, look for the
minimum spanning tree.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 2

Solution to Question 1

Recall: Kruskal’s Algorithm

1. Sort all edges from low weight to high

2. Take the edge with the lowest weight and add it to the spanning tree. If adding
the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 3

Solution to Question 1

Kruskal’s Algorithm
1. Sort all edges from low weight to high

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 4

Solution to Question 1

Kruskal’s Algorithm
2. Take the edge with the lowest weight and add it to the spanning tree. If adding
the edge created a cycle, then reject this edge.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 5

Solution to Question 1

Kruskal’s Algorithm
3. Keep adding edges until we reach all vertices.
Total Distance = 155.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 6

Solution to Question 2

Given the distance matrix of a Minimum Spanning Tree problem

Find all Minimum Spanning Tree of the network graph. Write the total distance.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 7

Solution to Question 2

Kruskal’s Algorithm
1. Sort all edges from low weight to high

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 8

Solution to Question 2

Kruskal’s Algorithm
2. Take the edge with the lowest weight and add it to the spanning tree. If adding
the edge created a cycle, then reject this edge.

Total distance = 380 Total distance = 380

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 9

Solution to Question 2

Kruskal’s Algorithm
2. Take the edge with the lowest weight and add it to the spanning tree. If adding
the edge created a cycle, then reject this edge.

Total distance = 380 Total distance = 380

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 10

Solution to Question 3

The Shell Petrochemical Corporation is a company which buys unprocessed fuels from suppliers and then refining it into
Gasoline, Diesel and Kerosene fuels. Shell delivers fuel to 9 fuel stations in the Central Luzon area using oil tankers.
However to decrease costs in the long run, Shell decided to build pipelines underground such that Shell main refinery
plant node (6) can service the 9 stations without the use of fuel tankers. Given below are the distances (in kms) and the
possible connections from one station (node) to another station (node)

Given that the cost of laying the pipe is linear with a rate of $5/km and a fixed penalty cost of $250 if the distance is less
than 200 km (to cover for high fixed costs for the contractor), how should Shell Petrochemical Corporation lay the
“pipelines of the future”? (please draw the graph)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 11

Solution to Question 3

Total Cost = 9,230

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 12

Solution to Question 4

Given the following network graph:

a. Determine the longest path from the origin to the terminal that passes through
node E. Briefly explain your process.
b. Would your method still work if the directed arcs are replaced with undirected
edges? Why or why not?
QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 13
Solution to Question 4

Recall: Acyclic Digraph Method for Shortest Path

• Step 0: Number the nodes such that each arc(i,j) has i < j (start with 0).
Label node 0 with [0,-]. k = 1
• Step k: if node k has no inbound arc, label node k with [∞, -].
• Otherwise, uk = min {ui + dik | (i,k) exists} and label node k with [uk, i]
• ** i = number of the node achieving the minimum.
• If all nodes are labelled, STOP. Else, k = k + 1

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 14

Solution to Question 4

Acyclic Digraph Method for Longest Path

• Step 0: Number the nodes such that each arc(i,j) has i < j (start with 0).
Label node 0 with [0,-]. k = 1
• Step k: if node k has no inbound arc, label node k with [∞, -].
• Otherwise, uk = max {ui + dik | (i,k) exists} and label node k with [uk, i]
• ** i = number of the node achieving the minimum.
• If all nodes are labelled, STOP. Else, k = k + 1

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 15

Solution to Question 4

Determine the longest path from the origin to the terminal that passes through node
E. Briefly explain your process.

1. Divide the problem into two stages. In stage 1, we consider the arcs that can take us
from O to E. In stage 2, we consider the arcs that can take us from E to T.
2. Apply Acyclic Digraph Method for Longest Path for stage 1 (to determine longest path
from O to E) and stage 2 (to determine largest path from E to T)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 16

Solution to Question 4

1. Divide the problem into two stages. In stage 1, we consider the arcs that can take us
from O to E (in red). In stage 2, we consider the arcs that can take us from E to T (in
green).

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 17

Solution to Question 4

2. Apply Acyclic Digraph Method for Longest Path for stage 1 (to determine longest path
from O to E) and stage 2 (to determine largest path from E to T)

Longest path: O - A - B - E

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 18

Solution to Question 4

2. Apply Acyclic Digraph Method for Longest Path for stage 1 (to determine longest path
from O to E) and stage 2 (to determine largest path from E to T)

Longest path:
E - H - I – T or E - F - T
Final answer:
O - A - B - E - H - I – T or O - A - B - E - F - T

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 19

Solution to Question 4

Would your method still work if the directed arcs are replaced with undirected
edges? Why or why not?
With undirected edges, we have to
resort to Dijkstra’s algorithm

Not guaranteed to give optimal

solution:
1. Fails to take into account
“unexplored” nodes
2. Doesn’t work on negative weights
(even if we negate the weights)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 20

Dijkstra’s Algorithm (Practice)

Use Dijkstra’s Algorithm to determine shortest path from O to T

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 21

Dijkstra’s Algorithm (Practice)

Recall: Dijkstra’s Algorithm

Step 0: Label source node 0 with permanent label: [0,-], set i = 0

Step i: (a) Compute temporary label [ui + dij, i] for each node j that can be reached
from node i, provided that j is not permanently labelled. If j is already labelled
with [uj, k] through another node k, and if ui + dij < uj, replace [uj, k] with [ui + dij, i]
Step i: (b) if all nodes have permanent labels, STOP. Otherwise, select the label
[un,s] with shortest distance un from all the temporary labels and set it as
permanent. Set i = n and repeat step i

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 22

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 23

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 24

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 25

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 26

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 27

Dijkstra’s Algorithm (Practice)

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 28

Reverse-delete Algorithm (Practice)

Use Reverse-delete algorithm to determine the Minimum Spanning Tree

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

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 29

Reverse-delete Algorithm (Practice)

Recall: Reverse-delete Algorithm

1. Sort all edges of graph in non-increasing order of edge weights.

2. Pick highest weight edge from remaining edges and check if deleting the edge
disconnects the graph or not. If disconnects, then we don't delete the edge. Else we
delete the edge and continue.
3. Keep deleting edges until we reach all vertices

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 30

Reverse-delete Algorithm (Practice)

1. Sort all edges of graph in non-increasing order of edge weights.

2
2 1
7 0
5 4 5
O B D T

1
4 1 3
7
4
C E

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 31

Reverse-delete Algorithm (Practice)
2. Pick highest weight edge from remaining edges and check if deleting the
edge disconnects the graph or not. If disconnects, then we don't delete the
edge. Else we delete the edge and continue.

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 32

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 33

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 34

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 35

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 36

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 37

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 38

Reverse-delete Algorithm (Practice)

3. Keep deleting edges until we reach all vertices

Edges of MST in red

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 39

Acyclic Digraph (Practice)

Use Acyclic Digraph Solution to determine the shortest path from O to other nodes:

QUANT 163: Advanced OR | Armin Paul D. Allado | 2nd Semester SY 2021-2022 40

Acyclic Digraph (Practice)

1. Number the nodes such that each arc(i,j) has i < j (start with 0). Label node
0 with [0,-]. k = 1