# 1 Linear Programming

## 1.1 Introduction

Problem description:

• motivate by min-cost flow

• bit of history

• everything is LP

• NP and coNP. P breakthrough.

• general form:

• variables

• constraints: linear equalities and inequalities

• $$x$$ feasible if satisfies all constraints

• LP feasible if some feasible $$x$$

• $$x$$ optimal if optimizes objective over feasible $$x$$

• LP is unbounded if have feasible $$x$$ of arbitrary good objective value

lemma: every LP is infeasible, has opt, or is unbounded

• (by compactness of $$R^n$$ and fact that polytopes are closed sets).

Problem formulation:

• canonical form: $$\max c^Tx, Ax \le b$$

• note $$c$$ is a row vector but I won’t always write $$c^T$$

• matrix representation, component-wise $$\le$$

• rows $$a_i$$ of $$A$$ are constraints

• $$c$$ is objective

• any LP has transformation to canonical:

• max/min objectives same

• move vars to left, consts to right

• negate to flip $$\le$$ for $$\ge$$

• replace $$=$$ by two $$\le$$ and $$\ge$$ constraints

• standard form: $$\min c^Tx, Ax=b, x\ge 0$$

• slack variables

• splitting positive and negative parts $$x \rightarrow x^+-x^-$$

• $$Ax \ge b$$ often nicer for theory; $$Ax=b$$ good for implementations.

Some steps towards efficient solution:

• What does answer look like?

• Can it be represented effectively?

• Easy to verify it is correct?

• Is there a small proof of no answer?

## 1.2 Linear Equalities

How solve? First review systems of linear equalities.

• $$Ax=b$$. when have solution?

• baby case: $$A$$ is squre matrix with unique solution.

• demonstrate solution by giving $$x$$

• easy to verify correct!

• construct using, eg, Gaussian elimination.

• Suppose there’s a answer. Can we write it down?

• discuss polynomiality, integer arithmetic later

• equivalent statements:

• $$A$$ invertible

• $$A^T$$ invertible

• det$$(A)\ne 0$$

• $$A$$ has linearly independent rows

• $$A$$ has linearly independent columns

• $$Ax=b$$ has unique solution for every $$b$$

• $$Ax=b$$ has unique solution for some $$b$$.

To talk formally about polynomial size/time, need to talk about size of problems.

• integer $$n$$ has size $$\log n$$

• rational $$p/q$$ has size size$$(p)$$+size$$(q)$$

• size(product) is sum(sizes).

• dimension $$n$$ vector has size $$n$$ times size of number

• $$m \times n$$ matrix similar: $$mn$$ times size of numbers

• size (matrix product) at most sum of matrix sizes

• our goal: polynomial time in size of input, measured this way

Claim: if $$A$$ is $$n \times n$$ matrix, then $$\det(A)$$ is poly in size of $$A$$

• more precisely, twice the size

• proof by writing determinant as sum of permutation products. $det(A)=\sum_{\pi:n\rightarrow n} \textrm{sign}(\pi)\prod_{i=1}^{n} A_{i\pi(i)}$

• each product has size $$n$$ times size of numbers

• $$n!$$ products

• so size at most size of ($$n!$$ times product) $$\le n\log n+n\cdot$$size(largest entry).

Corollary:

• inverse of matrix is poly size (write in terms of cofactors—Cramer’s rule). For any $$i$$, $x_i^*=\frac{det(A_i)}{det(A)},$ where $$A_i$$ is the matrix $$A$$ with the $$i$$-th column substituted with $$b$$.

• solution to $$Ax=b$$ is poly size (by inversion)

• can use this to argue Gaussian eliminiation produces poly size answer

• not obvious, since multiplying two integers can yield a double-size integer and we do polynomially many multiplies in GE

• but can argue if work in units of $$1/det(A)$$ that all stays integer

What if $$A$$ isn’t square? Can we find an answer?

• Note we are asking if columns of A span $$b$$

• Find a maximal set of linearly independent columns

• These span $$b$$ if $$A$$ does.

• Extend to a basis by adding (independent) columns

• Now previous analysis applies

• Unique $$x$$

So can check answer in polynomial time.

Can we show there isn’t an answer?

• $$Ax=b$$ has a witness for true: give $$x$$.

• How about a proof that there is no solution?

• “Failure of algorithm to work” is a hard witness to check

• note that “$$Ax=b$$” means columns of $$A$$ span $$b$$.

• in general, set of points $$\set{Ax \mid x \in \Re^n}$$ is a subspace

• 2d case

• $$\set{Ax}$$ is a line through origin

• $$A$$ is vector in direction of line

• point $$b$$ not on line

• i.e., part of it (projection) is perpendicular to line

• claim: no solution iff for some $$y$$, $$yA=0$$ but $$yb \ne 0$$.

• proof: if $$Ax=b$$, then $$yA=0$$ means $$yb=yAx=0$$.

• if no $$Ax = b$$, means columns of $$A$$ don’t span $$b$$

• set of points $$\set{Ax}$$ is subspace not containing $$b$$

• find part of $$b$$ perpendicular to subspace, call it $$y$$

• then $$yb \ne 0$$, but $$yA=0$$,

• standard form LP asks for linear combo too, but requires that all coefficients of combo be nonnegative!

• wait, we showed existence, but is $$y$$ polynomial size?

• note $$yb \ne 0$$ has solution means $$yb=1$$ has solution

• so solve $$y \cdot \binom{A}{b} = \binom{0}{1}$$

• we proved this matrix problem has polynomial number of bits solution

• and can find by e.g. Gaussian elimination

Summary:

• in polytime, can find solution

• and provide easy polytime checkable solution

• and in polytime can determine insoluble

• and give easy polytime checkable “nonsolution”

## 1.3 Geometry

Polytopes

• canonical form: $$Ax \ge b$$ is an intersection of (finitely many) halfspaces, a (convex) polytope

• standard form: $$Ax=b$$ is an intersection of hyperplanes (thus a subspace), then $$x \ge 0$$ intersects in some halfspace. Also a polytope, but not full dimensional.

• polytope is bounded if fits inside some box.

• (some call this polyhedron. Others invert definitions.

• either formulation defines a convex set:

• if $$x, y \in P$$, so is $$\lambda x+(1-\lambda)y$$ for $$\lambda \in 0,1$$.

• that is, line from $$x$$ to $$y$$ stays in $$P$$.

• halfspaces define convex sets. Converse also true!

• let $$C$$ be any convex set, $$z \notin C$$.

• then there is some $$a,b$$ such that $$ax \ge b$$ for $$x \in C$$, but $$az < b$$.

• proof by picture. also true in higher dimensions (don’t bother proving)

• deduce: every convex set is the intersection of the halfspaces containing it.

## 1.4 Basic Feasible Solutions

Again, let’s start by thinking about structure of optimal solution.

• Can optimum be in “middle” of polytope?

• Not really: if can move in all directions, can move to improve opt.

Where can optimum be? At “corners.”

• “vertex” is point that is not a convex combination of two others

• “extreme point” is point that is unique optimum in some direction

Basic solutions:

• A constraint $$ax \le b$$ or $$ax=b$$ is tight or active if $$ax=b$$

• for $$n$$-dim LP, point is basic if (i) all equality constraints are tight and (ii) $$n$$ linearly independent constraints are tight.

• in other words, $$x$$ is at intersection of boundaries of $$n$$ linearly independent constraints

• note $$x$$ is therefore the unique intersection of these boundaries.

• a basic feasible solution is a solution that is basic and satisfies all constraints.

In fact, vertex, extreme point, bfs are equivalent.

• Proof left somewhat to reader.

Any standard form lp $$\min cx,\ Ax=b,\ x\ge 0$$ with opt has one at a BFS.

• Suppose opt $$x$$ is not at BFS

• Then less than $$n$$ tight constraints

• So at least one degree of freedom

• i.e, there is a (linear) subspace on which all those constraints are tight.

• In particular, some line through $$x$$ for which all these constraints are tight.

• Write as $$x+\epsilon d$$ for some vector direction $$d$$

• Since $$x$$ is feasible and other constraints not tight, $$x+\epsilon d$$ is feasible for small enough $$\epsilon$$.

• Consider moving along line. Objective value is $$cx+\epsilon cd$$.

• So for either positive or negative $$\epsilon$$, objective is nonincreasing, i.e. doesn’t get worse.

• Since started at opt, must be no change at all—i.e., $$cd=0$$.

• So can move in either direction.

• In at least one direction, some $$x_i$$ is decreasing.

• Keep going till new constraint becomes tight (some $$x_i=0$$).

• Argument can be repeated until $$n$$ tight constraints, i.e. bfs

• Conclude: every standard form LP with an optimum has one at a bfs.

• canonical form has oddities: e.g. $$\min 0x+1y \mid y \le 1$$.

• but any bounded, feasible LP has BFS optimum

• generalize idea of moving without worsening objective until new constraint becomes tight.

Corollaries:

• Actually showed, if $$x$$ feasible, exists BFS with no worse objective.

• Note that in canconical form, might not have opt at BFS ($$\min y$$ over $$(x,y)$$ such that $$0 \le x \le 1$$).

• But this only happens if LP is unbounded

• In particular, if opt is unique, it is a bfs.

• More generally, for our proof above to “break”, the line we made through opt can’t hit any constraint

• so feasible set contains an entire line

• so if polytope is feasible and “half bounded”, there is an opt

• standard form is half-bounded since positive orthant is.

Question:

• arbitary unbounded LP with optimum transforms to standard LP with optimum

• but standard LP with OPT has one at BFS

• where did the BFS come from that wasn’t in original LP?

• consider $$\min 0x+1y \mid y \ge 1$$.

• $$x$$ is unbounded so no BFS

• conversion create $$x^+$$ and $$x^-$$, writes $$x=x^+-x^-$$ with $$x^+,x^- \ge 0$$

• this turns the point $$x^+=x^-=0$$, i.e. $$x=0$$, into a vertex!

## 1.5 Vertices and Extreme Points

Two other characterizations of corner.

Vertex:

• “vertex” is point that is not a convex combination of two others

• BFS if-and-only-if vertex:

• if point is convex combo (not vertex), consider line through it

• all points on it feasible

• so don’t have $$n$$ tight constraints

• conversely, if less than $$n$$ tight constraints, they define feasible subspace containing line through point

• so point is convex combo of points on line.

Extreme Point

• “extreme point” is point that is unique optimum in some direction

• Extreme point implies BFS

• if cannot move to any other opt, must have $$n$$ tight constraints.

• Conversely, BFS is extreme point

• BFS means feasible and total of $$n$$ tight constraints

• let $$T$$ be set of $$x_i \ge 0$$ constraints that are tight

• take objective $$\sum_{i \in T} x_i$$

• consider any other feasible point

• It’s loose on some $$i \in T$$

• so objective value $$>0$$

• so not optimal

• Thus, BFS is unique opt for this objective, i.e. extreme point

• This proof assumes standard form, but easily generalizes.

Shows output is polynomial size:

• Let $$A'$$ and correspoinding $$b'$$ be $$n$$ tight constraints (rows) at opt

• Then opt is (unique) solution to $$A'x=b'$$

• We saw that such an inverse is represented in polynomial size in input

• (So, at least weakly polynomial algorithms seem possible)

Yields first algorithm for LP: try all bfs.

• How many are there?

• just choose $$n$$ tight constraints out of $$m$$, check feasibility and objective

• Upper bound $$\binom{m}{n}$$

OK, this is an exponential method for finding the optimum. Maybe we can do better if we just try to verify the optimum. Let’s look for a way to prove that a given solution $$x$$ is optimal.

Quest for nonexponential algorithm: start at an easier place: how decide if a solution is optimal?

• decision version of LP: is there a solution with opt$$>k$$?

• this is in NP, since can exhibit a solution (we showed poly size output)

• is it in coNP? Ie, can we prove there is no solution with opt$$>k$$? (this would give an optimality test)