The apparent paradox: feasibility ≡ optimization

  • Checking feasibility of a general polytope is as hard as solving the LP. Guess a target value r, add the constraint cᵀx ≤ r, and ask whether a feasible point exists; binary search on r then recovers OPT 16:03, 16:41, 16:59, 20:22, 20:45.
  • So getting a starting vertex "for free" would be suspicious — unless the LP used for it is a special, easy one.

Why the binary search terminates (bit-precision argument)

  • A vertex is (as proved later) the intersection of m tight constraints, so there are at most n choose m vertices, and computing one means solving a linear system on a submatrix of A 17:40, 17:59, 18:30.
  • If all entries of A, b, c are integers of at most B bits, one can bound the number of bits needed to write down a vertex, hence OPT is a rational of bounded precision 18:30, 18:45.
  • Therefore the binary search only needs that many iterations — it never has to refine beyond the known precision bound 19:12, 19:48, 20:09.
  • Caveat stated explicitly: this argument assumes vertices are optimal and that vertices come from linear systems on submatrices of A — both proved later in the lecture 19:48.

The trick: run Simplex twice

Reduce "find a starting vertex" to a different LP that has an obvious starting vertex 20:45:

min  t
s.t. Ax = (1 − t)·b
     x ≥ 0
     0 ≤ t ≤ 1

21:16

  • Not yet standard form because of t ≤ 1; fix it with a slack: s_t + t = 1, s_t ≥ 0 22:04, 22:23.

The obvious starting vertex

  • x = 0, t = 1, s_t = 0 is feasible 22:23, 23:06.
  • It is a vertex, not merely feasible — checked against the definition: any candidate y can put no mass on the x coordinates (one of x ± y would go negative), none on the slack (same reason), and none on t (increasing t violates t ≤ 1), so y = 0 23:40, 24:31, 24:53.

What minimizing t buys you

  • If the optimum reaches t = 0, the constraint becomes Ax = b, so you have a feasible point of the original LP — and the point returned is in fact a vertex of the original polytope 24:53, 25:29.
flowchart TD
    A["Auxiliary LP: min t, Ax = (1−t)b"] -->|obvious vertex x=0, t=1| B[Run Simplex #1]
    B --> C{optimal t = 0?}
    C -->|yes| D[Vertex of original P]
    C -->|no| E[Original LP infeasible]
    D --> F[Run Simplex #2 on the real LP]