15-780: Grad AILec. 9: Linear programs, DualityGeoff Gordon (this lecture)Tuomas Sandholm TAs Erik Zawadzki, Abe OthmanAdmin•Have you tested your handin directories?‣/afs/cs/user/aothman/dropbox/USERID/‣where USERID is your Andrew ID•Poster session: ‣???Review•LPs, ILPs, MILPs‣ℝ or ℤ variables‣linear ≤ ≥ =‣linear objective‣LP relaxations, integrality gap‣relation to SAT, MAXSAT, PBI‣complexity (LP: P; ILP: NP & no approx)‣(in)feasible, (sub)optimal, (in)activeReview•Standard form: all vars ≥ 0, all = constraints•Nonsingular: n vars ≥ m constraints, rank m•Basis‣spans Rng(A) (m × m invertible submatrix)‣corresponds to “corner”‣using row ops to make basic variables into “slacks” → tableau notation•Degeneracy: distinct bases yield same corner•Naïve algorithm: check all basesFinding 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 RHSSimplex in one slide•Given a nonsingular standard-form LP‣make it nonsingular if needed•Start from a feasible basis and its tableau‣big-M if needed•Pick non-basic variable w/ objective > 0 (max)•Pivot it into basis, getting neighboring basis‣select exiting variable to keep feasibility•Repeat until all non-basic variables have objective < 0 (max)(ignoring degeneracy, which is actually important)Example x y s t u RHS 1 1 1 0 0 4 2 5 0 1 0 12 1 2 0 0 1 5 2 3 0 0 0 ↑ max 2x + 3y s.t.x + y ≤ 42x + 5y ≤ 12x + 2y ≤ 5Examplemax 2x + 3y s.t.x + y ≤ 42x + 5y ≤ 12x + 2y ≤ 5 x y s t u RHS 0.4 1 0 0.2 0 2.4 0.6 0 1 -0.2 0 1.6 0.2 0 0 -0.4 1 0.2 0.8 0 0 -0.6 0 ↑Examplemax 2x + 3y s.t.x + y ≤ 42x + 5y ≤ 12x + 2y ≤ 5 x y s t u RHS 1 0 0 -2 5 1 0 1 0 1 -2 2 0 0 1 1 -3 1 0 0 0 1 -4 ↑Examplemax 2x + 3y s.t.x + y ≤ 42x + 5y ≤ 12x + 2y ≤ 5 x y s t u RHS 1 0 2 0 -1 3 0 1 -1 0 1 1 0 0 1 1 -3 1 0 0 -1 0 -1 ↑Big M•How do we get one? ‣for each violated constraint, add var w/ coeff –1‣penalize in objective, include in initial basis x y t u v w RHS 1 1 1 0 0 0 4 3 -2 0 1 0 0 4 1 -1 0 0 1 0 1 -3 -2 0 0 0 1 -1 1 -2 0 0 0 0 ↑•So far, assumed we started w/ initial feasible basisEx: combinatorial auctions•Goods: Newspaper, Magazine, L shoe, R shoe•Bids (note use of bidding language: 7 rt 16 numbers for B1 and 1 rt 16 for B2):‣N: +5; M: +4‣N, M: –3‣L, R: +10‣N, L, R: –5; M, L, R: –4; N, M, L, R: +3‣M: +10Bidder 1Bidder 2Winner determination•Goods: Newspaper, Magazine•Bids:‣N: +5; M: +4‣N, M: –3‣N, M: +4Bidder 1Bidder 2Bounds•Any feasible point yields lower bd: (N to B1, keep M) → 5•Upper bound: solve LP relaxation‣a bit expensive‣can we be lazier?n1m1 0 0.20.40.6 0.8100.20.40.60.8144.555.56Being lazy•A “hard” LP:$ max x + y s.t.% x + y ≤ 3% x ≤ 1 y ≤ 1 V. Vazirani. Approximation Algorithms. Ch 12.OK, we got lucky•What if it were:$ max x + 3y s.t.% x + y ≤ 3% x ≤ 1 y ≤ 1How general is this?•What if it were:$ max px + qy s.t.% x + y ≤ 3% x ≤ 1 y ≤ 1Let’s do it again•Note ≥, ≤, = constraints, min obj% min x – 2y s.t.% x + y ≥ 2% y ≤ 3 2x – y = 0Summary of LP duality•Use multipliers to write combined constraints%≥%≤$=•Constrain multipliers to give us a bound on objective (by matching coefficients)•Optimize to get tightest bound•Q: what happens if we take dual of dual?Ordering•For primal max problem (dual min):‣primal feas primal opt dual opt dual feas•For primal min problem (dual max):‣primal feas primal opt dual opt dual feasGeometricallyWidgets →Doodads →w + d ≤ 42w + 5d ≤ 12profit = w + 2dGeometricallyWidgets →Doodads →w + d ≤ 42w + 5d ≤ 12profit = w + 2dGeometricallyWidgets →Doodads →w + d ≤ 42w + 5d ≤ 12profit = w + 2dDual widgetsa →b →a = b = 1/3a + 2b ≥ 1a + 5b ≥ 20.50.51 1.5bound = 4a + 12bfeasibleDual variables as multipliersWidgets →Doodads →Ca: w + d ≤ 4Cb: 2w + 5d ≤ 12(1/3) Ca + (1/3) CbSo why bother?•Reason 1: any feasible solution to dual yields upper bound (compared with only optimal solution to primal)•Reason 2: dual might be easier to work with•Reason 3: solvers can often work w/ primal and dual at the same time for no extra costInterpreting the dual variables•Primal variables in the factory LP were how many widgets and doodads to produce•Interpreted dual variables as multipliers for primal constraints—not much intuition•Often possible to interpret dual variables as prices for primal constraintsDual variables as prices•Suppose someone offered us a quantity ε of wood, loosening constraint to w + d ≤ 4 + ε•How much should we be willing to pay for this wood?Dual variables as prices•Dual constrs stay same: a + 2b ≥ 1, a + 5b ≥ 2•Dual objective becomes: min (4+ε)a + 12b•Previous solution a = b = 1/3 still feasible‣still optimal if ε small enough•Bound changes to (4+ε)a + 12b, increase by ε/3•So we should pay up to $1/3 per unit of wood (in small quantities)Dual degeneracy•Primal degenerate = two bases, same corner•Dual can be degenerate too‣so, 4 possibilities for degeneracy•E.g., what if objective were w+d (not w+2d)?Dual degeneracyWidgets →Doodads →w + d ≤ 42w + 5d ≤ 12profit = w + dDual degeneracya →b →a + 2b ≥ 1a + 5b ≥ 10.50.51 1.5bound = 4a + 12bfeasiblea + 5b ≥ 2Complementary slackness•Suppose a constraint is inactive. Would we pay anything to have it relaxed?•Write si ≥ 0 for slack in primal constraint j•Write dj ≥ 0 for dual variable (multiplier, price) for constraint j•CS: at optimal primal and dual solutions,•Uses: certificate of optimality, proving that optimal solution satisfies some
View Full Document
Unlocking...