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?

• Can answer, nonanswer be found efficiently?

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\)

• It had better zero out all the added columns

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”

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.

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!

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)