Linear Programming: Introduction and Duality NTHU CS CSBB lab 劉至善 大家好,今天我要報告的主題是Linear programming. 主要是簡單介紹一下linear program跟他的對偶性duality

Outline Linear programming The LP-duality theorem Linear-program duality theorem 然後會用max flow min cut 做一個linear program 的primal轉dual的例子

Linear programming Linear programming The problem of optimizing a linear function subject to linear inequality constraints. Minimize 7x1+x2+5x3 Subject to x1-x2+3x3≧10 5x1+2x2-x3≧6 x1,x2,x3≧0 Linear programming是找出限制在一些線性不等式中的一個linear function的最佳解.(maximize或是minimize)

Linear programming Linear programming Any solution satisfies all the constraints is a feasible solution. Is 7x1+x2+5x3≦30? Yes, (2,1,3) makes 7x1+x2+5x3=30. 如果存在一組解,能夠滿足所有的條件,我們就稱他為一個feasible solution 那要怎麼判定這個解不成立?對於找出min值問題,我們就找出他的lower bound. Minimize 7x1+x2+5x3= 7*2+1+5*3=30 Subject to x1-x2+3x3 = 2-1+3*3=10 ≧10 5x1+2x2-x3 =5*2+2*1-3=9 ≧6 x1,x2,x3≧0

Linear programming Linear programming How to provide a “NO” certificate? Find an optimal lower bound. 7x1+x2+5x3 ≧ 6x1+x2+2x3 =(x1-x2+3x3)+(5x1+2x2-x3) ≧16. 如果存在一組解,能夠滿足所有的條件,我們就稱他為一個feasible solution 那要怎麼判定這個解不成立?對於找出min值問題,我們就找出他的lower bound.

Linear programming Minimize 7x1+x2+5x3 Subject to x1-x2+3x3≧10 y1*(x1-x2+3x3 )+y2*(5x1+2x2-x3) ≧10y1+6y2 → (y1+5y2)*x1 +(-y1+2y2)*x2 +(3y1-y2)*x3 ≧10y1+6y2 Maximize 10y1+6y2 Subject to y1+5y2≦7 -y1+2y2≦1 3y1-y2≦5 y1,y2≧0 (y1+5y2)*x1≦7x1 (-y1+2y2)*x2≦1x2 (3y1-y2)*x3≦5x3

Linear programming Primal program Dual program Minimize 7x1+x2+5x3 Subject to x1-x2+3x3≧10 5x1+2x2-x3≧6 x1,x2,x3≧0 Maximize 10y1+6y2 Subject to y1+5y2≦7 -y1+2y2≦1 3y1-y2≦5 y1,y2≧0 What is the dual of the dual program?

Linear programming Maximize 10y1+6y2 Subject to y1+5y2≦7 -y1+2y2≦1 x1*(y1+5y2)+x2*(-y1+2y2)+x3*(3y1-y2)≦7x1+x2++5x3 →(x1-x2+3x3)*y1 +(5x1+2x2-x3)*y2≦7x1+x2+5x3 Minimize 7x1+x2+5x3 Subject to x1-x2+3x3≧10 5x1+2x2-x3≧6 x1,x2,x3≧0 (x1-x2+3x3)*y1≧10y1 (5x1+2x2-x3)*y2≧6y2

Linear programming Max flow

Linear programming

Linear programming Every feasible solution to the dual program gives a lower bound on the optimum value of the primal. 26 ∞ dual solutions primal solutions 10y1+6y2 7x1+x2+5x3 (2,1) (7/4,0,11/4)

The LP-duality theorem The primal program has finite optimum iff its dual has finite optimum. Moreover, if x*=(x1*,…,xn*) and y*=(y1*,…,ym*) are optimal solutions for the primal and dual programs, respectively, then

The LP-duality theorem

The LP-duality theorem (Complementary slackness conditions) Let x and y be primal and dual feasible solutions, respectively. Then, x and y are both optimal iff all of the following conditions are satisfied: Primal complementary slackness conditions Dual complementary slackness conditions

Algorithm design techniques LP-rounding Primal-dual schema

Thank you.