Linear Programming

Note

Given a set of variables, assign real values to each to:

1. Satisfy a set of linear equations (Linearity) and/or inequalities over the variables
2. Maximize or minimize a linear objective function

For example, we are given a list of constraints, values and a goal (optimize for some linear objective problem). You can usually plot the constrains which defines a feasible region. For lines with constant objective values (some equation of a line), the optimal solution for a given problem is the last point in the feasible region that line touches which always lies on a vertex of the feasible region. The only exceptions are when the problem is not well-defined.

• LP could be infeasible, it is not possible to satisfy all constraints (infeasible like in Input-Output Parameterization solving)
• LP could be unbounded (we can achieve arbitrarily large or small objective values)

Solving LPs

Simplex

1. Start at a vertex arbitrarily
2. Look for an adjacent vertex of better objective values
3. Repeat until no better vertex exists

This is optimal since the feasible region is convex!

This idea still apply’s when we have n variables in n dimensions.

Variants

1. Can be a minimization or maximization
2. Constraints can be equalities or inequalities
3. Variables can be nonnegative or can be free to be negative or positive
4. We can reform these linear programming problems
   1. Like turning inequality constraints into equalities (using slack variables)
   2. Turning problem into one with nonnegative variables
5. The standard form for a linear program (LP) is:
   1. Maximize $c^{T}x$
   2. Subset to $Ax<b$
   3. and $x\ge 0$
   4. This is a system of equations where A is a matrix and b is a row vector
   5. The objective is a linear combination of c and x $c_1{x}_1+\dots c_n{x}_n$
   6. The constraints are a linear combination of x and x $a_{11}{x}_1+a_{12}{x}_2<b_1$. Setting up the Input-Output Parameterization equations forms a linear programming problem
6. Therefore, the input is A, b, c and the output is $x$ that satisfies $Ax<b$ and $x\ge 0$ and maximizes $c^{T}x$

Duality

Duality is the idea that every linear programming problem has another related problem called the dual.

The dual is of the form $\min c^{T}x$ (assuming the primal was a max) subject to $A^{T}y\ge c,y\ge 0$ . Then identify parts of this equation and solve.

Note

If an LP is bounded, then so is its dual, and the primal and dual have the same optimal value.

This is useful because:

• We can verify a solution to primal is optimal by solving the dual
• We can solve the dual instead of the primal
• If primal is unbounded then its dual is infeasible (same for the other way around)

If $x^{\ast }$ is the optimal solution to the primal and $y^{\ast }$ is the optimal solution to the dual, then $c^T{x}^{\ast }=b^T{y}^{\ast }$.

The new Simplex

1. Let v be any vertex of the feasible region
2. while there is a neighbour v’ of v with better objective value
   1. Set v=v’ Here, we need to understand what each of these inputs actually are from our linear programming problem:

• Each equality defines a hyperplane
• Each inequality define a half-plane
• Each vertex is an intersection of n hyperplanes (in 2D, each vertex is an intersection of 2 lines)
• More formally:
  • A point is a vertex if
    • It satisfies n constraints with equality and satisfies all other constraints (with inequality)
  • Two vertices are neighbours if they have n-1 defining constraints in common
  • We assume vertices are not degenerate: they cannot satisfy n+1 constraints with equality At each inner-workings:

1. Check if the current vertex is optimal
2. If it is not, then determine a vertex to move to
3. The origin is optimal if $c_1\dots c_n<0$
4. Iteratively
   1. Check if the origin is a vertex (are constraints sastisfied)
   2. If the coefficients of our objective are negative we are optimal since we cannot increase it
   3. Examining constraints, make new vertex
   4. Once we move from the origin to a new vertex, we pretend that this vertex is the origin by changing coordinates.
   5. At this new origin our ith constraint looks like $a_{i1}{x}_1+\cdots +a_{in}{x}_n=b_i$
   6. Therefore, a change of coordinates is $y_i=b_i-(a_{i_1}{x}_1+\cdots +a_{in}{x}_n)$ (use the constraint that we reached to put our $x^{\prime }s$ in terms of $y^{\prime }s$. By definition, $y_i$ is 0 at the vertex.
   7. Now we can rewrite LP in terms of $y_1,\dots ,y_n$ and repeat the process (where we also
   8. Note that we can also solve for each $x_i$ as a function of the $y$’s (all constraints and objectives)

This new LP has several properties:

1. It includes n constraints $y_1,\dots ,y_n>0$
2. The vertex v is the origin in the y-coordinates
3. The cost function becomes $\max c_v+\overline{c^T}y$
   1. $c_v$ is the objective value at vertex v
   2. $\bar{c}$ is the transformed cost vector Now we are back to the origin

Note

Note that:

• If the origin is not feasible, we can find a start by solving an LO
• If a point satisfies n+1 constraints, perturb $b_i$ values slightly to break
• If we get n constraints with infinite number of solutions, the LP can be declared unbounded

The runtime is exponential in the worst case but is realistically polynomial, especially using interior points methods.