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
f. Bin Packing
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 :(