Linear Programming (LP) and Mixed Integer Programming (MIP)
Linear Programming
Linear programming is an approach to optimize a linear objective function (e.g. cost = #units * price + #hours * wage), subject to a set of linear constraints, such as #hours <= 8 per day, price > 0, #hour1 + #hour2 + ... #hourk < 200. The goal is to find the best possible outcome, maximizing / minimizing the objective function, while satisfying all the constraints.
An example
Scenario: A farmer has 100 acres of land. He can plant either corn or wheat. Each acre of corn requires 3 hours of labor and yields a profit of $500. Each acre of wheat requires 2 hours of labor and yields a profit of $400. The farmer has a total of 240 hours of labor available.
Variables: x is acres of corn
y is acres of wheat
Objective: Maximize profit from planting corn and wheat.
500x + 400y
Constraints:
Land size constraint: x+y≤100 (where x is acres of corn and y is acres of wheat)
Labor hour constraint: 3x+2y≤240
Variable bounds: x≥0, y≥0, x<=100, y<=100
Python script solution
firstly install the Google OR-Tools library pip install ortools
from ortools.linear_solver import pywraplp
# Create the solver
solver = pywraplp.Solver.CreateSolver('GLOP')
# Create variables
# The lower bound lb and upper bound up of variables are set
x = solver.NumVar(lb=0, ub=100, name='corn') # acres of corn
y = solver.NumVar(lb=0, ub=100, name='wheat') # acres of wheat
# Land constraint
solver.Add(x + y <= 100)
# Labor constraint
solver.Add(3 * x + 2 * y <= 240)
# Objective function: Maximize profit
solver.Maximize(500 * x + 400 * y)
# Solve the problem
status = solver.Solve()
#The solution value for each variable
#or simply use variable.solution_value() for each variable
results = {var.name(): var.solution_value() for var in solver.variables()}
if status == pywraplp.Solver.OPTIMAL:
print(f'Optimal solution found:')
print(f'Acres of corn to plant: {x.solution_value()}')
print(f'Acres of wheat to plant: {y.solution_value()}')
print(f'Maximum profit: ${solver.Objective().Value()}')
else:
print('The problem does not have an optimal solution.')
If there are too many variables, and don't want to code it one by one, just use loop, e.g.
variables = []
#declare variables
for i in range(100):
variables.append(solver.NumVar(lb=0, ub=100, name=f'var{i}'))
#add constraints,
for i in range(99):
solver.Add(variables[i] + variables[i+1] < 100)
#add objective function
#Note if a list of variables is provided, use the solver.Sum to avoid listing a hundred variables.
solver.Maximize(solver.Sum([var - 0.5 for var in variables]))
#and maybe exceptions
for i in range(99):
if i > 60:
solver.Add(variables[i] > 1)
Mixed Integer Programming (MIP)
Similar to Linear Programming except extra constraints on variables being an integer, because some variables must be integer to make sense, e.g. can't allocate half an person to a different production site at the same time.
Continuing with the corn and wheat example from linear programming, if the number of acres must be an integer, the problem becomes a Mixed Integer Programming (MIP) problem. In MIP, at least some of the decision variables (in this case, the acres of corn and wheat) are required to take on integer values.
The python code is almost the same. Only the variables are declared as IntVar instead of NumVar.
from ortools.linear_solver import pywraplp
# Create the solver
# GLOP / CLP for LP, CBC for MIP, SCIP for MIP / Constraint programming,
# Xpress for LP, MIP, QP
# CP-SAT for constraint programming
solver = pywraplp.Solver.CreateSolver('SCIP')
# Create Integer variables
x = solver.IntVar(lb=0, ub=100, name='corn') # acres of corn
y = solver.IntVar(lb=0, ub=100, name='wheat') # acres of wheat
# Land constraint
solver.Add(x + y <= 100)
# Labor constraint
solver.Add(3 * x + 2 * y <= 240)
# Objective function: Maximize profit
solver.Maximize(500 * x + 400 * y)
# Solve the problem
status = solver.Solve()
#The solution value for each variable
#or simply use variable.solution_value() for each variable
results = {var.name(): var.solution_value() for var in solver.variables()}
if status == pywraplp.Solver.OPTIMAL:
print(f'Optimal solution found:')
print(f'Acres of corn to plant: {x.solution_value()}')
print(f'Acres of wheat to plant: {y.solution_value()}')
print(f'Maximum profit: ${solver.Objective().Value()}')
else:
print('The problem does not have an optimal solution.')
Tricks for handling non-linear problems
Converting a non-linear problem to a linear one can make it easier to solve, especially using linear programming techniques.
Here are some common tricks and methods to achieve this:
Sometimes, you can reformulate the problem to avoid non-linear terms:
Substitution: If x^2 appears, introduce a new variable z = x^2, turning it into a linear relationship involving z.
Constraints: Use constraints to limit the behavior of the non-linear terms, effectively bounding them.
Linearization of Non-Linear Functions:
Taylor Series Expansion: For functions that are differentiable, you can use a first-order Taylor series expansion around a point to approximate the non-linear function linearly.
Piecewise Linear Approximations: Approximate non-linear functions with linear segments over specific intervals. This is useful for functions that can be segmented into simpler linear parts.
Use of Binary Variables:
For problems involving logical conditions (like if-then statements), introduce binary variables. For example, if you have a non-linear piecewise function, you can define linear constraints for each segment based on the binary variable.
Logarithmic Transformation:
If the non-linear relationship is multiplicative (e.g., xy=z), taking the logarithm can transform it into an additive form (e.g., log(x)+log(y)=log(z), which can sometimes simplify the problem.
Convex Hull Representation:
For non-linear sets, consider using the convex hull representation, which can often allow for linear approximations of non-linear constraints.
Utilizing Linear Relaxations:
In mixed-integer programming (MIP), relax non-linear constraints to linear forms wherever possible. This is especially useful when the non-linearities are limited to certain regions of the solution space.
Graphical Methods:
For simple problems, graphical methods can help visualize non-linear relationships and find linear approximations.
NOTE
QP – Quadratic programming
if objective function is quadratic, e.g. minimize(the square of x + y)
The constraints must still be linear though.