Linear Programming: Introduction and Duality

Presentation on theme: "Linear Programming: Introduction and Duality"— Presentation transcript:

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

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

3 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)

4 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 x1+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

5 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.

6 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≦ y1,y2≧0 (y1+5y2)*x1≦7x1 (-y1+2y2)*x2≦1x2 (3y1-y2)*x3≦5x3

7 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≦ y1,y2≧0 What is the dual of the dual program?

8 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

9 Linear programming Max flow

10 Linear programming

11 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)

12 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

13 The LP-duality theorem

14 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

15 Algorithm design techniques
LP-rounding Primal-dual schema

16 Thank you.