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

Charles (Chris) Ochoa

currently a work in progress

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.

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

simple network flow done with pulp and networkx

Classic traveling salesman solved as an integer program

Simple generalization of the traveling salesman

Classic 0-1 Knapsack problem solved as an integer program

Minimize the number of bins needed to pack items

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

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

for editing notes see setup-notes.txt

install PuLP

$ pip install pulp

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 :(