Linear Optimization

Introduction to Linear optimization programming problems

Settlers of Catan, board game where Objective is to maximize points, with constrained resources.

It’s one of those “cloudy Monday mornings” and you are late for the office.
While starting your bike, you start thinking.
How can I make it to office in time? Which is the shortest route? Would it be crowded? Or, should I take the longest path but with lesser traffic? Traffic should not add to delay. Also, I am running low on fuel, I need to visit the petrol pump on my way. Would I be able to make it in time? And then, you take certain decisions, and start on your journey to the office.

This decision making process is nothing but optimization. We choose something over other, we make trade-offs with some goal in mind. We optimize cause the resources are scarce and there are multiple activities which are supposed to consume these resources. The objective is to fulfil your goal, with least cost incurred and without violating any rule.

Optimization is a method to maximize or minimize a some function, which is restricted by some constraints. And the goal is to find values of the variables that maximizes or minimizes the function.

Linear optimization is subset of optimization problems, where the constraints and objective function are linear in nature.
What do we mean by that?

Maximize, c^T.x
Subject to, Ax <= b
and x >= 0

Where x is vector of unknown variables, c and b are known vectors, T is transpose of vector c, And A is known matrix.

Or the same thing can be easily written as Standard form.

maximize, f(x1, x2) = c1x1 + c2x2
Subject to, 
 a11x1 + a12x2 <= b1
 a21x1 + a22x2 <= b2
 a31x1 + a32x2 <= b3
Where
 x1 >= 0
 x2 >= 0

Use of linear optimization is across multiple domains like finance, production, Distribution, Agriculture, Military and so on and so forth.

To solve the linear optimization problems manually, we can use graphical technique or simplex method. But most of the times, the number of variables and constraints are so large that it gets difficult to solve the model by hand. In such scenarios, we can use packages like python-pulp or Julia-JuMP to model the problem and to solve these models, there are number of solvers available -Cplex, Cbc, Gurobi to name a few.

Please refer “Linear optimization using Julia” for solving our first Linear optimization problem with Julia, JuMP and Cbc solver.

Thanks for reading. Your feedback is highly appreciated.