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.

Well known 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 or free solvers in this page. Commercial solvers remain maybe 6-7 time faster than the main free/open-source solvers.

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

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)
  • Python-MIP interface for CBC (free) and Gurobi (commercial)
  • PySCIPOpt interface for SCIP (free)

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.10 installed otherwise install it http://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 Python-MIP with pip install mip this should install also the solver CBC. If you want to work with gurobi follow these local guidelines for the installation.

    • Alternatively, install SCIP following these instructions (you need to be on Linux, MacOs or WSL). Choose the installation via Precompiled Packages. Then, install PySCIPOpt with pip install pyscipopt preceeded by these instructions under the section Requirements. Consult the documentation.

We assume that you have previous knowledge of Python programming (a couple of links to review Python programming are available from the course Web Page).

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: