Solving MILP Problems in Python

Introduction

This hands on tutorial aims at introducing students to mathematical modeling languages. These languages make it possible to write in an easy and compact way problems in Linear Programming (LP), Integer Programming (IP) and Mixed Integer Linear Programming (MILP) and to instantiate them in MILP solvers.

Examples of mathematical programming languages are: AMPL, GAMS, ZIMPL and GNU MathProg. The last two are open source.

These languages are declarative type of languages, as opposed to procedural type. That is, they can be used to define the problem without saying how it should be solved. Moreover, they allow to separate the model from the data. In fact, that is essentially all what they do, they instantiate the model on the given data. The output that is used by the solver can also be used for debugging purposes, that is, to check that the explicit model is as expected. There are two formats in which an instantiated MILP can be exported to a file: .mps format, which is an almost universal format among solver systems, but that is not easy to read, and .lp format, which is more readable (introduced by CPLEX).

You find a list of commercial and open source solvers in this page.

The NEOS server (www.neos-server.org) provides an infrastructure to upload an instantiated model and solve it remotely.

In this course, we use Python. In Python we will import a module, that makes available a library to pass models to the solver. It is not a mathematical programming language but the library is very light and similar to a modelling language.

You can work on your own laptop, in which case it is enough to install the software there. Alternatively, you can use the IMADA Virtual Computer Lab. In this latter case you will have to install the software in your IMADA home directory.

We will consider the following alternatives:

  • gurobipy Gurobi Python interface to their solver (commercial)

  • highspy Highs Python interface (open source)

Although commercial, we will prefer using Gurobi because of its good documentation. Passing to HiGHS once learned should be relatively easy.

Preparation

You can use Google CoLabs and execute the code online. However, it is recommended to set up a local working environment with the following steps:

  • If your operating system is Windows then install the Windows Subsystem for Linux (WSL) and work from the shell.

  • Ensure you have at least Python 3.14 installed otherwise install it https://python.org/download/.

  • Choose and prepare your favourite Python Integrated Development Environment (IDE): For example:

  • Choose one of the following:

    • Install gurobipy (easiest alternative). Follow these guidelines. The recommended installation is via pip. This should install also gurobi. To make it work you need also a license from the gurobi web page. You could use the tools from here and register at the gurobi page to get the license. See also this local page of guidelines for a full installation and documentation of gurobi.

    • Alternatively, install HiGHSpy with pip install highspy.

In the remaining part of this document you will be guided through some elements of the course revisited with the use of software. Although the exercises are about implementing the models at the computer, remember that the best practice is to first write the mathematical models on paper! Do that for the subtasks that asks you to derive a mathematical model.

Hands on

Continue this tutorial with the hands on parts:

This site uses Just the Docs, a documentation theme for Jekyll.