Python Integer Programming

An introduction to (mostly) linear programming and combinatorial optimization problems in python.

Charles (Chris) Ochoa

currently a work in progress

Who is this book for?

This book is for someone who already knows python, is not afraid of basic math (mostly math as a written language), and has the need to solve combinatorial problems. The book will cover linear programs both continuous and integer and some theory on the algorithms that solve these. It will also cover the PuLP open source linear modeling library, some convex optimization, and lots of case studies and examples along with discussions about improving performance. Also maybe some combinatorial game theory if I ever get the time and quadratic programming.

Sections

a. Linear Programming Intro

The basics of modeling and solving linear programs with python PuLP.

b. Network Flows

simple network flow done with pulp and networkx

c. Traveling Salesman Problem

Classic traveling salesman solved as an integer program

d. Multiple Salesman and Vehicle Routing

Simple generalization of the traveling salesman

e. Knapsack Problem

Classic 0-1 Knapsack problem solved as an integer program

f. Bin Packing

Minimize the number of bins needed to pack items

g. Logical Operations

Model complex non-linear constraints and objectives via clever uses of binary variables.

Setup

''' conda env create -f environment.yml '''

for editing notes see setup-notes.txt

install PuLP

$ pip install pulp

optional for now,

install network x

$ pip install networkx

install the GNU Linear Programming Kit GLPK:

linux:

$ sudo apt-get install python-glpk sudo apt-get install glpk-utils

osx (via homebrew):

$ brew install glpk

windows: sorry :(