Introduction

When life was easy

At some point in my calculus education I developed a simple rule, when in doubt set the derivative equal to zero and solve for x. You might recall doing this, and the reason for doing it is because for a smooth function its local maximum and minimum are found at places where the derivate is zero. Imagine if you have curve shaped like a hill, now if you go up the hill and at some point go over the top (the max), if you keep going you will start traveling downward. If you went from increasing to decreasing, the calculus argument was that at some point your rate of increase was zero and that would be at the top. Largely this works very well. It leads nicely to many optimization rules, but it breaks down a little bit when we don't have a curve. In particular it breaks down when our domain is the set of integers.

Enter the real world, everything is a model

Often times the problems are stated as find the "best" route, or find the "best" fitting function. For us to solve these problems, we need to model what "best" means. We need to mathematically describe a quantity to either maximize or minimize. For example we might seek select the route that minimizes the total distance traveled by a salesman (traveling salesman). Or if we were trying to fit a curve to some data, we might minimize the error between the predicted curve and the data (regression). We might try to select paths in a distribution network that maximize flow (network flow problems) etc.

When we talk about programs, we mean a set of variables, a function of those variables to maximize or minimize, and some constraints that those variables must satisfy.

formally:

$$minimize\: f(x)\\subject\, to\: g(x) < 0 $$

We will see that the form of this optimization metric $f(x)$ plays a huge role in the difficulty. The first best case is when $f(x)$ and the constraints $g(x)$ are linear.

Linear Programs

A linear program is one where the metric or objective to minimize is linear and the constraints are linear, i.e.:

$$f(x) = a_{0}x_{0} + a_{1}x_{1}+ \dots + a_{n}x_{n}$$

continuous vs integer (and mixed integer!)

If all the variables are continuous life is good. If however the variables must take on integer solutions, for example, 1,2,3... then life can be very hectic. Problems with integer only solutions are integer programming problems and they can be very difficult to solve if a solution exists at all! When you have a mix of variable types, you have a mixed integer problem. While many algorithms exist to solve all of these types, the most common for continuous programs is the simplex algorithm and for mixed integer the insanely clever branch cut and bound method works very well. We will talk about these later.

How do you know if the program is linear? just make sure the expression and the constraints are a combination of constants multiplied by some variables. If any of variables are multiplied or divided by another, you are in trouble and you have a harder problem. It is also important that the variables be continuous. If for example Most interesting problems are not linear, however there are a number approximations and tricks that can turn non linear programs into linear ones. We will explore this later. For now, lets solve our first program using PuLP.


In [3]:
#load all the things! 
from pulp import *

lets try a small problem we can easily solve by hand

$$minimize\: f(x,y,z)=5x+10y+6z \\ subject\, to\\ x+y+z \geq 20 \\ 0\leq x,y,z \leq 10 $$

In school we may have learned how to solve these types or problems by writing them in canonical form and throwing some linear algebra at them. PuLP is a library that removes this need, we can code our problem almost exactly as stated above in PuLP and it will do the hard work for us. What PuLP actually does is format the problem into a standard language that is used by many numerical solvers.

1. Setup the problem


In [4]:
prob = LpProblem("Hello-Mathematical-Programming-World!",LpMinimize)

2. Setup the variables:

for now we will make them manually, but there are convenience methods for when you need to make millions at a time


In [5]:
x = LpVariable('x',lowBound=0, upBound=10, cat='Continuous')
y = LpVariable('y',lowBound=0, upBound=10, cat='Continuous')
z = LpVariable('z',lowBound=0, upBound=10, cat='Continuous')

3. Setup the objective


In [6]:
objective = 5*x+10*y+6*z

what does this create?


In [7]:
print(type(objective))


<class 'pulp.pulp.LpAffineExpression'>

It is an LpAffineExpression. You can actually print LpAffineExpressions to see what you have programmed. Be careful with this on larger problems


In [8]:
print(objective)


5*x + 10*y + 6*z

4. Setup the constraints


In [9]:
constraint = x + y + z >= 20

5. stuff the objective and the constraint into the problem

To add constraints and objectives to the problem, we literally just add them to it


In [10]:
#add the objective
prob+= objective

#add the constraints
prob+=constraint

like the LpAffineExpression class, we can print the problem to see what PuLP has generated. This is very useful for small problems, but can print thousands of lines for large problems. Its always a good idea to start small.


In [11]:
print(prob)


Hello-Mathematical-Programming-World!:
MINIMIZE
5*x + 10*y + 6*z + 0
SUBJECT TO
_C1: x + y + z >= 20

VARIABLES
x <= 10 Continuous
y <= 10 Continuous
z <= 10 Continuous

6. Solve it!

Pulp comes packaged with an okay-ish solver. The really fast solvers like cplex and gurobi are either not free or not free for non academic use. I personally like GLPK which is the GNU linear programming solver, except it is for *nix platforms.


In [12]:
%time prob.solve()
print(LpStatus[prob.status])


CPU times: user 3.16 ms, sys: 9.15 ms, total: 12.3 ms
Wall time: 106 ms
Optimal

7. Get the results


In [13]:
#get a single variables value
print(x.varValue)


10.0

In [14]:
#or get all the variables
for v in prob.variables():
    print(v, v.varValue)


x 10.0
y 0.0
z 10.0

In this example, the optimal objective is {{x.varValue}}

and the variables that give us that answer are: {{[q.varValue for q in prob.variables()]}}


In [ ]: