Answered step by step
Verified Expert Solution
Question
1 Approved Answer
The year is 1 4 2 3 and the storm is gathering around Lombaria! The ambitious Filippo Maria Visconti, Duke of Milan, have attacked you
The year is and the storm is gathering around Lombaria! The ambitious Filippo Maria Visconti, Duke of Milan, have attacked you the fellow Venetians! You and your mercenary friends Tuna, Kaan, Ali, Kutup, O zgu n and Muhittin are stuck in Lombardy, Italy. You need to somehow save the people of Lombardy from the cruel Duke. You are currently located in Pavia, and you can rescue people to come with you along your journey in Lombardy. Due to the logistic reasons, each of you have the a capacity to rescue people during your route. Since the Duke is fast and furious, you only have time to visit cities in total.
But you are lucky, all of you are Medieval IEOR specialists! So your job is to gather as many people as possible in order to collaborate and survive against the Milanese. In other words, you need to come up with a route that maximizes the number of people rescued along your route.
Rules
From a city, you can only go to a neighboring city. You need to start from Pavia.
The route is finished once you visit the th city.
The region of Lombardy has cities in total that can be seen in Figure
We also have some additional conditions. Ali knows someone named Sena in Milan, who must be rescued since she is the only medical scientist left in Lombardy. Moreover, Kutup knows a new companion of his, Bora, with a capacity to rescue more people, who is living right next to the Lake Como. O zgu n knows a person in Bergamo, Yi git who is among the population of Bergamo. O zgu n informs you that if Yi git is to come across with his friends in Cremona, Yi git is going to persuade them to leave your party and they will rush to the aid of the Venetians in the battlefield against the Milanese, so they will NOT be rescued in the end.
Solve this problem using Mixed Integer Linear Programming and report your solution The region of Lombardy has cities in total that can be seen in Figure
Figure : Map of the region of Lombardy, Italy
Each city has a number of people residing in it as follows:after implementing it in gurobipy. Clearly indicate the visited cities in your reports.
For this question, I have the following code:
import gurobipy as gp
from gurobipy import GRB
# Cities & Populations
cities Pavia"Lodi", "Milan", "Varese", "Como", "MonzaBrianza "Sondrio",
"Lecco","Cremona", "Mantua", "Brescia", "Bergamo"
p
K
# Initialize model
m gpModelItaly
# Decision variables
#X arc between cities i and j
#Y Visited city
#C Capacity of every person
#B Binary value that demonstrates whether bora is saved or not
x maddVarslencities lencities vtypeGRBBINARY, namexij
y maddVarslencities vtypeGRBBINARY, nameyi
c maddVarsrange vtypeGRBINTEGER, nameci
b maddVarvtypeGRBBINARY, name"bora"
ns maddVarvtypeGRBBINARY, name"Not Saved"
mupdate
# Objective Function
msetObjectivegpquicksumci for i in rangeb nsp GRBMAXIMIZE
# Each city is visited at most once
for j in rangelencities:
maddConstrgpquicksumKij xi j for i in rangelencities
# Constraints
#Starting from Pavia
maddConstry
# Max. cities can be visited
maddConstrgpquicksumxi j for i in rangelencities for j in rangelencities
for i in range lencities:
for j in range lencities:
maddConstrKij xij
#Model ends at most th visit th city
maddConstrgpquicksumyi for i in rangelencities
# Each arc can be used once
for i in range lencities:
for j in range lencities:
maddConstrxijxji
# Capacity for each person
for j in range:
maddConstrcj
# Sena, Bora & Yigit's special cases
maddConstry
#maddConstry y
if maddConstry:
ns
if maddConstry:
b
# To ensure that capacity does not exceeds population
maddConstrgpquicksumyi pi for i in rangelencities gpquicksumck for k in range
# To connect variables X & Y
for i in range lencities:
for j in range lencities:
if ij:
maddConstryi yi xij
However, when the code is runned, the outcome is Pavia, Milan, Como, Bergamo. Since milan and como are not neighbor, it is impossible. Enhance the code according to that "neighbour" problem please.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started