15 780 Grad AI Lec 8 Linear programs Duality Geoff Gordon this lecture Tuomas Sandholm TAs Erik Zawadzki Abe Othman Admin 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 site Project idea Answer the question what is fairness In case anyone thinks of slacking off LPs ILPs and their ilk Boyd Vandenberghe Convex Optimization Sec 4 3 and 4 3 1 M I LPs Linear program min 3x 2y s t x 2y 3 x 2 x 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 2 Factory LP M Doodads w d 4 profit w 2d feasible M Widgets 2w 5d 12 Factory LP M Doodads w d 4 profit w 2d feasible M Widgets 2w 5d 12 Factory LP M Doodads w d 4 OPT 16 3 8 3 4 3 feasible M Widgets profit w 2d 2w 5d 12 Example ILP Instead of 4M units of wood 12M units of steel have 4 units wood and 12 units steel Factory example w d 4 Doodads profit w 2d 2w 5d 12 Widgets Factory example w d 4 Doodads profit w 2d OPT 5 Widgets 2w 5d 12 LP 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 close w d 4 Doodads profit w 2d 2w 5d 12 Widgets Unfortunately Doodads profit w 2d Widgets 13 This is called an integrality gap Falling 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 ILP 14 From ILP to SAT 0 1 ILP all variables in 0 1 SAT 0 1 ILP objective constant all constraints of form x 1 y 1 z 1 MAXSAT 0 1 ILP constraints of form x 1 y 1 z sj maximize 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 well Complexity 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 pruning Complexity 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 Terminology max 2x 3y s t x y 4 2x 5y 12 x 2y 5 x y 0 Finding the optimum max 2x 3y s t x y 4 2x 5y 12 x 2y 5 x y 0 Finding the optimum max 2x 3y s t x y 4 2x 5y 12 x 2y 5 x y 0 Where s my ball Unhappy ball min 2x 3y subject to x 5 x 1 Transforming LPs Getting rid of inequalities except variable bounds Getting rid of unbounded variables Standard form LP all variables are nonnegative all constraints are equalities E g q x y u v w T max 2x 3y s t x y 4 2x 5y 12 x 2y 5 x 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 corners x 1 2 1 y 1 5 2 u 1 0 0 v 0 1 0 w 0 0 1 RHS 4 12 5 1 1 1 0 0 2 5 0 1 0 1 2 0 0 1 4 12 5 set v w 0 1 1 1 0 0 2 5 0 1 0 1 2 0 0 1 4 12 5 set x u 0 set x y 0 Row 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 1 2 1 2 y 1 5 2 3 u 1 0 0 0 v 0 1 0 0 w RHS 0 4 0 12 1 5 0 Presto change o Which are the slacks now vars that appear in Terminology slack like variables are called basic x 1 0 0 0 y u v w 1 1 0 0 3 2 1 0 1 1 0 1 1 2 0 0 RHS 4 4 1 The new LP max y 2u y u 4 3y 2u 4 y u 1 y u 0 x 1 0 0 0 y u v w 1 1 0 0 3 2 1 0 1 1 0 1 1 2 0 0 RHS 4 4 1 Many different looking but equivalent LPs depending on which variables we choose to make into slacks Or many corners of same LP Basis Which variables can we choose to make basic x 1 2 3 2 y 1 2 3 1 u 1 0 0 0 v 0 1 0 0 w 0 0 1 0 RHS 4 5 9 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 submatrix Na ve slooow algorithm Iterate through all subsets B of m vars if m constraints n vars 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 end Degeneracy 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 Degeneracy x 1 2 1 y 1 5 2 u 1 0 0 v 0 1 0 w RHS 0 4 0 12 1 16 3 1 0 0 0 1 0 0 2 5 0 1 …
View Full Document
Unlocking...