#linear optimization

LP is the first category of optimization problems that were considered by early scientists and researchers in the OR field.

It turns out that many models can be cast in the form of LP models, without too many wild assumptions.

To solve an optimization problem, a model file contains at least the elements, i.e Objective Function, Constraints and Bounds.

1) Objective Functions

Objective function is a mathematical representation of the business objectives or goals to be achieved. It always starts with maximize or minimize of the outputs, for minimizing costs or maximizing revenue.

$\min c_1 x_1 + c_2 x_2 +\ ...\ +\ c_n x_n$

min means minimize. It can be maximize based on modeler's logic.

$c_1, c_2, ..., c_n$ are the objective function coefficients.

$x_1, x_2, ..., x_n$ are the variables or unknowns.

2) Constraints

Constraints are the elements that limit or restrict the decision variables in some way.

$\begin{aligned} a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n \leq b_1 \\\ a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n \leq b_2 \\\ ... \\\ a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n \leq b_m \\\ x1, x2, ..., x_n \geq 0 \end{aligned}$

$a_{11}, a_{12}, ..., a_{1n}, a_{m1}, a_{m2}, ..., a_{mn}$ are the constraint coefficients.

$\leq, \geq, \lt, \gt$ are the relations between both sides in inequalities form.

$b_1, b_2, ..., b_m$ are the righthand side values.

3) Bounds

Bounds are the special contraints to define lower and upper boundaries.

$l_1 \leq x_1 \leq u1,\ ...,\ l_n \leq x_n \leq u_n$

$u_1, u_2, ..., u_n$ are the upper bounds.

$l_1, l_2, ..., l_n$ are the lower bounds.

This is the Simplest Structure of a Model with the conventional form or typical symbolic representation of a LP.

Minimize (or Maximize) c1 x1 + c2 x2 + ... + cn xn Subject To a11 x1 + a12 x2 + ... + a1n xn = 0 l1 = 0

model starts with the objective, i.e. to minimize a linear function.

c is the vector of objective coefficients.

s.t. means subject to constraints in the form of linear expressions.

b is the vector of right-hand side constants of constraints.

A is the matrix of constraint coefficient.

x is the decision variable.

$x \geq 0$ is the variable domain.

This example shows how to a general linear programming problem, and illustrates how scripting can be combined with the model to display results and obtain details on the solution. The problem we want to solve can be written in matrix form as

$\begin{aligned} \max c^T x \\\ s.t.\ A_x \leq b \\\ x \geq 0 \\\ \end{aligned}$

Simplest form of a LP

min c^T x s. t. Ax = b x >= 0

$c^T$ is the c transpose x.

if y represents the dual variables for a given basic solution, the reduced costs are defined as $c - y^T A$.

the basic solution is optimal if $c - y^T A \geq 0$.

if all reduced costs for this LP are non-negative, it follows that the objective value can only increase with a change in variable value and therefore the solution when minimizing is optimal.

for large LPs, the reduced costs can be used to determine whether multiple optimal solutions exist.

Multiple solutions exist when at least one non-basic variable with a zero reduced cost exists in an optimal solution, that is, the variables values that can change without affecting the objective values.

It is possible that a LP has multiple optimal solutions. This can happen when the slope of the objective function is the same as the slope of the constraints.

We have stressed the linearity condition, where the objective function and all of the constraints must be linear in the decision variables. But there are two further properties that we must have, which are Divisibility and Determinism.

Divisibility means that in an acceptable solution any values of the decision variables are allowed within the restrictions imposed by the linear constraints. In particular, we are not constrained to accept only whole number (integer) values for some or all of the decision variables.

Deterministic requires all the coefficients in the constraints and the objective function are known exactly. Determinism is sometimes a very strong assumption, particularly if we are building planning models which extend some way into the future.

Problems where we must consider the Variability in objective function coefficients, right hand sides or coefficients in the constraints are Stochastic Programming problems. In fact, it can be argued that all planning models have stochastic elements and we will later demonstrate some methods for dealing with uncertainty in an LP framework.

Nowadays Linear Programming is still frequently taught from a very academic perspective. With the exception of a few students in applied mathematics who have learned to deal with applications, the others do not retain much.

So what is a linear function? Well let's start with the one-variable case. As we probably all remember via flashbacks to high school algebra, a line has equation $y = mx +b$. (We say $m$ is the slope and $b$ is the y-intercept). I prefer a variant equation $y = m(x-x_0) + y_0$, which conveys more information directly: the line has slope $m$, and goes through the point $(x_0, y_0)$.

Why is this nice? Well, primarily, it's easy to compute with. We don't have to do anything weird. We can solve it without taking any square roots or doing anything nasty. Assuming the slope isn't zero, it will hit every possible value exactly once, and we can easily tell where that happens.

(We also like lines because they're fundamental to most conceptions of geometry, but that's not going to be super relevant. It will be a little, though).

How do lines come up in calculus? Well, if you've taken calculus you might remember that people define the derivative as the "slope of the tangent line" to a function. There are a number of ways one could define the "tangent line," but relevant to our purposes, the tangent line is the linear function that best approximates your original function.

Basically, we like linear functions because they're easy to work with. When we look for the tangent line to a function $f$ at a point $a$, we're saying "okay, let's pretend $f$ is a line. What's the closest we can get to it being the same as the real $f$?"

And the answer is different depending on where you are on the graph. Below we have a graph with two tangent lines at two different points. We can see that each one looks a lot like the graph in a certain neighborhood, but they're very different from each other.

This means that we need a different derivative for every point on the graph. And the function $f'(x)$ is a function that tells you "If I look at the point $x$, then what is the line that looks the most like the graph of $f$ near that point?" And near a starting point $a$, we get the approximation $$f(x)\approx f'(a) (x-a) + f(a).$$

So with one variable, the derivative $f'(x)$ is a function that takes in a point, and outputs a line. What happens if we have more than one variable?

Well, first we can ask what the analog of a line is. If you ask most people what the two-dimensional version of a line is, after some hemming and hawing they'll probably come up with "a plane." And that's basically right.

And in fact we can see that the equation that gives a plane as its graph is something like $f(x,y) = ax + by +c$, which looks like our line equation except with an extra variable. And we can generalize this. A linear function on three variables is $f(x,y,z) = ax + by + cz + d$, and in general if we have a linear function on $n$ variables it looks like $$f(x_1, \dots, x_n) = a_1 x_1 + a_2 x_2 + \dots + a_n x_n +c= \sum_{i=1}^n a_i x_i +c.$$

Note: we can make things more compact with good notation. I'll use the convention that $\mathbf{x} = (x_1, \dots, x_n)$. You also may or may not remember that we can take the "dot product" of two vectors by $$\mathbf{x} \cdot \mathbf{y} = x_1 y_1 + x_2 y_2 + \dots + x_n y_n = \sum_{i=1}^n x_i y_i.$$ Thus a linear function is one where we have some vector $\mathbf{a} = (a_1, \dots, a_n)$ such that $f(\mathbf{x}) = \mathbf{a} \cdot \mathbf{x} + c.$

This basically just means that a linear function is one where you multiply each variable by some fixed number and then add them all together. You never multiply two variables together and you never do anything weird to them. So things are still really easy to calculate with.

So how does this relate to calculus and the idea of approximation? If you've taken a multivariable calculus course, you've probably spent some time dealing with "partial derivatives" and "directional derivatives" and such. These are all useful computational tools but are a bit beside the point for understanding what's actually going on.

Let's return to the two-variable case, because we can actually draw pictures of graphs and see what's going on. We have a function and we want the equation for a plane that looks the most like our function--the "tangent plane," which you can see below.

If you remember the details of your hypothetical multivariable calculus class, this might point you to the gradient. The gradient of a function at a given point is the normal vector to the tangent plane, and thus tells you the equation. In less technical language, the gradient at a point is a list of all the $a_i$ in the equation I gave above. And thus if the gradient of a function $f$ is $\nabla f$, then our linear approximation is given by $\nabla f(\mathbf{a}) \cdot \textbf{x} + c$.

So the "real" derivative here is the vector $\nabla f(\mathbf{x})$, which for any vector $\mathbf{x}$ gives us all the coefficients for the linear function that approximates our original function near $\mathbf{x}$. In particular, we get the approximation $$f(\mathbf{x}) \approx \nabla f(\mathbf{a}) \cdot (\mathbf{x} - \mathbf{a}) + f(\mathbf{a}).$$ Notice how similar this is to our earlier approximation! And we can use this to turn a hard-to-work-with function into an easy-to-work-with linear approximation.

But we can actually go one step further. Until now I've assumed that while my function might have many inputs, it only has one output. But for full generality we want to let our function have multiple outputs.

If a function has $n$ inputs and $m$ outputs we say it is a function from $\mathbb{R}^n$ to $\mathbb{R}^m$ or write $F: \mathbb{R}^n \to \mathbb{R}^m$. We usually break this up output by output; so we have $F(\mathbf{x}) = (f_1(\mathbf{x}), \dots, f_m(\mathbf{x}))$. Each component has many inputs but just one output, so we can compute the linear approximation just like we did before.

Since $F$ is a list of many-to-one functions, our linear approximation will be a list of vectors. And if you're clever, you might realize that a list of vectors is a matrix. The total derivative of a function $F$ at a point $a$ is a matrix $dF_\mathbb{a}$, and the approximation is $$F(\mathbf{x}) \approx dF_\mathbf{a} \cdot\mathbf{x} + F(\mathbf{a}).$$ So the best linear approximation of any function with many inputs and outputs is going to be given by some matrix the total derivative, or the Jacobian. This is basically the fundamental object of multivariable differential calculus--though it usually isn't taught that way.

Because I'm a mathematician, I can't resist abstracting one more step. (Going up one more meta-level? I dunno, I guess that's endemic around here).

When a mathematician says a function is linear, he generally means that it has the following two properties: $$f(\mathbf{x} + \mathbf{y}) = f(\mathbf{x}) + f(\mathbf{y})$$ $$f(c \mathbf{x}) = c f(\mathbf{x}).$$ In any finite-dimensional setup these functions correspond to matrices, and in the many-to-one variable setup these functions are dot products. (and in the typical single-variable case, every linear function is just scalar multiplication--or multiplication by a $1 \times 1$ matrix).

You might have noticed that in the preceeding exposition, I basically ignored the constant at the end of every equation. And that's because on technical points that makes the equation not linear in this sense. The actual linear function is the number/vector/matrix that we multiply by.

And this means we can give a very general definition of a (Frechet) derivative, for any function between two normed vector spaces. If $f: A \to B$ is a map of normed vector spaces, then $L$ is the derivative at $a$ if it is a (bounded) linear function from $A$ to $B$, and $$\lim_{x \to a} \frac{f(x) - f(a) - L(x-a)}{x-a} = 0.$$ If you're familiar with the usual single-variable derivative definition, you can write it out and see that this is the same thing.