15-780: Grad AILec. 8: Linear programs, DualityGeoff Gordon (this lecture)Tuomas Sandholm TAs Erik Zawadzki, Abe OthmanAdmin•Test your handin directories‣/afs/cs/user/aothman/dropbox/USERID/‣where USERID is your Andrew ID•Poster session: ‣Mon 5/2, 1:30–4:30PM, room TBA•Readings for today & Tuesday on class siteProject idea•Answer the question: what is fairness?In case anyone thinks of slacking offLPs, ILPs, and their ilkBoyd & Vandenberghe.!Convex Optimization.!Sec 4.3 and 4.3.1.((M)I)LPs•Linear program:min 3x + 2y s.t.x + 2y ! 3x ! 2x, y " 0•Integer linear program: constrain x, y ∈ ℤ•Mixed ILP: x ∈ ℤ, y ∈ ℝExample LP•Factory makes widgets and doodads•Each widget takes 1 unit of wood and 2 units of steel to make•Each doodad uses 1 unit wood, 5 of steel•Have 4M units wood and 12M units steel•Maximize profit: each widget nets $1, each doodad nets $2Factory LPM Widgets !M Doodads !feasiblew + d ! 42w + 5d ! 12profit = w + 2dFactory LPM Widgets !M Doodads !feasiblew + d ! 42w + 5d ! 12profit = w + 2dFactory LPM Widgets !M Doodads !feasiblew + d ! 42w + 5d ! 12profit = w + 2d(8/3,4/3)OPT = 16/3Example ILP•Instead of 4M units of wood, 12M units of steel, have 4 units wood and 12 units steelFactory exampleWidgets !Doodads !w + d ! 42w + 5d ! 12profit = w + 2dOPT = 5Factory exampleWidgets !Doodads !w + d ! 42w + 5d ! 12profit = w + 2dLP relaxations•Above LP and ILP are the same, except for constraint w, d ∈ ℤ•LP is a relaxation of ILP•Adding any constraint makes optimal value same or worse•So, OPT(relaxed) " OPT(original)(in a maximization problem)Factory relaxation is pretty closeWidgets !Doodads !w + d ! 42w + 5d ! 12profit = w + 2dWidgets !Doodads !13Unfortunately…profit = w + 2dThis is called an integrality gapFalling into the gap•In this example, gap is 3 vs 8.5, or about a ratio of 0.35•Ratio can be arbitrarily bad‣but, can sometimes bound it for classes of ILPs•Gap can be different for different LP relaxations of “same” ILP14From ILP to SAT•0-1 ILP: all variables in {0, 1}•SAT: 0-1 ILP, objective = constant, all constraints of formx + (1–y) + (1–z) " 1•MAXSAT: 0-1 ILP, constraints of formx + (1–y) + (1–z) " sjmaximize s1 + s2 + …Pseudo-boolean inequalities•Any inequality with integer coefficients on 0-1 variables is a PBI•Collection of such inequalities (w/o objective): pseudo-boolean SAT•Many SAT techniques work well on PB-SAT as wellComplexity•Decision versions of ILPs and MILPs are NP-complete (e.g., ILP feasibility contains SAT)‣so, no poly-time algos unless P=NP‣in fact, no poly-time algo can approximate OPT to within a constant factor unless P=NP•Typically solved by search + smart techniques for ordering & pruning nodes•E.g., branch & cut (in a few lectures)—like DPLL (DFS) but with more tricks for pruningComplexity•There are poly-time algorithms for LPs‣e.g., ellipsoid, log-barrier methods‣rough estimate: n vars, m constraints ⇒ ~50–200 # cost of (n # m) regression•No strongly polynomial LP algorithms known—interesting open question‣simplex is “almost always” polynomial[Spielman & Teng]max 2x+3y s.t." x + y ≤ 4"" 2x + 5y ≤ 12" x + 2y ≤ 5"" x, y ≥ 0Terminologymax 2x+3y s.t." x + y ≤ 4"" 2x + 5y ≤ 12" x + 2y ≤ 5"" x, y ≥ 0Finding the optimummax 2x+3y s.t." x + y ≤ 4"" 2x + 5y ≤ 12" x + 2y ≤ 5"" x, y ≥ 0Finding the optimumWhere’s my ball?Unhappy ball‣min 2x + 3y subject to‣x " 5‣x ! 1Transforming LPs•Getting rid of inequalities (except variable bounds)•Getting rid of unbounded variablesStandard form LP•all variables are nonnegative•all constraints are equalities•E.g.: q = (x y u v w)Tmax 2x+3y s.t.x + y ! 4$2x + 5y ! 12x + 2y ! 5x, y " 0$max cTq s.t. Aq = b, q " 0(componentwise)Why is standard form useful?•Easy to find corners•Easy to manipulate via row operations•Basis of simplex algorithm Bertsimas and Tsitsiklis. Introduction to Linear Optimization. Ch. 2–3.Finding corners1 1 1 0 0 42 5 0 1 0 121 2 0 0 1 5set x, y = 01 1 1 0 0 42 5 0 1 0 121 2 0 0 1 5set v, w = 01 1 1 0 0 42 5 0 1 0 121 2 0 0 1 5set x, u = 0x y u v w RHSRow operations•Can replace any row with linear combination of existing rows‣as long as we don’t lose independence•Elim. x from 2nd and 3rd rows of A•And from c:x y u v w RHS1 1 1 0 0 42 5 0 1 0 121 2 0 0 1 52 3 0 0 0 ↑Presto change-o•Which are the slacks now?‣ ‣vars that appear in•Terminology: “slack-like” variables are called basicx y u v w RHS1 1 1 0 0 40 3 -2 1 0 40 1 -1 0 1 10 1 -2 0 0 ↑The “new” LPmax y – 2u y + u ! 43y – 2u ! 4y – u ! 1y, u " 0Many different-looking but equivalent LPs, depending on which variables we choose to make into slacksOr, many corners of same LPx y u v w RHS1 1 1 0 0 40 3 -2 1 0 40 1 -1 0 1 10 1 -2 0 0 ↑Basis•Which variables can we choose to make basic?x y u v w RHS1 1 1 0 0 42 2 0 1 0 53 3 0 0 1 92 1 0 0 0 ↑Nonsingular•We can assume‣n " m (at least as many vars as constrs)‣A has full row rank•Else, drop rows (w/o reducing rank) until true: dropped rows are either redundant or impossible to satisfy‣easy to distinguish: pick a corner of reduced LP, check dropped = constraints•Called nonsingular standard form LP‣means basis is an invertible m # m submatrixNaïve (slooow) algorithm•Iterate through all subsets B of n vars‣if m constraints, how many subsets?•Check each B for‣full rank (“basis-ness”)‣feasibility (A(:,B) \ RHS " 0)•If pass both tests, compute objective•Maintain running winner, return at endDegeneracy•Not every set of m variables yields a corner‣some have rank < m (not a basis)‣some are infeasible•Can the reverse be true? Can two bases yield the same corner? (Assume nonsingular standard-form LP.)Degeneracyx y u v w RHS1 1 1 0 0 4 2 5 0 1 0 12 1 2 0 0 1 16/3 1 0 0 -2 5 8/30 1 0 1 -2 4/30 0 1 1 -3 0 1 0 2 0 -1 8/30 1 -1 0 1 4/30 0 1 1 -3 0Degeneracy in 3DDegeneracy in 3Dwe’ll pretend this never happensNeighboring bases•Two bases are neighbors if they share (m–1) variables•Neighboring feasible bases correspond to vertices connected by an edge (note: degeneracy)x y z u v w RHS1 0 0 1 0 0 10 1 0 0 1 0 10 0 1 0 0 1 1Improving our search•Naïve: enumerate all possible bases•Smarter: maybe neighbors of good bases are also
View Full Document
Unlocking...