Linear Programming in Python

Linear Programming in Python#

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.

Task 2: Setting up the software

We will use Pyomo (modeling language) together with the open-source solver HiGHS. No licenses are required.

What you need:

  • Python environment (same as previous weeks)
  • Install the packages: pyomo and highspy

Installation (if needed):

pip install pyomo highspy

from pyomo.environ import (
    ConcreteModel, Set, Var, Param, Objective, Constraint,
    Binary, NonNegativeReals, Integers, minimize, maximize,
    SolverFactory, value
)

Task 3: Setting up the problem

Define any inputs you might need to setup your model.

# Project data
### YOUR CODE HERE ###

# Minimum required profit
### YOUR CODE HERE ###

# Number of projects and types
### YOUR CODE HERE ###

Part 2: Create model with Pyomo + HiGHS#

We will follow these steps (Pyomo separates modeling from solving):

  1. Define the model container (ConcreteModel)

  2. Define sets and parameters (Param or Python Dictionary)

  3. Define decision variables (Var)

  4. Define the objective (Objective)

  5. Add constraints (Constraint)

  6. Call the solver (SolverFactory("highs").solve(m, tee=False))

If you need help on a Pyomo component, use Python’s help:

import pyomo.environ as pyo
help(pyo.Var)

Task 4: Create the Pyomo model

Create the Pyomo model, declare the decision variables, objective function, and constraints as specified in the formulation. Use the code skeleton provided to guide you. You can also refer to the Pyomo documentation for additional details of implementation.

### YOUR CODE HERE ###

Task 5: Display your results

Display the model in a good way to interpret and print the solution of the optimization.

### YOUR CODE HERE ###

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\).

In the first cell you should add the constraint, then in a second cell optimize the model.

### YOUR CODE HERE ###

### YOUR CODE HERE ###

By Nadia Pourmohammadzia, Delft University of Technology. CC BY 4.0, more info on the Credits page of Workbook.

Contents