Objective
# Course: BUAN 5260
# Title: Week 4-Network optimization
# Purpose: USE IFRC Information information to model scenarios
# and make Recommendation Plans
# Author: Afsar Ali# Clear packages
if(is.null(sessionInfo()$otherPkgs) == FALSE)lapply(
paste("package:", names(sessionInfo()$otherPkgs), sep=""),
detach, character.only = TRUE, unload = TRUE)
# Clear all data in environment
rm(list=ls(all=TRUE))
# Load packages
library(igraph)
library(lpSolve)
library(lpSolveAPI)
library(tidyverse)
library(magrittr)
library(data.table)
set.seed(123)Loading and cleaning the data
#load Data
ifrc <- read.csv("5260_S18_Aiding_Africa_Data.csv", skip = 1)
#Naming and Creating each table
req_trv <- ifrc[1:3,1:3]
mdata <- ifrc[,8:12]
req <- ifrc[1:9,14:15]
air_max <- ifrc[1:15,17:19]
truck_max <- ifrc[1:6,21:23]
#create nodes
req$Requirements <- req$Requirements *-1
req$City <- as.character(req$City)
nodes<- rbind('1' = c('New York, NY', '500000'), '2' = c('Jacksonville, FL', '500000'), req)
nodes$Requirements <- as.integer(nodes$Requirements)
# Join the tables and create edges
edges <- mdata %>%
left_join(req_trv, by = c("Type.1" = "Type")) %>%
mutate(Time = Distance / Speed) %>%
mutate(Cost = Cost * 1000) %>%
left_join(air_max, by = c("From" = "From.1", "To" = "To.1")) %>%
left_join(truck_max, by = c("From" = "From.2", "To" = "To.2"))
colnames(edges)[3] <- 'Type'
#create constraints
edges$Max.Airplanes <- edges$Max.Airplanes * edges$Capacity
edges$Max.Trucks <- edges$Max.Trucks * edges$Capacity
edges$Max.Airplanes[is.na(edges$Max.Airplanes)] <- 0
edges$Max.Trucks[is.na(edges$Max.Trucks)] <- 0
edges$Max <- edges$Max.Trucks + edges$Max.Airplanes
edges$Max[is.na(edges$Max)] <- 0
#Network ID
edges$ID <- paste(edges$From, edges$To, sep = ' > ')1 Netowrk Map
- Make sense all the Air Routes are the Fastest
net <- graph_from_data_frame(d=edges, vertices=nodes, directed=T)
net$layout <- matrix(c(-800, -800,
0, 0, 0, 0, 0, 0,
800, 800, 800,
225, 125,
300, 250, 200, 150, 100, 50,
250, 175, 100), nc = 2)
#Set Weight for Edges
E(net)$weight = E(net)$Time
#Create a Unique col
edges$ID <- paste(edges$From, edges$To, sep = ' > ')
#Add route attribute
V(net)$route <- c("From","From","To","To","To","To","To","To","To","To","To")
V(net)$color <- c("gold","green")[1+(V(net)$route=="From")]
#look at the data
glimpse(edges)## Observations: 30
## Variables: 12
## $ From <chr> "New York, NY", "New York, NY", "New York, NY", ...
## $ To <chr> "Lusaka, Zambia", "Libreville, Gabon", "Nairobi,...
## $ Type <chr> "Airplane", "Ship", "Airplane", "Airplane", "Shi...
## $ Distance <int> 8098, 6024, 8050, 7041, 6526, 4172, 7944, 6329, ...
## $ Cost <dbl> 50000, 30000, 55000, 45000, 30000, 32000, 57000,...
## $ Capacity <dbl> 150.0, 240.0, 150.0, 150.0, 240.0, 240.0, 150.0,...
## $ Speed <int> 400, 35, 400, 400, 35, 35, 400, 35, 400, 400, 35...
## $ Time <dbl> 20.2450, 172.1143, 20.1250, 17.6025, 186.4571, 1...
## $ Max.Airplanes <dbl> 45000, 0, 75000, 75000, 0, 0, 75000, 0, 105000, ...
## $ Max.Trucks <dbl> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
## $ Max <dbl> 45000, 0, 75000, 75000, 0, 0, 75000, 0, 105000, ...
## $ ID <chr> "New York, NY > Lusaka, Zambia", "New York, NY >...# Get some colours in to visualise routes
E(net)$color[E(net)$Type == 'Truck'] <- 'saddlebrown'
E(net)$color[E(net)$Type == 'Airplane'] <- 'forestgreen'
E(net)$color[E(net)$Type == 'Ship'] <- 'royalblue'
#Plot Network Map
plot(net, edge.arrow.size=.3, edge.label = round(E(net)$Time, 2),
edge.width = 10*E(net)$Time/max(E(net)$Time),
vertex.size=25)
2 Netowrk Map with Fastest Route
-Bottlenecks are on Dakar, Senegal, Libreville, Garbon, Luanda, Angola -Quickest route is 20.60 hours From New York to Ndjamena, Chad +New York, NY > Kosongo, D.R. Congo = 21.04
+New York, NY > Ndjamena, Chad = 20.60
+New York, NY > Niamey, Niger = 22.76 +Jacksonville, FL > Kosongo, D.R. Congo = 21.15
+Jacksonville, FL > Ndjamena, Chad = 20.71
+Jacksonville, FL > Niamey, Niger = 22.87
#Create Table for shortest time
distMatrix <- shortest.paths(net, v=V(net), to=V(net))
as.data.frame(distMatrix)## New York, NY Jacksonville, FL Dakar, Senegal
## New York, NY 0.0000 35.3125 55.8850
## Jacksonville, FL 35.3125 0.0000 55.9925
## Dakar, Senegal 55.8850 55.9925 0.0000
## Libreville, Gabon 43.4050 43.5125 53.7600
## Luanda, Angola 48.8250 48.9325 69.5050
## Khartoum, Sudan 17.6025 17.7100 38.2825
## Lusaka, Zambia 20.2450 19.8600 43.2950
## Nairobi, Kenya 20.1250 19.9025 39.4300
## Niamey, Niger 22.7650 22.8725 33.1200
## Kosongo, D.R. Congo 21.0450 21.1525 41.7250
## Ndjamena, Chad 20.6025 20.7100 41.2825
## Libreville, Gabon Luanda, Angola Khartoum, Sudan
## New York, NY 43.4050 48.8250 17.6025
## Jacksonville, FL 43.5125 48.9325 17.7100
## Dakar, Senegal 53.7600 69.5050 38.2825
## Libreville, Gabon 0.0000 57.0250 25.8025
## Luanda, Angola 57.0250 0.0000 31.2225
## Khartoum, Sudan 25.8025 31.2225 0.0000
## Lusaka, Zambia 30.8150 29.6450 5.3075
## Nairobi, Kenya 26.9500 30.5050 6.1675
## Niamey, Niger 20.6400 36.3850 5.1625
## Kosongo, D.R. Congo 29.2450 27.7800 3.4425
## Ndjamena, Chad 28.3000 34.2225 3.0000
## Lusaka, Zambia Nairobi, Kenya Niamey, Niger
## New York, NY 20.2450 20.1250 22.7650
## Jacksonville, FL 19.8600 19.9025 22.8725
## Dakar, Senegal 43.2950 39.4300 33.1200
## Libreville, Gabon 30.8150 26.9500 20.6400
## Luanda, Angola 29.6450 30.5050 36.3850
## Khartoum, Sudan 5.3075 6.1675 5.1625
## Lusaka, Zambia 0.0000 4.5900 10.1750
## Nairobi, Kenya 4.5900 0.0000 6.3100
## Niamey, Niger 10.1750 6.3100 0.0000
## Kosongo, D.R. Congo 1.8650 2.7250 8.6050
## Ndjamena, Chad 5.2750 4.4200 8.1625
## Kosongo, D.R. Congo Ndjamena, Chad
## New York, NY 21.0450 20.6025
## Jacksonville, FL 21.1525 20.7100
## Dakar, Senegal 41.7250 41.2825
## Libreville, Gabon 29.2450 28.3000
## Luanda, Angola 27.7800 34.2225
## Khartoum, Sudan 3.4425 3.0000
## Lusaka, Zambia 1.8650 5.2750
## Nairobi, Kenya 2.7250 4.4200
## Niamey, Niger 8.6050 8.1625
## Kosongo, D.R. Congo 0.0000 6.4425
## Ndjamena, Chad 6.4425 0.0000all_shortest_paths(net, c("New York, NY", 'Jacksonville, FL'),
c('Kosongo, D.R. Congo' ,"Ndjamena, Chad",
'Niamey, Niger'))$res[[1]]## + 3/11 vertices, named, from 74ae952:
## [1] New York, NY Khartoum, Sudan Niamey, Niger# New York, NY > Khartoum, Sudan > Niamey, Niger
distances(net, c("New York, NY", 'Jacksonville, FL'),
c('Kosongo, D.R. Congo' ,"Ndjamena, Chad",
'Niamey, Niger'))## Kosongo, D.R. Congo Ndjamena, Chad Niamey, Niger
## New York, NY 21.0450 20.6025 22.7650
## Jacksonville, FL 21.1525 20.7100 22.8725# Kosongo, D.R. Congo Ndjamena, Chad Niamey, Niger
#New York, NY 21.04 20.60 22.76
#Jacksonville, FL 21.15 20.71 22.87
shortMatrix<- mst(net, weights = NULL)
shortMatrix## IGRAPH 74d2300 DNW- 11 10 --
## + attr: layout (g/n), name (v/c), Requirements (v/n), route (v/c),
## | color (v/c), Type (e/c), Distance (e/n), Cost (e/n), Capacity
## | (e/n), Speed (e/n), Time (e/n), Max.Airplanes (e/n), Max.Trucks
## | (e/n), Max (e/n), ID (e/c), weight (e/n), color (e/c)
## + edges from 74d2300 (vertex names):
## [1] New York, NY ->Khartoum, Sudan
## [2] Jacksonville, FL ->Khartoum, Sudan
## [3] Libreville, Gabon->Niamey, Niger
## [4] Khartoum, Sudan ->Niamey, Niger
## [5] Dakar, Senegal ->Niamey, Niger
## + ... omitted several edgesplot(shortMatrix, edge.arrow.size=.2, edge.label = round(E(net)$Time, 2))
3 - 2nd Plan considering cost and constraints
#Part 3 - Min Cost
# Set up model
min_cost <- make.lp(0, 30)
## Set objective fn
obj_fn <- as.integer(as.vector(edges$Cost))
set.objfn(min_cost, obj_fn)
# Set up constraints
#Input
add.constraint(min_cost, c( 150, 240, 150, 150, 240, 240, 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ), "=", 500000) #NY
add.constraint(min_cost, c( 0 , 0 , 0 , 0 , 0 , 0 , 150, 240, 150, 150, 240
, 240, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ), "=", 500000) #FL
#City Requirements
add.constraint(min_cost, c(-150, 0 , 0 , 0 , 0 , 0 ,-150, 0 , 0 , 0 , 0
, 0 , 150 , 0 , 0 , 0 , 0 , 0 , 150, 0
, 0 , 0 , 0 , 0 , 150, 0 , 0 , 0 , 0 , 0 ), "=", -150000) #Lusaka
add.constraint(min_cost, c( 0 ,-240, 0 , 0 , 0 , 0 ,0 ,-240, 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,17.7
, 0 , 0 , 0 , 0 , 0 ,17.7 , 0 , 0 , 0 , 0 ), "=", -100000) #Libreville
add.constraint(min_cost, c( 0 ,0 ,-150, 0 , 0 , 0 ,0 ,0 ,-150, 0 , 0
, 0 , 0 , 0 ,150 , 0 , 0 , 0 , 0 , 0
,150 , 0 , 0 , 0 , 0 , 0 , 150 , 0 , 0 , 0 ), "=", -120000) #Nairobi
add.constraint(min_cost, c( 0 ,0 ,0 ,-150, 0 , 0 ,0 ,0 ,0 ,-150, 0
, 0 , 0 , 0 , 0 ,150 , 0 , 0 , 0 , 0
, 0 ,150 , 0 , 0 , 0 , 0 , 0 , 150, 0 , 0 ), "=", -90000) #Khartoum
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,-240 , 0 ,0 ,0 ,0 ,0
,-240, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 ,17.7 , 0 , 0 , 0 , 0 , 0 ,17.7 , 0 ), "=", -130000) #Luanda
add.constraint(min_cost, c( 0 ,0 ,0 ,0 , 0 ,-240,0 ,0 ,0 ,0 , 0
,-240, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 ,17.7 , 0 , 0 , 0 , 0 , 0 ,17.7 ), "=", -50000) #Dakar
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 ,-150 , 0 ,-150,-150, 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ), "=", -100000) #Niamey Air routes only
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 , 0 , 0 , 0 , 0 , 0 , 0 ,-150,-17.7,
-150,-150,-17.7,-17.7, 0 , 0 , 0 , 0 , 0 , 0 ), "=", -180000) #Kosongo
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 ,-150,-17.7,-150 ,-150,-17.7,-17.7), "=", -80000) #Ndjamena
#additional constraint
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 ,1 , 0 , 0 ,1 ,1), "<=", 840) #Ndjmamena Truck constraint
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 ,1 , 0 , 0 , 0 , 0 , 0 ), "<=", (200)) #200 flights from tLusaka-Ndjmamena constrain
add.constraint(min_cost, c( 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0
,0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
, 0 , 0 , 0 , 0 , 0 , 0 ,1 , 0 , 0 ), "<=", (200)) #200 flights from Khartoum-Ndjmamena constraint
#set names
dimnames(min_cost) <- list(c("New York", "Jacksonville","Lusaka",
"Libreville", "Nairobi", "Khartoum", "Luanda",
"Dakar", "Niamey", "Kosongo", "Ndjamena",
"Ndjamena Truck Limit", "Lusaka->Ndjmamena limited Flights",
"Khartoum->Ndjmamena limited Flights"), as.vector(edges$ID) )
# Write to view the algebraic formulation
write.lp(min_cost, "5260_S18_minterm_min_cost.lp",type = 'lp')
# Solve the model
solve(min_cost)## [1] 0# Make results and sensitivity table
ps <- get.primal.solution(min_cost)
obj_sa <- get.sensitivity.obj(min_cost)
rhs_sa <- get.sensitivity.rhs(min_cost)
nv <- length(get.variables(min_cost))
mc <- length(get.constr.type(min_cost))
ov <- paste0("Objective Value = ", ps[1])
sa_tab <- rbind(ps[2:(nv + mc + 1)],
round(c(rhs_sa$duals[1:mc], obj_fn), 2),
round(c(rhs_sa$dualsfrom[1:mc],obj_sa$objfrom), 2),
round(c(rhs_sa$dualstill[1:mc],obj_sa$objtill), 2))
colnames(sa_tab) <- c(rownames(min_cost), colnames(min_cost))
rownames(sa_tab) <- c("solution", "duals/coef", "Sens From", "Sens Till")
# Objective value and sensitivity analysis table Transposing for better quality
m1<- as.data.frame(sa_tab)
tm1 <- transpose(m1)
setnames(tm1, rownames(m1))
colnames(tm1) <- rownames(m1)
rownames(tm1) <- colnames(m1)
ov## [1] "Objective Value = 310861299.435028"tm1## solution duals/coef
## New York 500000.0000 373.33
## Jacksonville 500000.0000 420.00
## Lusaka -150000.0000 40.00
## Libreville -100000.0000 248.33
## Nairobi -120000.0000 13.33
## Khartoum -90000.0000 93.33
## Luanda -130000.0000 248.33
## Dakar -50000.0000 240.00
## Niamey -100000.0000 -53.33
## Kosongo -180000.0000 22.34
## Ndjamena -80000.0000 0.00
## Ndjamena Truck Limit 0.0000 0.00
## Lusaka->Ndjmamena limited Flights 0.0000 0.00
## Khartoum->Ndjmamena limited Flights 200.0000 -10000.00
## New York, NY > Lusaka, Zambia 266.6667 50000.00
## New York, NY > Libreville, Gabon 1166.6667 30000.00
## New York, NY > Nairobi, Kenya 0.0000 55000.00
## New York, NY > Khartoum, Sudan 0.0000 45000.00
## New York, NY > Luanda, Angola 541.6667 30000.00
## New York, NY > Dakar, Senegal 208.3333 32000.00
## Jacksonville, FL > Lusaka, Zambia 733.3333 57000.00
## Jacksonville, FL > Libreville, Gabon 0.0000 48000.00
## Jacksonville, FL > Nairobi, Kenya 1133.3333 61000.00
## Jacksonville, FL > Khartoum, Sudan 1466.6667 49000.00
## Jacksonville, FL > Luanda, Angola 0.0000 44000.00
## Jacksonville, FL > Dakar, Senegal 0.0000 56000.00
## Lusaka, Zambia > Niamey, Niger 0.0000 24000.00
## Libreville, Gabon > Niamey, Niger 0.0000 3000.00
## Nairobi, Kenya > Niamey, Niger 0.0000 28000.00
## Khartoum, Sudan > Niamey, Niger 666.6667 22000.00
## Luanda, Angola > Niamey, Niger 0.0000 3000.00
## Dakar, Senegal > Niamey, Niger 0.0000 5000.00
## Lusaka, Zambia > Kosongo, D.R. Congo 0.0000 22000.00
## Libreville, Gabon > Kosongo, D.R. Congo 10169.4915 4000.00
## Nairobi, Kenya > Kosongo, D.R. Congo 0.0000 25000.00
## Khartoum, Sudan > Kosongo, D.R. Congo 0.0000 19000.00
## Luanda, Angola > Kosongo, D.R. Congo 0.0000 5000.00
## Dakar, Senegal > Kosongo, D.R. Congo 0.0000 5000.00
## Lusaka, Zambia > Ndjamena, Chad 0.0000 23000.00
## Libreville, Gabon > Ndjamena, Chad 0.0000 7000.00
## Nairobi, Kenya > Ndjamena, Chad 333.3333 2000.00
## Khartoum, Sudan > Ndjamena, Chad 200.0000 4000.00
## Luanda, Angola > Ndjamena, Chad 0.0000 8000.00
## Dakar, Senegal > Ndjamena, Chad 0.0000 9000.00
## Sens From Sens Till
## New York 5.000000e+05 5.0000e+05
## Jacksonville 5.000000e+05 5.0000e+05
## Lusaka -1.500000e+05 -1.5000e+05
## Libreville -1.000000e+05 -1.0000e+05
## Nairobi -1.200000e+05 -1.2000e+05
## Khartoum -9.000000e+04 -9.0000e+04
## Luanda -1.300000e+05 -1.3000e+05
## Dakar -5.000000e+04 -5.0000e+04
## Niamey -1.000000e+05 -1.0000e+05
## Kosongo -1.800000e+05 -1.8000e+05
## Ndjamena -1.000000e+30 1.0000e+30
## Ndjamena Truck Limit -1.000000e+30 1.0000e+30
## Lusaka->Ndjmamena limited Flights -1.000000e+30 1.0000e+30
## Khartoum->Ndjmamena limited Flights 0.000000e+00 5.3333e+02
## New York, NY > Lusaka, Zambia 4.825000e+04 5.1000e+04
## New York, NY > Libreville, Gabon -5.315250e+03 3.6800e+04
## New York, NY > Nairobi, Kenya 5.400000e+04 1.0000e+30
## New York, NY > Khartoum, Sudan 4.200000e+04 1.0000e+30
## New York, NY > Luanda, Angola 1.644068e+04 3.2800e+04
## New York, NY > Dakar, Senegal 1.644068e+04 4.4800e+04
## Jacksonville, FL > Lusaka, Zambia 5.600000e+04 5.8750e+04
## Jacksonville, FL > Libreville, Gabon 4.120000e+04 1.0000e+30
## Jacksonville, FL > Nairobi, Kenya 5.100000e+04 6.2000e+04
## Jacksonville, FL > Khartoum, Sudan 4.064831e+04 5.2000e+04
## Jacksonville, FL > Luanda, Angola 4.120000e+04 1.0000e+30
## Jacksonville, FL > Dakar, Senegal 4.320000e+04 1.0000e+30
## Lusaka, Zambia > Niamey, Niger 1.400000e+04 1.0000e+30
## Libreville, Gabon > Niamey, Niger 3.000000e+03 1.0000e+30
## Nairobi, Kenya > Niamey, Niger 1.000000e+04 1.0000e+30
## Khartoum, Sudan > Niamey, Niger -1.000000e+30 3.2000e+04
## Luanda, Angola > Niamey, Niger 3.000000e+03 1.0000e+30
## Dakar, Senegal > Niamey, Niger 5.000000e+03 1.0000e+30
## Lusaka, Zambia > Kosongo, D.R. Congo 2.648310e+03 1.0000e+30
## Libreville, Gabon > Kosongo, D.R. Congo -1.000000e+30 4.9855e+03
## Nairobi, Kenya > Kosongo, D.R. Congo -1.351690e+03 1.0000e+30
## Khartoum, Sudan > Kosongo, D.R. Congo 1.064831e+04 1.0000e+30
## Luanda, Angola > Kosongo, D.R. Congo 4.000000e+03 1.0000e+30
## Dakar, Senegal > Kosongo, D.R. Congo 3.852500e+03 1.0000e+30
## Lusaka, Zambia > Ndjamena, Chad 6.000000e+03 1.0000e+30
## Libreville, Gabon > Ndjamena, Chad 4.395500e+03 1.0000e+30
## Nairobi, Kenya > Ndjamena, Chad -8.000000e+03 1.9000e+04
## Khartoum, Sudan > Ndjamena, Chad -1.000000e+30 1.4000e+04
## Luanda, Angola > Ndjamena, Chad 4.395500e+03 1.0000e+30
## Dakar, Senegal > Ndjamena, Chad 4.248000e+03 1.0000e+30Graph the Min Cost Solution
# Include solution in edges dataframe
edges$flow <- get.variables(min_cost)
edges$Mincost <- edges$flow * edges$Cost
g <- edges %>%
# creating igraph: "from" and "to" fields in the first two colums
select(From, To, ID, Capacity, Cost, Type, flow, Mincost) %>%
# Make into graph object
graph_from_data_frame()
#Add route attribute
V(g)$route <- c("From","From","To","To","To","To","To","To","To","To","To")
V(g)$color <- c("gold","green")[1+(V(net)$route=="From")]
# Get some colours in to visualise routes
E(g)$color[E(g)$Type == 'Truck'] <- 'saddlebrown'
E(g)$color[E(g)$Type == 'Airplane'] <- 'forestgreen'
E(g)$color[E(g)$Type == 'Ship'] <- 'royalblue'
E(g)$color[E(g)$Mincost == 0] <- 'white'
g$layout <- matrix(c(-800, -800,
0, 0, 0, 0, 0, 0,
800, 800, 800,
225, 125,
300, 250, 200, 150, 100, 50,
250, 175, 100), nc = 2)
get.variables(min_cost)## [1] 266.6667 1166.6667 0.0000 0.0000 541.6667 208.3333
## [7] 733.3333 0.0000 1133.3333 1466.6667 0.0000 0.0000
## [13] 0.0000 0.0000 0.0000 666.6667 0.0000 0.0000
## [19] 0.0000 10169.4915 0.0000 0.0000 0.0000 0.0000
## [25] 0.0000 0.0000 333.3333 200.0000 0.0000 0.0000# Flow as edge size and colour
plot(g, edge.width = 15*E(g)$Mincost/max(E(g)$Mincost),
edge.arrow.size=.4,
edge.label = as.integer(E(g)$Mincost), vertex.size=35)
#[E(g)$Mincost >= 0]
#vertex.size=244 - Last Plan Max Flow with many constraints
#Maximum Flow
# Set up model
max_flow <- make.lp(0, 41)
lp.control(max_flow, sense = "max")## $anti.degen
## [1] "fixedvars" "stalling"
##
## $basis.crash
## [1] "none"
##
## $bb.depthlimit
## [1] -50
##
## $bb.floorfirst
## [1] "automatic"
##
## $bb.rule
## [1] "pseudononint" "greedy" "dynamic" "rcostfixing"
##
## $break.at.first
## [1] FALSE
##
## $break.at.value
## [1] 1e+30
##
## $epsilon
## epsb epsd epsel epsint epsperturb epspivot
## 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07
##
## $improve
## [1] "dualfeas" "thetagap"
##
## $infinite
## [1] 1e+30
##
## $maxpivot
## [1] 250
##
## $mip.gap
## absolute relative
## 1e-11 1e-11
##
## $negrange
## [1] -1e+06
##
## $obj.in.basis
## [1] TRUE
##
## $pivoting
## [1] "devex" "adaptive"
##
## $presolve
## [1] "none"
##
## $scalelimit
## [1] 5
##
## $scaling
## [1] "geometric" "equilibrate" "integers"
##
## $sense
## [1] "maximize"
##
## $simplextype
## [1] "dual" "primal"
##
## $timeout
## [1] 0
##
## $verbose
## [1] "neutral"## Set objective fn
obj_fn <- c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1)
set.objfn(max_flow, obj_fn)
# Set up constraints
add.constraint(max_flow, c( 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 1000000)#inflow
add.constraint(max_flow, c(-1,0,150,240,150,150,240,240,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "=", 0 ) #NY
add.constraint(max_flow, c(0,-1,0,0,0,0,0,0,150,240,150,150,240,240,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "=", 0) #FL
add.constraint(max_flow, c(0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0,0,0,0), "=", 0) #Lusaka
add.constraint(max_flow, c(0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0,0,0,0,0),"=", 0) #Libreville
add.constraint(max_flow, c(0,0,0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0,0), "=", 0) #Nairobi
add.constraint(max_flow, c(0,0,0,0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0), "=", 0) #Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0,0),"=", 0) #Luanda
add.constraint(max_flow, c(0,0,0,0,0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0), "=", 0) #Dakar
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0),"=", 0) #Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0),"=", 0) #Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,1),"=", 0) #Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1), "<=", 1000000) #OUtflow
# Air Constraints
add.constraint(max_flow, c(0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #NY-Lusak
add.constraint(max_flow, c(0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #NY-Nairobi
add.constraint(max_flow, c(0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #NY-Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #FL-Lusaka
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 700) #FL-Nairobi
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 600) #FL-Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 200) #Lusaka-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 0) #Nairobi-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Khartoum-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 140) #Lusaka-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 40 ) #Nairobi-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 80 ) #Khartoum-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 0 ) #Lusaka-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Nairobi-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0), "<=", 40 ) #Khartoum-Ndja
# Truck Contraints
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 250) #Lunda-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0), "<=", 240) #Lunda-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Lib-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 160) #Lib-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 700) #Dakar-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0), "<=", 450) #Dakar-Ndjamena
# City REquirements Constraints
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0), "<=", 150000) #Lusaka
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0), "<=", 100000) #Liber
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0), "<=", 120000) #Nairobi
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0), "<=", 90000) #Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0), "<=", 130000) #Lunada
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0), "<=", 50000) #Dakar
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0), "<=", 100000) #Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0), "<=", 180000) #Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1), "<=", 80000) #Ndjamena
dimnames(max_flow) <- list(c("Inflow","New York", "Jacksonville","Lusaka", "Libreville", "Nairobi",
"Khartoum", "Luanda", "Dakar", "Niamey", "Kosongo", "Ndjamena", "Max Outflow",
"Ny-Lusaka AirC", "NY-Nairobi AirC", "NY-Khartoum AirC",
"JAX-Lusaka AirC", "JAX-Nairobi AirC","JAX-Khartoum AirC",
"Lusaka-Niamey AirC", "Nairobi-Niamey AirC", "Khartoum-Niamey AirC",
"Lusaka-Kosongo AirC","Nairobi-Kosongo AirC", "Khartoum-Kosongo AirC",
"Lusaka-Ndjamena AirC", "Nairobi-Ndjamena AirC", "Khartoum-Ndjamena AirC",
"Luanda-Kosongo TruckC", "Luanda-Ndjamena TruckC", "Libreville-Kosongo TruckC",
"Libreville-Ndjamena TruckC", "Dakar-Kosongo TruckC", "Dakar-Ndjamena TruckC",
"LusakaR", "LibrevilleR", "NairobiR", "KhartoumR",
"LuandaR", "DakarR", "NiameyR", "KosongoR", "NdjamenaR"),
c("I-NY", "I-JAX", as.vector(edges$ID), "Lusaka-O", "Libreville-O",
"Nairobi-O", "Khartoum-O", "Luanda-O","Dakar-O", "Niamey-O",
"Kosongo-O", "Ndjamena-O") )
# Write to view the algebraic formulation
write.lp(max_flow, "5260_S18_minterm_max_flow.lp",type = 'lp')
# Solve the model
solve(max_flow)## [1] 0# Make results and sensitivity table
ps <- get.primal.solution(max_flow)
obj_sa <- get.sensitivity.obj(max_flow)
rhs_sa <- get.sensitivity.rhs(max_flow)
nv <- length(get.variables(max_flow))
mc <- length(get.constr.type(max_flow))
ov <- paste0("Objective Value = ", ps[1])
sa_tab <- rbind(ps[2:(nv + mc + 1)],
round(c(rhs_sa$duals[1:mc], obj_fn), 2),
round(c(rhs_sa$dualsfrom[1:mc],obj_sa$objfrom), 2),
round(c(rhs_sa$dualstill[1:mc],obj_sa$objtill), 2))
colnames(sa_tab) <- c(rownames(max_flow), colnames(max_flow))
rownames(sa_tab) <- c("solution", "duals/coef", "Sens From", "Sens Till")
# Objective value and sensitivity analysis table Transposing for better quality
m2<- as.data.frame(sa_tab)
tm2 <- transpose(m2)
setnames(tm2, rownames(m2))
colnames(tm2) <- rownames(m2)
rownames(tm2) <- colnames(m2)
ov## [1] "Objective Value = 816170"tm3<- as.data.frame(tm2)
tm3## solution duals/coef
## Inflow 8.161700e+05 0.0
## New York 1.455192e-10 0.0
## Jacksonville 0.000000e+00 0.0
## Lusaka 0.000000e+00 1.0
## Libreville 0.000000e+00 0.0
## Nairobi 0.000000e+00 0.0
## Khartoum 0.000000e+00 0.0
## Luanda 0.000000e+00 0.0
## Dakar 0.000000e+00 0.0
## Niamey 0.000000e+00 0.0
## Kosongo 0.000000e+00 1.0
## Ndjamena 0.000000e+00 1.0
## Max Outflow -8.161700e+05 0.0
## Ny-Lusaka AirC 3.000000e+02 150.0
## NY-Nairobi AirC 5.000000e+02 0.0
## NY-Khartoum AirC 5.000000e+02 0.0
## JAX-Lusaka AirC 5.000000e+02 150.0
## JAX-Nairobi AirC 6.400000e+02 0.0
## JAX-Khartoum AirC 5.200000e+02 0.0
## Lusaka-Niamey AirC 0.000000e+00 0.0
## Nairobi-Niamey AirC 0.000000e+00 0.0
## Khartoum-Niamey AirC 3.000000e+02 0.0
## Lusaka-Kosongo AirC 0.000000e+00 0.0
## Nairobi-Kosongo AirC 4.000000e+01 150.0
## Khartoum-Kosongo AirC 8.000000e+01 150.0
## Lusaka-Ndjamena AirC 0.000000e+00 0.0
## Nairobi-Ndjamena AirC 3.000000e+02 150.0
## Khartoum-Ndjamena AirC 4.000000e+01 150.0
## Luanda-Kosongo TruckC 2.500000e+02 17.7
## Luanda-Ndjamena TruckC 2.400000e+02 17.7
## Libreville-Kosongo TruckC 3.000000e+02 17.7
## Libreville-Ndjamena TruckC 1.600000e+02 17.7
## Dakar-Kosongo TruckC 7.000000e+02 17.7
## Dakar-Ndjamena TruckC 4.500000e+02 17.7
## LusakaR 1.200000e+05 0.0
## LibrevilleR 1.000000e+05 1.0
## NairobiR 1.200000e+05 1.0
## KhartoumR 9.000000e+04 1.0
## LuandaR 1.300000e+05 1.0
## DakarR 5.000000e+04 1.0
## NiameyR 1.000000e+05 1.0
## KosongoR 4.012500e+04 0.0
## NdjamenaR 6.604500e+04 0.0
## I-NY 5.671700e+05 0.0
## I-JAX 2.490000e+05 0.0
## New York, NY > Lusaka, Zambia 3.000000e+02 0.0
## New York, NY > Libreville, Gabon 6.797583e+02 0.0
## New York, NY > Nairobi, Kenya 5.000000e+02 0.0
## New York, NY > Khartoum, Sudan 5.000000e+02 0.0
## New York, NY > Luanda, Angola 5.778042e+02 0.0
## New York, NY > Dakar, Senegal 2.931458e+02 0.0
## Jacksonville, FL > Lusaka, Zambia 5.000000e+02 0.0
## Jacksonville, FL > Libreville, Gabon 0.000000e+00 0.0
## Jacksonville, FL > Nairobi, Kenya 6.400000e+02 0.0
## Jacksonville, FL > Khartoum, Sudan 5.200000e+02 0.0
## Jacksonville, FL > Luanda, Angola 0.000000e+00 0.0
## Jacksonville, FL > Dakar, Senegal 0.000000e+00 0.0
## Lusaka, Zambia > Niamey, Niger 0.000000e+00 0.0
## Libreville, Gabon > Niamey, Niger 3.107345e+03 0.0
## Nairobi, Kenya > Niamey, Niger 0.000000e+00 0.0
## Khartoum, Sudan > Niamey, Niger 3.000000e+02 0.0
## Luanda, Angola > Niamey, Niger 0.000000e+00 0.0
## Dakar, Senegal > Niamey, Niger 0.000000e+00 0.0
## Lusaka, Zambia > Kosongo, D.R. Congo 0.000000e+00 0.0
## Libreville, Gabon > Kosongo, D.R. Congo 3.000000e+02 0.0
## Nairobi, Kenya > Kosongo, D.R. Congo 4.000000e+01 0.0
## Khartoum, Sudan > Kosongo, D.R. Congo 8.000000e+01 0.0
## Luanda, Angola > Kosongo, D.R. Congo 2.500000e+02 0.0
## Dakar, Senegal > Kosongo, D.R. Congo 7.000000e+02 0.0
## Lusaka, Zambia > Ndjamena, Chad 0.000000e+00 0.0
## Libreville, Gabon > Ndjamena, Chad 1.600000e+02 0.0
## Nairobi, Kenya > Ndjamena, Chad 3.000000e+02 0.0
## Khartoum, Sudan > Ndjamena, Chad 4.000000e+01 0.0
## Luanda, Angola > Ndjamena, Chad 2.400000e+02 0.0
## Dakar, Senegal > Ndjamena, Chad 4.500000e+02 0.0
## Lusaka-O 1.200000e+05 1.0
## Libreville-O 1.000000e+05 1.0
## Nairobi-O 1.200000e+05 1.0
## Khartoum-O 9.000000e+04 1.0
## Luanda-O 1.300000e+05 1.0
## Dakar-O 5.000000e+04 1.0
## Niamey-O 1.000000e+05 1.0
## Kosongo-O 4.012500e+04 1.0
## Ndjamena-O 6.604500e+04 1.0
## Sens From Sens Till
## Inflow -1.0000e+30 1.00000e+30
## New York -1.8383e+05 5.67170e+05
## Jacksonville -1.8383e+05 2.49000e+05
## Lusaka -1.2000e+05 3.00000e+04
## Libreville -1.8383e+05 1.63142e+05
## Nairobi -9.0000e+03 9.60000e+04
## Khartoum -1.2000e+04 7.80000e+04
## Luanda -1.8383e+05 1.38673e+05
## Dakar -1.8383e+05 7.03550e+04
## Niamey -1.8383e+05 5.50000e+04
## Kosongo -4.0125e+04 1.39875e+05
## Ndjamena -6.6045e+04 1.39550e+04
## Max Outflow -1.0000e+30 1.00000e+30
## Ny-Lusaka AirC 0.0000e+00 5.00000e+02
## NY-Nairobi AirC 4.4000e+02 1.14000e+03
## NY-Khartoum AirC 4.2000e+02 1.02000e+03
## JAX-Lusaka AirC 0.0000e+00 7.00000e+02
## JAX-Nairobi AirC -1.0000e+30 1.00000e+30
## JAX-Khartoum AirC -1.0000e+30 1.00000e+30
## Lusaka-Niamey AirC -1.0000e+30 1.00000e+30
## Nairobi-Niamey AirC 0.0000e+00 6.00000e+01
## Khartoum-Niamey AirC 0.0000e+00 3.80000e+02
## Lusaka-Kosongo AirC -1.0000e+30 1.00000e+30
## Nairobi-Kosongo AirC 0.0000e+00 1.00000e+02
## Khartoum-Kosongo AirC 0.0000e+00 1.60000e+02
## Lusaka-Ndjamena AirC -1.0000e+30 1.00000e+30
## Nairobi-Ndjamena AirC 0.0000e+00 3.60000e+02
## Khartoum-Ndjamena AirC 0.0000e+00 1.20000e+02
## Luanda-Kosongo TruckC 0.0000e+00 8.15254e+03
## Luanda-Ndjamena TruckC 0.0000e+00 1.02842e+03
## Libreville-Kosongo TruckC 0.0000e+00 8.20254e+03
## Libreville-Ndjamena TruckC 0.0000e+00 9.48420e+02
## Dakar-Kosongo TruckC 0.0000e+00 8.60254e+03
## Dakar-Ndjamena TruckC 0.0000e+00 1.23842e+03
## LusakaR -1.0000e+30 1.00000e+30
## LibrevilleR 0.0000e+00 2.83830e+05
## NairobiR 2.4000e+04 1.29000e+05
## KhartoumR 1.2000e+04 1.02000e+05
## LuandaR 0.0000e+00 3.13830e+05
## DakarR 0.0000e+00 2.33830e+05
## NiameyR 4.5000e+04 2.83830e+05
## KosongoR -1.0000e+30 1.00000e+30
## NdjamenaR -1.0000e+30 1.00000e+30
## I-NY 0.0000e+00 0.00000e+00
## I-JAX 0.0000e+00 0.00000e+00
## New York, NY > Lusaka, Zambia -1.5000e+02 1.00000e+30
## New York, NY > Libreville, Gabon 0.0000e+00 0.00000e+00
## New York, NY > Nairobi, Kenya 0.0000e+00 1.00000e+30
## New York, NY > Khartoum, Sudan 0.0000e+00 1.00000e+30
## New York, NY > Luanda, Angola 0.0000e+00 0.00000e+00
## New York, NY > Dakar, Senegal 0.0000e+00 0.00000e+00
## Jacksonville, FL > Lusaka, Zambia -1.5000e+02 1.00000e+30
## Jacksonville, FL > Libreville, Gabon -1.0000e+30 0.00000e+00
## Jacksonville, FL > Nairobi, Kenya 0.0000e+00 0.00000e+00
## Jacksonville, FL > Khartoum, Sudan 0.0000e+00 0.00000e+00
## Jacksonville, FL > Luanda, Angola -1.0000e+30 0.00000e+00
## Jacksonville, FL > Dakar, Senegal -1.0000e+30 0.00000e+00
## Lusaka, Zambia > Niamey, Niger -1.0000e+30 1.50000e+02
## Libreville, Gabon > Niamey, Niger 0.0000e+00 0.00000e+00
## Nairobi, Kenya > Niamey, Niger -1.0000e+30 1.00000e+30
## Khartoum, Sudan > Niamey, Niger 0.0000e+00 1.00000e+30
## Luanda, Angola > Niamey, Niger -1.0000e+30 0.00000e+00
## Dakar, Senegal > Niamey, Niger -1.0000e+30 0.00000e+00
## Lusaka, Zambia > Kosongo, D.R. Congo -1.0000e+30 0.00000e+00
## Libreville, Gabon > Kosongo, D.R. Congo -1.7700e+01 1.00000e+30
## Nairobi, Kenya > Kosongo, D.R. Congo -1.5000e+02 1.00000e+30
## Khartoum, Sudan > Kosongo, D.R. Congo -1.5000e+02 1.00000e+30
## Luanda, Angola > Kosongo, D.R. Congo -1.7700e+01 1.00000e+30
## Dakar, Senegal > Kosongo, D.R. Congo -1.7700e+01 1.00000e+30
## Lusaka, Zambia > Ndjamena, Chad -1.0000e+30 0.00000e+00
## Libreville, Gabon > Ndjamena, Chad -1.7700e+01 1.00000e+30
## Nairobi, Kenya > Ndjamena, Chad -1.5000e+02 1.00000e+30
## Khartoum, Sudan > Ndjamena, Chad -1.5000e+02 1.00000e+30
## Luanda, Angola > Ndjamena, Chad -1.7700e+01 1.00000e+30
## Dakar, Senegal > Ndjamena, Chad -1.7700e+01 1.00000e+30
## Lusaka-O 1.0000e+00 1.00000e+30
## Libreville-O 0.0000e+00 1.00000e+30
## Nairobi-O 0.0000e+00 1.00000e+30
## Khartoum-O 0.0000e+00 1.00000e+30
## Luanda-O 0.0000e+00 1.00000e+30
## Dakar-O 0.0000e+00 1.00000e+30
## Niamey-O 0.0000e+00 1.00000e+30
## Kosongo-O 0.0000e+00 1.00000e+00
## Ndjamena-O 0.0000e+00 1.00000e+00#get.variables(max_flow)Graph Max Cost Solution
# Include solution in edges dataframe
edges$Mflow <- get.variables(max_flow)[3:32]
edges$TotalAid <- edges$Mflow * edges$Capacity
#create size for vertecies
#V()$Mflow <- get.variables(max_flow)[31:41] #tried playing with size of vertecies but failed
#nodes$Mflow[1] <- get.variables(max_flow)[1]
#nodes$Mflow[2] <- get.variables(max_flow)[2]
g1 <- edges %>%
# creating igraph: "from" and "to" fields in the first two colums
select(From, To, ID, Capacity, Cost, Type, Mflow, TotalAid) %>%
# Make into graph object
graph_from_data_frame()
#Add route and node attribute
V(g1)$route <- c("From","From","To","To","To","To","To","To","To","To","To")
V(g1)$color <- c("gold","green")[1+(V(net)$route=="From")]
V(g1)$Mflow <- get.variables(max_flow)[31:41] #tried playing with size of vertecies but failed
V(g1)$Mflow[1] <- get.variables(max_flow)[1]
V(g1)$Mflow[2] <- get.variables(max_flow)[2]
# Get some colours in to visualise routes
E(g1)$color[E(g1)$Type == 'Truck'] <- 'saddlebrown'
E(g1)$color[E(g1)$Type == 'Airplane'] <- 'forestgreen'
E(g1)$color[E(g1)$Type == 'Ship'] <- 'royalblue'
E(g1)$color[E(g1)$Mflow == 0] <- 'white'
g1$layout <- matrix(c(-800, -800,
0, 0, 0, 0, 0, 0,
800, 800, 800,
225, 125,
300, 250, 200, 150, 100, 50,
250, 175, 100), nc = 2)
plot(g1, edge.width = 20*E(g1)$TotalAid/max(E(g1)$TotalAid) ,
edge.arrow.size=.3,
edge.label = as.integer(E(g1)$TotalAid),
vertex.size= 50*V(g1)$Mflow/max(V(g1)$Mflow))
#get.variables(max_flow)
E(g1)$TotalAid## [1] 45000 163142 75000 75000 138673 70355 75000 0 96000 78000
## [11] 0 0 0 55000 0 45000 0 0 0 5310
## [21] 6000 12000 4425 12390 0 2832 45000 6000 4248 79654 - Last Plan Testing Max Flow by relaxing some constraints to congos
#Maximum Flow
# Set up model
max_flow <- make.lp(0, 41)
lp.control(max_flow, sense = "max")## $anti.degen
## [1] "fixedvars" "stalling"
##
## $basis.crash
## [1] "none"
##
## $bb.depthlimit
## [1] -50
##
## $bb.floorfirst
## [1] "automatic"
##
## $bb.rule
## [1] "pseudononint" "greedy" "dynamic" "rcostfixing"
##
## $break.at.first
## [1] FALSE
##
## $break.at.value
## [1] 1e+30
##
## $epsilon
## epsb epsd epsel epsint epsperturb epspivot
## 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07
##
## $improve
## [1] "dualfeas" "thetagap"
##
## $infinite
## [1] 1e+30
##
## $maxpivot
## [1] 250
##
## $mip.gap
## absolute relative
## 1e-11 1e-11
##
## $negrange
## [1] -1e+06
##
## $obj.in.basis
## [1] TRUE
##
## $pivoting
## [1] "devex" "adaptive"
##
## $presolve
## [1] "none"
##
## $scalelimit
## [1] 5
##
## $scaling
## [1] "geometric" "equilibrate" "integers"
##
## $sense
## [1] "maximize"
##
## $simplextype
## [1] "dual" "primal"
##
## $timeout
## [1] 0
##
## $verbose
## [1] "neutral"## Set objective fn
obj_fn <- c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1)
set.objfn(max_flow, obj_fn)
# Set up constraints
add.constraint(max_flow, c( 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 1000000)#inflow
add.constraint(max_flow, c(-1,0,150,240,150,150,240,240,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "=", 0 ) #NY
add.constraint(max_flow, c(0,-1,0,0,0,0,0,0,150,240,150,150,240,240,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "=", 0) #FL
add.constraint(max_flow, c(0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0,0,0,0), "=", 0) #Lusaka
add.constraint(max_flow, c(0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0,0,0,0,0),"=", 0) #Libreville
add.constraint(max_flow, c(0,0,0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0,0), "=", 0) #Nairobi
add.constraint(max_flow, c(0,0,0,0,0,-150,0,0,0,0,0,-150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,150,0,0,0,0,0,1,0,0,0,0,0), "=", 0) #Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0,0),"=", 0) #Luanda
add.constraint(max_flow, c(0,0,0,0,0,0,0,-240,0,0,0,0,0,-240,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,17.7,0,0,0,0,0,1,0,0,0), "=", 0) #Dakar
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0),"=", 0) #Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0),"=", 0) #Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-150,-17.7,-150,-150,-17.7,-17.7,0,0,0,0,0,0,0,0,1),"=", 0) #Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1), "<=", 1000000) #OUtflow
# Air Constraints
add.constraint(max_flow, c(0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #NY-Lusak
add.constraint(max_flow, c(0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #NY-Nairobi
add.constraint(max_flow, c(0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #NY-Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500) #FL-Lusaka
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 700) #FL-Nairobi
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 600) #FL-Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 200) #Lusaka-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 0) #Nairobi-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Khartoum-Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 140) #Lusaka-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 400 ) #Nairobi-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 500 ) #Khartoum-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 200 ) #Lusaka-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Nairobi-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0), "<=", 40 ) #Khartoum-Ndja
# Truck Contraints
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 250) #Lunda-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0), "<=", 240) #Lunda-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 300) #Lib-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 160) #Lib-Ndjamena
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), "<=", 700) #Dakar-Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0), "<=", 450) #Dakar-Ndjamena
# City REquirements Constraints
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0), "<=", 150000) #Lusaka
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0), "<=", 100000) #Liber
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0), "<=", 120000) #Nairobi
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0), "<=", 90000) #Khartoum
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0), "<=", 130000) #Lunada
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0), "<=", 50000) #Dakar
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0), "<=", 100000) #Niamey
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0), "<=", 180000) #Kosongo
add.constraint(max_flow, c(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1), "<=", 80000) #Ndjamena
dimnames(max_flow) <- list(c("Inflow","New York", "Jacksonville","Lusaka", "Libreville", "Nairobi",
"Khartoum", "Luanda", "Dakar", "Niamey", "Kosongo", "Ndjamena", "Max Outflow",
"Ny-Lusaka AirC", "NY-Nairobi AirC", "NY-Khartoum AirC",
"JAX-Lusaka AirC", "JAX-Nairobi AirC","JAX-Khartoum AirC",
"Lusaka-Niamey AirC", "Nairobi-Niamey AirC", "Khartoum-Niamey AirC",
"Lusaka-Kosongo AirC","Nairobi-Kosongo AirC", "Khartoum-Kosongo AirC",
"Lusaka-Ndjamena AirC", "Nairobi-Ndjamena AirC", "Khartoum-Ndjamena AirC",
"Luanda-Kosongo TruckC", "Luanda-Ndjamena TruckC", "Libreville-Kosongo TruckC",
"Libreville-Ndjamena TruckC", "Dakar-Kosongo TruckC", "Dakar-Ndjamena TruckC",
"LusakaR", "LibrevilleR", "NairobiR", "KhartoumR",
"LuandaR", "DakarR", "NiameyR", "KosongoR", "NdjamenaR"),
c("I-NY", "I-JAX", as.vector(edges$ID), "Lusaka-O", "Libreville-O",
"Nairobi-O", "Khartoum-O", "Luanda-O","Dakar-O", "Niamey-O",
"Kosongo-O", "Ndjamena-O") )
# Write to view the algebraic formulation
write.lp(max_flow, "5260_S18_minterm_max_flow.lp",type = 'lp')
# Solve the model
solve(max_flow)## [1] 0# Make results and sensitivity table
ps <- get.primal.solution(max_flow)
obj_sa <- get.sensitivity.obj(max_flow)
rhs_sa <- get.sensitivity.rhs(max_flow)
nv <- length(get.variables(max_flow))
mc <- length(get.constr.type(max_flow))
ov <- paste0("Objective Value = ", ps[1])
sa_tab <- rbind(ps[2:(nv + mc + 1)],
round(c(rhs_sa$duals[1:mc], obj_fn), 2),
round(c(rhs_sa$dualsfrom[1:mc],obj_sa$objfrom), 2),
round(c(rhs_sa$dualstill[1:mc],obj_sa$objtill), 2))
colnames(sa_tab) <- c(rownames(max_flow), colnames(max_flow))
rownames(sa_tab) <- c("solution", "duals/coef", "Sens From", "Sens Till")
# Objective value and sensitivity analysis table Transposing for better quality
m2<- as.data.frame(sa_tab)
tm2 <- transpose(m2)
setnames(tm2, rownames(m2))
colnames(tm2) <- rownames(m2)
rownames(tm2) <- colnames(m2)
ov## [1] "Objective Value = 882170"tm3<- as.data.frame(tm2)
tm3## solution duals/coef
## Inflow 8.821700e+05 0.0
## New York 1.455192e-10 0.0
## Jacksonville 0.000000e+00 0.0
## Lusaka 0.000000e+00 1.0
## Libreville 0.000000e+00 0.0
## Nairobi 0.000000e+00 1.0
## Khartoum 0.000000e+00 1.0
## Luanda 0.000000e+00 0.0
## Dakar 0.000000e+00 0.0
## Niamey 0.000000e+00 0.0
## Kosongo 0.000000e+00 1.0
## Ndjamena 0.000000e+00 1.0
## Max Outflow -8.821700e+05 0.0
## Ny-Lusaka AirC 3.000000e+02 150.0
## NY-Nairobi AirC 5.000000e+02 150.0
## NY-Khartoum AirC 5.000000e+02 150.0
## JAX-Lusaka AirC 5.000000e+02 150.0
## JAX-Nairobi AirC 7.000000e+02 150.0
## JAX-Khartoum AirC 6.000000e+02 150.0
## Lusaka-Niamey AirC 0.000000e+00 0.0
## Nairobi-Niamey AirC 0.000000e+00 0.0
## Khartoum-Niamey AirC 0.000000e+00 0.0
## Lusaka-Kosongo AirC 0.000000e+00 0.0
## Nairobi-Kosongo AirC 4.000000e+02 0.0
## Khartoum-Kosongo AirC 5.000000e+02 0.0
## Lusaka-Ndjamena AirC 0.000000e+00 0.0
## Nairobi-Ndjamena AirC 0.000000e+00 0.0
## Khartoum-Ndjamena AirC 0.000000e+00 0.0
## Luanda-Kosongo TruckC 2.500000e+02 17.7
## Luanda-Ndjamena TruckC 2.400000e+02 17.7
## Libreville-Kosongo TruckC 3.000000e+02 17.7
## Libreville-Ndjamena TruckC 1.600000e+02 17.7
## Dakar-Kosongo TruckC 7.000000e+02 17.7
## Dakar-Ndjamena TruckC 4.500000e+02 17.7
## LusakaR 1.200000e+05 0.0
## LibrevilleR 1.000000e+05 1.0
## NairobiR 1.200000e+05 0.0
## KhartoumR 9.000000e+04 0.0
## LuandaR 1.300000e+05 1.0
## DakarR 5.000000e+04 1.0
## NiameyR 1.000000e+05 1.0
## KosongoR 1.571250e+05 0.0
## NdjamenaR 1.504500e+04 0.0
## I-NY 6.121700e+05 0.0
## I-JAX 2.700000e+05 0.0
## New York, NY > Lusaka, Zambia 3.000000e+02 0.0
## New York, NY > Libreville, Gabon 8.672583e+02 0.0
## New York, NY > Nairobi, Kenya 5.000000e+02 0.0
## New York, NY > Khartoum, Sudan 5.000000e+02 0.0
## New York, NY > Luanda, Angola 5.778042e+02 0.0
## New York, NY > Dakar, Senegal 2.931458e+02 0.0
## Jacksonville, FL > Lusaka, Zambia 5.000000e+02 0.0
## Jacksonville, FL > Libreville, Gabon 0.000000e+00 0.0
## Jacksonville, FL > Nairobi, Kenya 7.000000e+02 0.0
## Jacksonville, FL > Khartoum, Sudan 6.000000e+02 0.0
## Jacksonville, FL > Luanda, Angola 0.000000e+00 0.0
## Jacksonville, FL > Dakar, Senegal 0.000000e+00 0.0
## Lusaka, Zambia > Niamey, Niger 0.000000e+00 0.0
## Libreville, Gabon > Niamey, Niger 5.649718e+03 0.0
## Nairobi, Kenya > Niamey, Niger 0.000000e+00 0.0
## Khartoum, Sudan > Niamey, Niger 0.000000e+00 0.0
## Luanda, Angola > Niamey, Niger 0.000000e+00 0.0
## Dakar, Senegal > Niamey, Niger 0.000000e+00 0.0
## Lusaka, Zambia > Kosongo, D.R. Congo 0.000000e+00 0.0
## Libreville, Gabon > Kosongo, D.R. Congo 3.000000e+02 0.0
## Nairobi, Kenya > Kosongo, D.R. Congo 4.000000e+02 0.0
## Khartoum, Sudan > Kosongo, D.R. Congo 5.000000e+02 0.0
## Luanda, Angola > Kosongo, D.R. Congo 2.500000e+02 0.0
## Dakar, Senegal > Kosongo, D.R. Congo 7.000000e+02 0.0
## Lusaka, Zambia > Ndjamena, Chad 0.000000e+00 0.0
## Libreville, Gabon > Ndjamena, Chad 1.600000e+02 0.0
## Nairobi, Kenya > Ndjamena, Chad 0.000000e+00 0.0
## Khartoum, Sudan > Ndjamena, Chad 0.000000e+00 0.0
## Luanda, Angola > Ndjamena, Chad 2.400000e+02 0.0
## Dakar, Senegal > Ndjamena, Chad 4.500000e+02 0.0
## Lusaka-O 1.200000e+05 1.0
## Libreville-O 1.000000e+05 1.0
## Nairobi-O 1.200000e+05 1.0
## Khartoum-O 9.000000e+04 1.0
## Luanda-O 1.300000e+05 1.0
## Dakar-O 5.000000e+04 1.0
## Niamey-O 1.000000e+05 1.0
## Kosongo-O 1.571250e+05 1.0
## Ndjamena-O 1.504500e+04 1.0
## Sens From Sens Till
## Inflow -1.00000e+30 1.00000e+30
## New York -1.17830e+05 6.12170e+05
## Jacksonville -1.17830e+05 2.70000e+05
## Lusaka -1.20000e+05 3.00000e+04
## Libreville -1.17830e+05 2.08142e+05
## Nairobi 0.00000e+00 4.50000e+04
## Khartoum 0.00000e+00 6.00000e+03
## Luanda -1.17830e+05 1.38673e+05
## Dakar -1.17830e+05 7.03550e+04
## Niamey -1.17830e+05 1.00000e+05
## Kosongo -1.57125e+05 2.28750e+04
## Ndjamena -1.50450e+04 6.49550e+04
## Max Outflow -1.00000e+30 1.00000e+30
## Ny-Lusaka AirC 0.00000e+00 5.00000e+02
## NY-Nairobi AirC 5.00000e+02 8.00000e+02
## NY-Khartoum AirC 5.00000e+02 5.40000e+02
## JAX-Lusaka AirC 0.00000e+00 7.00000e+02
## JAX-Nairobi AirC 7.00000e+02 1.00000e+03
## JAX-Khartoum AirC 6.00000e+02 6.40000e+02
## Lusaka-Niamey AirC -1.00000e+30 1.00000e+30
## Nairobi-Niamey AirC -1.00000e+30 1.00000e+30
## Khartoum-Niamey AirC -1.00000e+30 1.00000e+30
## Lusaka-Kosongo AirC -1.00000e+30 1.00000e+30
## Nairobi-Kosongo AirC 1.00000e+02 4.00000e+02
## Khartoum-Kosongo AirC 4.60000e+02 5.00000e+02
## Lusaka-Ndjamena AirC -1.00000e+30 1.00000e+30
## Nairobi-Ndjamena AirC -1.00000e+30 1.00000e+30
## Khartoum-Ndjamena AirC -1.00000e+30 1.00000e+30
## Luanda-Kosongo TruckC 0.00000e+00 1.54237e+03
## Luanda-Ndjamena TruckC 0.00000e+00 3.90977e+03
## Libreville-Kosongo TruckC 0.00000e+00 1.59237e+03
## Libreville-Ndjamena TruckC 0.00000e+00 3.82977e+03
## Dakar-Kosongo TruckC 0.00000e+00 1.99237e+03
## Dakar-Ndjamena TruckC 0.00000e+00 4.11977e+03
## LusakaR -1.00000e+30 1.00000e+30
## LibrevilleR 0.00000e+00 2.17830e+05
## NairobiR 7.50000e+04 1.20000e+05
## KhartoumR 8.40000e+04 9.00000e+04
## LuandaR 0.00000e+00 2.47830e+05
## DakarR 0.00000e+00 1.67830e+05
## NiameyR 0.00000e+00 2.17830e+05
## KosongoR -1.00000e+30 1.00000e+30
## NdjamenaR -1.00000e+30 1.00000e+30
## I-NY 0.00000e+00 1.00000e+30
## I-JAX -1.00000e+00 0.00000e+00
## New York, NY > Lusaka, Zambia -1.50000e+02 1.00000e+30
## New York, NY > Libreville, Gabon 0.00000e+00 1.00000e+30
## New York, NY > Nairobi, Kenya -1.50000e+02 1.00000e+30
## New York, NY > Khartoum, Sudan -1.50000e+02 1.00000e+30
## New York, NY > Luanda, Angola 0.00000e+00 0.00000e+00
## New York, NY > Dakar, Senegal 0.00000e+00 0.00000e+00
## Jacksonville, FL > Lusaka, Zambia -1.50000e+02 1.00000e+30
## Jacksonville, FL > Libreville, Gabon -1.00000e+30 0.00000e+00
## Jacksonville, FL > Nairobi, Kenya -1.50000e+02 1.00000e+30
## Jacksonville, FL > Khartoum, Sudan -1.50000e+02 1.00000e+30
## Jacksonville, FL > Luanda, Angola -1.00000e+30 0.00000e+00
## Jacksonville, FL > Dakar, Senegal -1.00000e+30 0.00000e+00
## Lusaka, Zambia > Niamey, Niger -1.00000e+30 1.50000e+02
## Libreville, Gabon > Niamey, Niger 0.00000e+00 1.00000e+30
## Nairobi, Kenya > Niamey, Niger -1.00000e+30 1.50000e+02
## Khartoum, Sudan > Niamey, Niger -1.00000e+30 1.50000e+02
## Luanda, Angola > Niamey, Niger -1.00000e+30 0.00000e+00
## Dakar, Senegal > Niamey, Niger -1.00000e+30 0.00000e+00
## Lusaka, Zambia > Kosongo, D.R. Congo -1.00000e+30 0.00000e+00
## Libreville, Gabon > Kosongo, D.R. Congo -1.77000e+01 1.00000e+30
## Nairobi, Kenya > Kosongo, D.R. Congo 0.00000e+00 1.00000e+30
## Khartoum, Sudan > Kosongo, D.R. Congo 0.00000e+00 1.00000e+30
## Luanda, Angola > Kosongo, D.R. Congo -1.77000e+01 1.00000e+30
## Dakar, Senegal > Kosongo, D.R. Congo -1.77000e+01 1.00000e+30
## Lusaka, Zambia > Ndjamena, Chad -1.00000e+30 0.00000e+00
## Libreville, Gabon > Ndjamena, Chad -1.77000e+01 1.00000e+30
## Nairobi, Kenya > Ndjamena, Chad -1.00000e+30 0.00000e+00
## Khartoum, Sudan > Ndjamena, Chad -1.00000e+30 0.00000e+00
## Luanda, Angola > Ndjamena, Chad -1.77000e+01 1.00000e+30
## Dakar, Senegal > Ndjamena, Chad -1.77000e+01 1.00000e+30
## Lusaka-O 1.00000e+00 1.00000e+30
## Libreville-O 0.00000e+00 1.00000e+30
## Nairobi-O 1.00000e+00 1.00000e+30
## Khartoum-O 1.00000e+00 1.00000e+30
## Luanda-O 0.00000e+00 1.00000e+30
## Dakar-O 0.00000e+00 1.00000e+30
## Niamey-O 0.00000e+00 1.00000e+30
## Kosongo-O 1.00000e+00 1.00000e+00
## Ndjamena-O 0.00000e+00 1.00000e+00#get.variables(max_flow)Graph Max Cost Solution
# Include solution in edges dataframe
edges$Mflow <- get.variables(max_flow)[3:32]
edges$TotalAid <- edges$Mflow * edges$Capacity
#create size for vertecies
nodes$Mflow2 <- get.variables(max_flow)[31:41] #tried playing with size of vertecies but failed
nodes$Mflow2[1] <- get.variables(max_flow)[1]
nodes$Mflow2[2] <- get.variables(max_flow)[2]
g1 <- edges %>%
# creating igraph: "from" and "to" fields in the first two colums
select(From, To, ID, Capacity, Cost, Type, Mflow, TotalAid) %>%
# Make into graph object
graph_from_data_frame()
#Add route and node attribute
V(g1)$route <- c("From","From","To","To","To","To","To","To","To","To","To")
V(g1)$color <- c("gold","green")[1+(V(net)$route=="From")]
V(g1)$Mflow <- get.variables(max_flow)[31:41] #tried playing with size of vertecies but failed
V(g1)$Mflow[1] <- get.variables(max_flow)[1]
V(g1)$Mflow[2] <- get.variables(max_flow)[2]
# Get some colours in to visualise routes
E(g1)$color[E(g1)$Type == 'Truck'] <- 'saddlebrown'
E(g1)$color[E(g1)$Type == 'Airplane'] <- 'forestgreen'
E(g1)$color[E(g1)$Type == 'Ship'] <- 'royalblue'
E(g1)$color[E(g1)$Mflow == 0] <- 'white'
g1$layout <- matrix(c(-800, -800,
0, 0, 0, 0, 0, 0,
800, 800, 800,
225, 125,
300, 250, 200, 150, 100, 50,
250, 175, 100), nc = 2)
plot(g1, edge.width = 20*E(g1)$TotalAid/max(E(g1)$TotalAid) ,
edge.arrow.size=.3,
edge.label = as.integer(E(g1)$TotalAid),
vertex.size= 50*V(g1)$Mflow/max(V(g1)$Mflow))
#get.variables(max_flow)
E(g1)$TotalAid## [1] 45000 208142 75000 75000 138673 70355 75000 0 105000 90000
## [11] 0 0 0 100000 0 0 0 0 0 5310
## [21] 60000 75000 4425 12390 0 2832 0 0 4248 7965Appendix for additional igraph data structure
Fuction to run Matrix
createConstraintsMatrix <- function(edges, total_flow) {
# Edge IDs to be used as names
names_edges <- edges$ID
# Number of edges
numberof_edges <- length(names_edges)
# Node IDs to be used as names
names_nodes <- c(edges$From, edges$To) %>% unique
# Number of nodes
numberof_nodes <- length(names_nodes)
# Build constraints matrix
constraints <- list(
lhs = NA,
dir = NA,
rhs = NA)
#Build capacity constraints by flowing through each edge should not be larger than capacity.
#add zero except the ones that matchs the edge
# Flow through individual edges
constraints$lhs <- edges$ID %>%
length %>%
diag %>%
set_colnames(edges$ID) %>%
set_rownames(edges$ID)
# should be smaller than or equal to
constraints$dir <- rep('<=', times = nrow(edges))
# than capacity
constraints$rhs <- edges$Max
#' Build node flow constraints For each node, find all edges that go to that node
nodeflow <- matrix(0,
nrow = numberof_nodes,
ncol = numberof_edges,
dimnames = list(names_nodes, names_edges))
for (i in names_nodes) {
# input arcs
edges_in <- edges %>%
filter(To == i) %>%
select(ID) %>%
unlist
# output arcs
edges_out <- edges %>%
filter(From == i) %>%
select(ID) %>%
unlist
# set input coefficients to 1
nodeflow[
rownames(nodeflow) == i,
colnames(nodeflow) %in% edges_in] <- 1
# set output coefficients to -1
nodeflow[
rownames(nodeflow) == i,
colnames(nodeflow) %in% edges_out] <- -1
}
# Source node is minimum ID number
# Sink node is maximum ID number
sourcenode_id <- min(edges$From)
targetnode_id <- max(edges$To)
# Keep node flow values for separate step below
nodeflow_source <- nodeflow[rownames(nodeflow) == sourcenode_id,]
nodeflow_target <- nodeflow[rownames(nodeflow) == targetnode_id,]
# Exclude them from node flow here
nodeflow <- nodeflow[!rownames(nodeflow) %in% c(sourcenode_id, targetnode_id),]
# Add nodeflow to the constraints list
constraints$lhs <- rbind(constraints$lhs, nodeflow)
constraints$dir <- c(constraints$dir, rep('==', times = nrow(nodeflow)))
constraints$rhs <- c(constraints$rhs, rep(0, times = nrow(nodeflow)))
#' Build constraints
# Add initialisation to the constraints list
constraints$lhs <- rbind(constraints$lhs,
source = nodeflow_source,
target = nodeflow_target)
constraints$dir <- c(constraints$dir, rep('==', times = 2))
# Flow should be negative for source, and positive for target
constraints$rhs <- c(constraints$rhs, total_flow * -1, total_flow)
return(constraints)
}
#Create My Matrix
constraintsMatrix <- createConstraintsMatrix(edges, 1000000)
#constraintsMatrix
#Set City Requirement
constraintsMatrix$rhs[31] <- 500000
constraintsMatrix$rhs[32] <- 500000
constraintsMatrix$rhs[33] <- -150000
constraintsMatrix$rhs[34] <- -100000
constraintsMatrix$rhs[35] <- -120000
constraintsMatrix$rhs[36] <- - 90000
constraintsMatrix$rhs[37] <- -130000
constraintsMatrix$rhs[38] <- -180000
constraintsMatrix$rhs[39] <- -80000
#Review data for Validity
CM <- as.data.frame(constraintsMatrix)
#glimpse(CM)
#CM
write.csv(CM, file = "MyData.csv")
#constraintsMatrix$lhs
#constraintsMatrix$dir
#constraintsMatrix$rhs
#plot.lpExtPtr(min_cost)
#get.variables(min_cost)Using I graph to calculate min and max (didnt work)
#Addmore attributes to the Graph
E(net)$Group <- E(net)$Type
#E(net)$Group
#V(net)$Group <- V(net)$CityType
#V(net)$Group
E(net)$weight = E(net)$Capacity
#E(net)$weight
E(net)$name = E(net)$ID
#E(net)$name
V(net)$weight = V(net)$Requirements
#V(net)$weight
E(net)$capacity <- E(net)$Max
E(net)$cost <- E(net)$Cost
plot(net, edge.label = E(net)$Max)
plot(net, edge.label = E(net)$Cost)
# Testing Maximum flow
g_max <- max_flow(net, c("New York, NY", 'Jacksonville, FL'),
c('Kosongo, D.R. Congo' ,"Ndjamena, Chad",
'Niamey, Niger'))
g_max$value## [1] 39000g_max## $value
## [1] 39000
##
## $flow
## [1] 21000 0 6000 12000 0 0 0 0 0 0 0
## [12] 0 0 0 0 0 0 0 21000 0 6000 12000
## [23] 0 0 0 0 0 0 0 0
##
## $cut
## [1] 2 5 6 8 11 12 19 21 22
##
## $partition1
## + 7/11 vertices, named, from 74ae952:
## [1] New York, NY Jacksonville, FL Khartoum, Sudan Lusaka, Zambia
## [5] Nairobi, Kenya Niamey, Niger Ndjamena, Chad
##
## $partition2
## + 4/11 vertices, named, from 74ae952:
## [1] Dakar, Senegal Libreville, Gabon Luanda, Angola
## [4] Kosongo, D.R. Congo
##
## $stats
## $stats$nopush
## [1] 3
##
## $stats$norelabel
## [1] 3
##
## $stats$nogap
## [1] 0
##
## $stats$nogapnodes
## [1] 0
##
## $stats$nobfs
## [1] 1gx <- net
E(gx)$label <- g_max$flow
plot(gx)
min_cut(net, c("New York, NY", 'Jacksonville, FL'),
c('Kosongo, D.R. Congo' ,"Ndjamena, Chad",
'Niamey, Niger'))## [1] 39000max_flow(net, c("New York, NY", 'Jacksonville, FL'),
c('Kosongo, D.R. Congo' ,"Ndjamena, Chad",
'Niamey, Niger'))$value## [1] 39000summary(net) #find more info## IGRAPH 74ae952 DNW- 11 30 --
## + attr: layout (g/n), name (v/c), Requirements (v/n), route (v/c),
## | color (v/c), weight (v/n), Type (e/c), Distance (e/n), Cost
## | (e/n), Capacity (e/n), Speed (e/n), Time (e/n), Max.Airplanes
## | (e/n), Max.Trucks (e/n), Max (e/n), ID (e/c), weight (e/n),
## | color (e/c), Group (e/c), name (e/c), capacity (e/n), cost (e/n)net[] #for matrix## 11 x 11 sparse Matrix of class "dgCMatrix"
##
## New York, NY . . 240 240 240 150 150 150 . . .
## Jacksonville, FL . . 240 240 240 150 150 150 . . .
## Dakar, Senegal . . . . . . . . 17.7 17.7 17.7
## Libreville, Gabon . . . . . . . . 17.7 17.7 17.7
## Luanda, Angola . . . . . . . . 17.7 17.7 17.7
## Khartoum, Sudan . . . . . . . . 150.0 150.0 150.0
## Lusaka, Zambia . . . . . . . . 150.0 150.0 150.0
## Nairobi, Kenya . . . . . . . . 150.0 150.0 150.0
## Niamey, Niger . . . . . . . . . . .
## Kosongo, D.R. Congo . . . . . . . . . . .
## Ndjamena, Chad . . . . . . . . . . .degree(net)## New York, NY Jacksonville, FL Dakar, Senegal
## 6 6 5
## Libreville, Gabon Luanda, Angola Khartoum, Sudan
## 5 5 5
## Lusaka, Zambia Nairobi, Kenya Niamey, Niger
## 5 5 6
## Kosongo, D.R. Congo Ndjamena, Chad
## 6 6E(net)[]## + 30/30 edges from 74ae952 (vertex names):
## [1] New York, NY ->Lusaka, Zambia
## [2] New York, NY ->Libreville, Gabon
## [3] New York, NY ->Nairobi, Kenya
## [4] New York, NY ->Khartoum, Sudan
## [5] New York, NY ->Luanda, Angola
## [6] New York, NY ->Dakar, Senegal
## [7] Jacksonville, FL ->Lusaka, Zambia
## [8] Jacksonville, FL ->Libreville, Gabon
## [9] Jacksonville, FL ->Nairobi, Kenya
## [10] Jacksonville, FL ->Khartoum, Sudan
## + ... omitted several edgesV(net)[]## + 11/11 vertices, named, from 74ae952:
## [1] New York, NY Jacksonville, FL Dakar, Senegal
## [4] Libreville, Gabon Luanda, Angola Khartoum, Sudan
## [7] Lusaka, Zambia Nairobi, Kenya Niamey, Niger
## [10] Kosongo, D.R. Congo Ndjamena, Chadtest<- net[]
test<- as.data.frame(as.matrix(test))
library(data.table)
library(reshape2)
test1<- data.table(test)
test1 <- transpose(test, fill =NA)
test1 <- melt(test1, fill = 0)
test1## variable value
## 1 V1 0.0
## 2 V1 0.0
## 3 V1 240.0
## 4 V1 240.0
## 5 V1 240.0
## 6 V1 150.0
## 7 V1 150.0
## 8 V1 150.0
## 9 V1 0.0
## 10 V1 0.0
## 11 V1 0.0
## 12 V2 0.0
## 13 V2 0.0
## 14 V2 240.0
## 15 V2 240.0
## 16 V2 240.0
## 17 V2 150.0
## 18 V2 150.0
## 19 V2 150.0
## 20 V2 0.0
## 21 V2 0.0
## 22 V2 0.0
## 23 V3 0.0
## 24 V3 0.0
## 25 V3 0.0
## 26 V3 0.0
## 27 V3 0.0
## 28 V3 0.0
## 29 V3 0.0
## 30 V3 0.0
## 31 V3 17.7
## 32 V3 17.7
## 33 V3 17.7
## 34 V4 0.0
## 35 V4 0.0
## 36 V4 0.0
## 37 V4 0.0
## 38 V4 0.0
## 39 V4 0.0
## 40 V4 0.0
## 41 V4 0.0
## 42 V4 17.7
## 43 V4 17.7
## 44 V4 17.7
## 45 V5 0.0
## 46 V5 0.0
## 47 V5 0.0
## 48 V5 0.0
## 49 V5 0.0
## 50 V5 0.0
## 51 V5 0.0
## 52 V5 0.0
## 53 V5 17.7
## 54 V5 17.7
## 55 V5 17.7
## 56 V6 0.0
## 57 V6 0.0
## 58 V6 0.0
## 59 V6 0.0
## 60 V6 0.0
## 61 V6 0.0
## 62 V6 0.0
## 63 V6 0.0
## 64 V6 150.0
## 65 V6 150.0
## 66 V6 150.0
## 67 V7 0.0
## 68 V7 0.0
## 69 V7 0.0
## 70 V7 0.0
## 71 V7 0.0
## 72 V7 0.0
## 73 V7 0.0
## 74 V7 0.0
## 75 V7 150.0
## 76 V7 150.0
## 77 V7 150.0
## 78 V8 0.0
## 79 V8 0.0
## 80 V8 0.0
## 81 V8 0.0
## 82 V8 0.0
## 83 V8 0.0
## 84 V8 0.0
## 85 V8 0.0
## 86 V8 150.0
## 87 V8 150.0
## 88 V8 150.0
## 89 V9 0.0
## 90 V9 0.0
## 91 V9 0.0
## 92 V9 0.0
## 93 V9 0.0
## 94 V9 0.0
## 95 V9 0.0
## 96 V9 0.0
## 97 V9 0.0
## 98 V9 0.0
## 99 V9 0.0
## 100 V10 0.0
## 101 V10 0.0
## 102 V10 0.0
## 103 V10 0.0
## 104 V10 0.0
## 105 V10 0.0
## 106 V10 0.0
## 107 V10 0.0
## 108 V10 0.0
## 109 V10 0.0
## 110 V10 0.0
## 111 V11 0.0
## 112 V11 0.0
## 113 V11 0.0
## 114 V11 0.0
## 115 V11 0.0
## 116 V11 0.0
## 117 V11 0.0
## 118 V11 0.0
## 119 V11 0.0
## 120 V11 0.0
## 121 V11 0.0