Networks & Integer Programming
Problem 1 - Networks & Shortest Path
Problem Statement:
Suppose you need to write a routing algorithm for a communications network that will route traffic through an
internetwork of networks (Ni) at the lowest possible cost. Your manager wants to know the least cost path between
Source (So) and Sink (Si). Consider a communications network that is characterized by the following link costs.
Link | Cost ($/Tb) | Link | Cost ($/Tb) | Link | Cost ($/Tb) |
So-N1 | 60 | N2-N4 | 20 | N5-N4 | 10 |
So-N2 | 30 | N2-N5 | 70 | N3 -Si | 20 |
N1-N2 | 10 | N3-N4 | 10 | N4-Si | 50 |
N2-N1 | 10 | N4-N3 | 20 | N5-Si | 30 |
N1-N3 | 50 | N4-N5 | 20 |
MATLAB Code: problem_1.m
Author: Yash Bansod
Date: 19th February, 2020
Problem 1 - Networks & Shortest Path
GitHub: https://github.com/YashBansod
Clear the environment and the command line
clear;
clc;
close all;
Define the graph
% Specify the node names
n_names = {'So', 'N1', 'N2', 'N3', 'N4', 'N5', 'Si'};
% Specify the edges and thier costs
e_start = [1 1 2 3 2 3 3 4 5 5 6 4 5 6];
e_stop = [2 3 3 2 4 5 6 5 4 6 5 7 7 7];
e_cost = [6 3 1 1 5 2 7 1 2 2 1 2 5 3] * 10;
% e_cost = [60 30 10 10 50 20 70 10 20 20 10 20 50 30];
% Some dimension checks to make sure values were inputted correctly
assert(size(e_start, 2) == size(e_stop, 2));
assert(size(e_start, 2) == size(e_cost, 2));
% Create the graph
graph = digraph(e_start, e_stop, e_cost, n_names);
Plotting the graph to visualize it better
figure('Name', 'Problem graph')
p_g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
title('Graph representing nodes and link cost')
xlabel('X Axis')
ylabel('Y Axis')
Calculate and plot the shortest path
[shortest_path, path_len] = shortestpath(graph, 'So', 'Si');
figure('Name', 'Shortest Path - Graph')
s_g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
highlight(s_g_plot, shortest_path, 'MarkerSize', 6, ...
'NodeColor', 'r', 'EdgeColor', 'g');
title(sprintf('Graph representing shortest path between %s and %s', ...
'So', 'Si'))
xlabel('X Axis')
ylabel('Y Axis')
Print the computation results
disp(strcat(sprintf('Shortest path sequence: %s', shortest_path{1}), ...
sprintf(' -> %s', shortest_path{2:end})))
fprintf('Shortest path cost: %d $/Tb\n', path_len
Shortest path sequence: So -> N2 -> N4 -> N3 -> Si
Shortest path cost: 90 $/Tb
Problem 2 - Transshipment/Production Problem
Problem Statement:
Suppose that you have two plants that manufacture drones, one in Chicago and one in Dallas. Suppose the Chicago plant can produce a maximum of 100 drones per week and the Dallas Plant can produce 200 drones/week. Suppose there are two major markets you serve, one in LA and the other in Baltimore. Suppose that the demand for drones in LA is 120 and the demand in Baltimore is 160 (drones per week).
Suppose there are the following per drone costs associated with shipping drones from one city to another (assume costs are symmetric (i.e. Cost i→j = Cost j→i):
To | ||||||
From | Los Angeles (LA) | Seattle (SA) | Chicago (CH) | Dallas (DA) | Philadelphia (PH) | Baltimore (BA) |
LA | - | $90 | $150 | $100 | $200 | $250 |
Seattle (SA) | - | $100 | $120 | $180 | $240 | |
Chicago (CH) | - | $50 | $120 | $140 | ||
Dallas (DA) | - | $100 | $150 | |||
Philadelphia (PH) | - | $30 | ||||
Baltimore (BA) | - |
Standard Form Representation:
Let X_B^A represent the number of drones shipped (per week) from city A to city B.
Let C_B^A represent the minimum cost of shipping a drone (single unit) from city A to city B.
Let Z represent the total cost of shipping incurred.
Then the objective function is the following:
min Z(X_LA^CH, X_BA^CH, X_LA^DA, X_BA^DA) = X_LA^CH*C_LA^CH + X_BA^CH*C_BA^CH + X_LA^DA *C_LA^DA + X_BA^DA*C_BA^DA
Such that:
X_LA^CH + X_BA^CH ≤ 100
X_LA^DA + X_BA^DA ≤ 200
X_LA^CH + X_LA^DA = 120
X_BA^CH + X_BA^DA = 160
X_B^A ∈ Z(0,+), A ∈ {CH, DA}, B ∈ {LA, BA}
MATLAB Code: problem_2.m
Author: Yash Bansod
Date: 19th February, 2020
Problem 2 - Transshipment/Production Problem
GitHub: https://github.com/YashBansod
Clear the environment and the command line
clear;
clc;
close all;
Define the graph
% Specify the node names
n_names = {'LA', 'SE', 'CH', 'DA', 'PH', 'BA'};
% Specify the edges and thier costs
e_start = [ 1 1 1 1 1;
2 2 2 2 2;
3 3 3 3 3;
4 4 4 4 4;
5 5 5 5 5;
6 6 6 6 6]';
e_start = e_start(:)';
e_stop = [ 2 3 4 5 6;
1 3 4 5 6;
1 2 4 5 6;
1 2 3 5 6;
1 2 3 4 6;
1 2 3 4 5]';
e_stop = e_stop(:)';
e_cost = [ 90 150 100 200 250;
90 100 120 180 240;
150 100 50 120 140;
100 120 50 100 150;
200 180 120 100 30;
250 240 140 150 30]';
e_cost = e_cost(:)';
% Some dimension checks to make sure values were inputted correctly
assert(size(e_start, 2) == size(e_stop, 2));
assert(size(e_start, 2) == size(e_cost, 2));
% Create the graph
graph = digraph(e_start, e_stop, e_cost, n_names);
Plotting the graph to visualize it better
figure('Name', 'Shortest Path - Graph')
g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
title('Graph representing cities and the paths between them')
xlabel('X Axis')
ylabel('Y Axis')
Calculate the least cost paths from production plants to markets
[shortest_path_ch_la, cost_ch_la] = shortestpath(graph, 'CH', 'LA');
[shortest_path_ch_ba, cost_ch_ba] = shortestpath(graph, 'CH', 'BA');
[shortest_path_da_la, cost_da_la] = shortestpath(graph, 'DA', 'LA');
[shortest_path_da_ba, cost_da_ba] = shortestpath(graph, 'DA', 'BA');
Define the optimization problem
f = [cost_ch_la cost_ch_ba cost_da_la cost_da_ba];
A = [1 1 0 0; 0 0 1 1];
B = [100; 200];
Aeq = [1 0 1 0; 0 1 0 1];
Beq = [120; 160];
lb = zeros(4, 1);
ub = inf(4, 1);
Find the solution
% Compute the solution using linear programming
[X, fval] = intlinprog(f, [1 2 3 4], A, B, Aeq, Beq, lb, ub);
LP: Optimal objective value is 33600.000000.
Print the computation results
% print out the least cost paths obtained using graph search
disp('Let C_A_B represent least cost path from city A to city B.')
fprintf([ 'Least cost of paths: \nC_CH_LA = %.2f' ...
'\nC_CH_BA = %.2f \nC_DA_LA = %.2f \nC_DA_BA = %.2f\n\n'], f)
% print out the solution obtained using integer programming
disp('Let X_A_B represent number of drones shipped from city A to city B.')
fprintf([ 'Solution using integer programming: \nX_CH_LA = %d' ...
'\nX_CH_BA = %d \nX_DA_LA = %d \nX_DA_BA = %d\n\n'], X)
fprintf('Cost of Shipment: %.2f dollars/week\n', fval)
Let C_A_B represent least cost path from city A to city B.
Least cost of paths:
C_CH_LA = 150.00
C_CH_BA = 140.00
C_DA_LA = 100.00
C_DA_BA = 130.00
Let X_A_B represent number of drones shipped from city A to city B.
Solution using integer programming:
X_CH_LA = 0
X_CH_BA = 80
X_DA_LA = 120
X_DA_BA = 80
Cost of Shipment: 33600.00 dollars/week
Problem 3 - Critical Path Method
Problem Statement:
Consider a Project that is characterized by the following activity edge table. The table indicates: 1) the activity names; 2) the associated event node names (numbers); 3) the duration times (in days) for each activity; and 4) the hourly labor costs for each activity. Assume two people are required to complete each task and that each works 8 hours a day.
Activity | Nodes | Duration Est (days) | Labor Cost ($/h) |
A | 1, 2 | 6 | $120 |
B | 1, 3 | 4 | $120 |
C | 2, 4 | 3 | $120 |
D | 3, 4 | 9 | $120 |
F | 3, 5 | 10 | $120 |
I | 3, 6 | 15 | $120 |
J | 4, 7 | 9 | $100 |
K | 5, 7 | 2 | $100 |
L | 6, 8 | 3 | $100 |
M | 7, 9 | 15 | $100 |
N | 8, 9 | 9 | $100 |
MATLAB Code: problem_3.m
Author: Yash Bansod
Date: 19th February, 2020
Problem 3 - Critical Path Method
GitHub: https://github.com/YashBansod
Clear the environment and the command line
clear;
clc;
close all;
Define the graph
% Specify the node names
n_names = {'N1', 'N2', 'N3', 'N4', 'N5', 'N6', 'N7', 'N8', 'N9'};
num_nodes = size(n_names, 2);
% Specify the edges and thier costs
e_start = [1 1 2 3 3 3 4 5 6 7 8];
e_stop = [2 3 4 4 5 6 7 7 8 9 9];
e_cost = [6 4.33 3.33 9 10 15.83 8.83 2 3.33 15 8.83];
% Some dimension checks to make sure values were inputted correctly
assert(size(e_start, 2) == size(e_stop, 2));
assert(size(e_start, 2) == size(e_cost, 2));
% Create the graph
graph = digraph(e_start, e_stop, e_cost, n_names);
Plotting the graph to visualize it better
figure('Name', 'Problem graph')
p_g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
title('Graph representing nodes and mean activity duration')
xlabel('X Axis')
ylabel('Y Axis')
Calculate the longest path
% Create a matrix that stores the longest known path from the node marked
% by index to the end.
max_len = zeros(1, num_nodes);
% Create a matrix that indicates nodes that follow a node on critical path
follow_node = zeros(1, num_nodes);
% distance/cost matrix of going from (row) node i to (column) node j
dist_mat = -inf(num_nodes);
for index = 1:size(e_start, 2)
dist_mat(e_start(index), e_stop(index)) = e_cost(index);
end
% Simplified Bellman-Ford Algorithm
% Longest known path from node n-1 to n is the edge from n-1 to n
max_len(num_nodes - 1) = dist_mat(num_nodes - 1, num_nodes);
% Working back from node n-2 to compute longest path from node i to end
for i_ind = num_nodes-2:-1:1
for j_ind = i_ind+1:num_nodes
% If longest path length from node j to end + path length from node
% i to j is greater than longest known path from node i to end then
if max_len(j_ind) + dist_mat(i_ind, j_ind) > max_len(i_ind)
% longest path length from node i to end equals the longest
% path length from node j to end + path length from node i to j
max_len(i_ind) = max_len(j_ind) + dist_mat(i_ind, j_ind);
% node i is followed by node j in the longest known path
follow_node(i_ind) = j_ind;
end
end
end
% Calculate the Critical Path
critical_path = zeros(1, num_nodes);
critical_path(1) = 1; % Start node always lies on the critical path
for path_ctr = 2:1:num_nodes
critical_path(path_ctr) = follow_node(critical_path(path_ctr -1));
if critical_path(path_ctr) == 0
critical_path(path_ctr) = num_nodes;
end
end
critical_path = n_names(unique(critical_path));
Plotting the critical path
figure('Name', 'Critical Path - Graph')
l_g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
title('Graph representing the Critical Path')
xlabel('X Axis')
ylabel('Y Axis')
highlight(l_g_plot, critical_path, 'MarkerSize', 6, ...
'NodeColor', 'r', 'EdgeColor', 'g');
Print the computation results
disp(strcat(sprintf('Critical path: %s', critical_path{1}), ...
sprintf(' -> %s', critical_path{2:end})))
fprintf('Longest path == Mean project duration: %.2f days\n\n', max_len(1))
Critical path: N1 -> N3 -> N4 -> N7 -> N9
Longest path == Mean project duration: 37.16 days
Calculate the shortest path
[shortest_path, path_len] = shortestpath(graph, 'N1', 'N9');
Print the computation results
disp(strcat(sprintf('Shortest path sequence: %s', shortest_path{1}), ...
sprintf(' -> %s', shortest_path{2:end})))
fprintf('Shortest path cost: %.2f days\n', path_len)
Shortest path sequence: N1 -> N3 -> N5 -> N7 -> N9
Shortest path cost: 31.33 days
Problem 4 - Transshipment Problem
The case of a company that produces a product at two plants (P1 and P2) and has two warehouses (WH1 and WH2). They produce the product, and send it to a warehouse, from which the product is then distributed to three retail outlets (RO1, RO2, & RO3). Each truck is capable of shipping “standard truck load” (i.e. ‘unit’) of product. Each plant has a different maximum output and each retail outlet has a different demand (see tables below). There is a maximum number of units that may be shipped from each plant to each warehouse and from each warehouse to each retail outlet and a different cost associated with each such link (see tables below). The company wants to develop a distribution plan that will minimize shipping costs.
Plant to Warehouse (WH) | |||||
Plant | Unit Ship Cost | Shipping Capacity (Units) | Max Output | ||
WH1 | WH2 | WH1 | WH2 | ||
P1 | $425 | $560 | 125 | 150 | 200 |
P2 | $510 | $600 | 175 | 200 | 300 |
Warehouse to Retail Outlet (RO) | ||||||
Warehouse | Unit Ship Cost | Shipping Capacity (Units) | ||||
RO1 | RO2 | RO3 | RO1 | RO2 | RO3 | |
WH1 | $470 | $505 | $490 | 100 | 150 | 100 |
WH2 | $390 | $410 | $440 | 125 | 150 | 75 |
RO1 | RO2 | RO3 | |
Demand (Units) | 100 | 150 | 100 |
MATLAB Code: problem_4.m
Author: Yash Bansod
Date: 11th March, 2020
Problem 4 - Transshipment Problem
GitHub: https://github.com/YashBansod
Clear the environment and the command line
clear;
clc;
close all;
Define the graph
% Specify the node names
n_names = {'P1', 'P2', 'WH1', 'WH2', 'RO1', 'RO2', 'RO3'};
num_nodes = size(n_names, 2);
% Specify the edges and thier costs
e_start = [1 1 2 2 3 3 3 4 4 4];
e_stop = [3 4 3 4 5 6 7 5 6 7];
e_cost = [425 560 510 600 470 505 490 390 410 440];
% Some dimension checks to make sure values were inputted correctly
assert(size(e_start, 2) == size(e_stop, 2));
assert(size(e_start, 2) == size(e_cost, 2));
% Create the graph
graph = digraph(e_start, e_stop, e_cost, n_names);
Plotting the graph to visualize it better
figure('Name', 'Problem graph')
p_g_plot = plot(graph, ...
'EdgeLabel', graph.Edges.Weight, ...
'LineWidth', 4 * graph.Edges.Weight / max(graph.Edges.Weight), ...
'ArrowSize', 15);
title('Graph representing nodes and shipping costs')
xlabel('X Axis')
ylabel('Y Axis')
Define the optimization problem
f = e_cost;
A = [ 1 1 0 0 0 0 0 0 0 0;
0 0 1 1 0 0 0 0 0 0];
B = [200; 300];
Aeq = [ 0 0 0 0 1 0 0 1 0 0;
0 0 0 0 0 1 0 0 1 0;
0 0 0 0 0 0 1 0 0 1;
1 0 1 0 -1 -1 -1 0 0 0;
0 1 0 1 0 0 0 -1 -1 -1];
Beq = [100; 150; 100; 0; 0];
lb = zeros(10, 1);
ub = [125; 150; 175; 200; 100; 150; 100; 125; 150; 75];
Find the solution
% Compute the solution using linear programming
[X, fval] = intlinprog(f, 1:10, A, B, Aeq, Beq, lb, ub);
LP: Optimal objective value is 335875.000000.
Print the computation results
% print out the solution obtained using integer programming
fprintf('Cost of Shipment: %d dollars\n\n', fval)
disp("Units Shipped [From->To:Number]");
% Optimal Plan
for index = 1:size(e_start, 2)
print_str = strcat(n_names{e_start(index)}, '->', ...
n_names{e_stop(index)}, ': ', int2str(X(index)));
fprintf('[%s]\n', print_str);
end
Cost of Shipment: 335875 dollars
Units Shipped [From->To:Number]
[P1->WH1:125]
[P1->WH2:75]
[P2->WH1:75]
[P2->WH2:75]
[WH1->RO1:100]
[WH1->RO2:0]
[WH1->RO3:100]
[WH2->RO1:0]
[WH2->RO2:150]
[WH2->RO3:0]