Part 1: Overview and Mathematical Formulation¶
A civil engineering company wants to decide on the projects that they should do. Their objective is to minimize the environmental impact of their projects while making enough profit to keep the company running.
They have a portfolio of 6 possible projects to invest in, where A, B , and C are new infrastructure projects (so-called type 1), and D, E, F are refurbishment projects (so-called type 2).
The environmental impact of each project is given by $I_i$ where $i \in [1,(...),6]$ is the index of the project. $I_i=[90,45,78,123,48,60]$
The profit of each project is given by $P_i$ where $i\in [1,(...),6]$ is the index of the project: $P_i=[120,65,99,110,33,99]$
The company is operating with the following constraints, please formulate the mathematical program that allows solving the problem:
- The company wants to do 3 out of the 6 projects
- the projects of type 2 must be at least as many as the ones of type 1
- the profit of all projects together must be greater or equal than $250$ ($\beta$)
Task 1: Writing the mathematical formulation
Write down every formulation and constraint that is relevant to solve this optimization problem.
Solution
$$Min(Z) \sum_{i=1}^{6} x_i I_i $$
subject to
$$ \sum_{i=1}^{6} x_i = 3 $$ $$ \sum_{i=4}^{6} x_i \ge \sum_{i=1}^{3} x_i $$ $$ \sum_{i=1}^{6} x_i P_i \ge β $$ $$x\in(1,0), i\in(1,....,6)$$
Extra Challenge (Task 6) $$ \sum_{i=1}^{6} x_i I_i \le x_1 γ + (1-x_1) M $$
where M is a sufficiently big number such as 9999
Task 2: Setting up the software
We'll continue using Gurobi this week, which you've set up in last week's PA. We'll use some other special packages as well. Therefore, be sure to use the special conda environment created for this week.
import gurobipy as gp
Task 3: Setting up the problem
Define any variables you might need to setup your model.
# YOUR_CODE_HERE
# SOLUTION
# Project data
I = [90, 45, 78, 123, 48, 60] # Environmental impact
P = [120, 65, 99, 110, 33, 99] # Profit
# Minimum required profit
beta = 250
M = 100000
# Number of projects and types
num_projects = len(I)
num_type1_projects = 3
num_type2_projects = num_projects - num_type1_projects
Part 2: Create model with Gurobi¶
Remember that examples of using Gurobi to create and optimize a model are provided in the online textbook, and generally consist of the following steps (the first instantiates a class and the rest are executed as methods of the class):
- Define the model (instantiate the class)
- Define variables
- Define objective function
- Add constraints
- Optimize the model
Remember, you can always ask for help to understand a function of gurobi
help(gurobipy.model.addVars)
Task 4: Create the Gurobi model
Create the Gurobi model, set your decision variables, your function and your constrains. Take a look at the book for an example implementation in Python if you don't know where to start.
Solution.
Each line of code does the following:
- Create a Gurobi model
- Add binary variables
- Objective function: Minimize environmental impact
- Constraint: Select exactly 3 projects
- Constraint: Number of type 2 projects must be at least as many as type 1 projects selected
- Constraint: Minimum profit requirement
- Optimize the model
# YOUR_CODE_HERE
# SOLUTION
model = gp.Model("Project_Selection")
x = model.addVars(num_projects, vtype=gp.GRB.BINARY, name="x")
model.setObjective(sum(I[i] * x[i] for i in range(num_projects)),
gp.GRB.MINIMIZE)
model.addConstr(x.sum() == 3, "Select_Projects")
model.addConstr((sum(x[i] for i in range(num_type2_projects, num_projects))
- sum(x[i] for i in range(num_type1_projects)) >= 0),
"Type_Constraint")
model.addConstr(sum(P[i] * x[i] for i in range(num_projects)) >= beta,
"Minimum_Profit")
model.optimize()
Task 5: Display your results
Display the model in a good way to interpret and print the solution of the optimization.
# YOUR_CODE_HERE
# SOLUTION
print("Model structure:")
# see the model that you have built in a nice why to interpret
model.display()
if model.status == gp.GRB.OPTIMAL:
print("Optimal Solution:")
for i in range(num_projects):
if x[i].x > 0.9:
print(f"Project {i+1}: Selected")
else:
print("No optimal solution found.")
print("Optimal Objective function Value", model.objVal)
Task 6: Additional constraint
Solve the model with an additional constraint: if project 1 is done then the impact of all projects together should be lower than $\gamma$ with $\gamma=130$.
Paste your model previous model, and call it model2 to keep the results separated and add the new constraint. Then run your second model.
# YOUR_CODE_HERE
# SOLUTION
model2 = gp.Model("Project_Selection")
x = model2.addVars(num_projects, vtype=gp.GRB.BINARY, name="x")
model2.setObjective(sum(I[i] * x[i] for i in range(num_projects)),
gp.GRB.MINIMIZE)
model2.addConstr(x.sum() == 3, "Select_Projects")
model2.addConstr((sum(x[i] for i in range(num_type2_projects, num_projects))
- sum(x[i] for i in range(num_type1_projects)) >= 0),
"Type_Constraint")
model2.addConstr(sum(P[i] * x[i] for i in range(num_projects)) >= beta,
"Minimum_Profit")
# added constraint
gamma = 130
model2.addConstr((sum(I[i] * x[i] for i in range(num_projects))
<= gamma * x[0]+ M * (1 - x[0])),
"Impact_Constraint")
# YOUR_CODE_HERE
# SOLUTION
model2.optimize()
print("Model structure:")
# see the model that you have built in a nice why to interpret
model2.display()
# Display the solution
if model2.status == gp.GRB.OPTIMAL:
print("Optimal Solution:")
for i in range(num_projects):
if x[i].x > 0.9:
print(f"Project {i+1}: Selected")
else:
print("No optimal solution found.")
print("Optimal Objective function Value", model2.objVal)
End of notebook.