# ECE 665 Spring 2005 Computer Algorithms with Applications to VLSI CAD

1 / 11
0
0
913 days ago, 280 views
PowerPoint PPT Presentation
ECE 665 Spring 2005 PC Calculations with Applications to VLSI computer aided design. Direct Programming Duality. w 1. w 2. w 3. Direct Program Double

### Presentation Transcript

Slide 1

﻿ECE 665 Spring 2005 Computer Algorithms with Applications to VLSI CAD Linear Programming Duality

Slide 2

w 1 w 2 w 3 Linear Program Dual – Example1 Primal LP (unique) max 100x 1 + 80x 2 s.to: 10x 1 + 5x 2  50 5x 1 + 5x 2  35 5x 1 + 15x 2  80 Primal arrangement: x 1 =3, x 2 =4, F p = 620 max c T x s.to : A x  b x  0 Dual LP (unique) min 50w 1 + 35w 2 + 80w 3 s.to: 10w 1 + 5w 2 + 5w 3  100 5w 1 + 5w 2 + 15w 3  80 Dual arrangement: w 1 =4, w 2 =12, w 3 =0 F d = 620 max w T b s.to: w T A  c T w  0 ECE 665 - LP Duality

Slide 3

Formulate it as a Linear Program (LP) Assign factors x i to each edge e i x i = 1 if edge e i is in the longest way x i = 0 generally Write the target work Write the limitation set x1 x3 x2 x4 x6 x5 4 2 x7 5 x9 2 x8 1 2 3 2 5 3 6 5 4 6 Example 2: Longest Path Problem ECE 665 - LP Duality

Slide 4

Primal Problem x1 x3 4 2 x2 5 x4 2 x6 x5 3 2 x7 x9 5 x8 3 1 2 6 3 6 5 4 Example 2: Longest Path Problem (2) max 4x1 + 5x2 + 2x3 + 2x4 + 2x5 + 3x6 + 5x7 + 3x8 + 6x9 st - x1 - x2 - x3 = - 1 x1 - x4 - x7 = 0 x2 + x4 - x5 = 0 x3 - x6 - x9 = 0 x5 + x6 - x8 = 0 x7 + x8 + x9 = 1 end ECE 665 - LP Duality

Slide 5

Primal Problem - arrangement x1 max 4x1 + 5x2 + 2x3 + 2x4 + 2x5 + 3x6 + 5x7 + 3x8 + 6x9 x3 st x2 - x1 - x2 - x3 = - 1 x1 - x4 - x7 = 0 x4 x2 + x4 - x5 = 0 x3 - x6 - x9 = 0 x5 + x6 - x8 = 0 x6 x5 4 x7 + x8 + x9 = 1 end 2 x7 5 LP OPTIMUM FOUND AT STEP 2 x9 2 x8 1 2 OBJECTIVE FUNCTION VALUE 3 1) 11.000000 2 VARIABLE VALUE REDUCED COST X1 1.000000 0.000000 5 X2 0.000000 1.000000 3 4 6 5 6 X3 0.000000 X4 1.000000 0.000000 X5 1.000000 0.000000 X6 0.000000 3.000000 X7 0.000000 2.000000 X8 1.000000 0.000000 X9 0.000000 3.000000 Example 2: Longest Path Problem (3) ECE 665 - LP Duality

Slide 6

Dual Problem plan + arrangement w1=0 min - w1 + w6 4 w2=4 2 st 5 - w1 + w2 > 4 w4=5 - w1 + w3 > 5 2 - w1 + w4 > 2 w3=6 - w2 + w3 > 2 - w3 + w5 > 2 3 2 - w4 + w5 > 3 - w2 + w6 > 5 w5=8 - w5 + w6 > 3 5 - w4 + w6 > 6 3 1 2 6 end LP OPTIMUM FOUND AT STEP 7 w6=11 OBJECTIVE FUNCTION VALUE 1) 11.000000 3 6 5 4 VARIABLE VALUE REDUCED COST W1 0.000000 W2 4.000000 0.000000 W3 6.000000 0.000000 W4 5.000000 0.000000 W5 8.000000 0.000000 W6 11.000000 0.000000 Example 2: Longest Path Problem (4) Interpretation of double factors : w i = separation of hub I from source Note: This is as yet a longest way issue ( Critical Path or Scheduling issue ): Find a base separation from sink to source that fulfills all edge-length requirements. ECE 665 - LP Duality

Slide 7

Primal Problem x3 x7 x1 x4 x0 max x0 st x2 x5 x8 - x1-x2+x0 = 0 x6 x1-x3-x4 = 0 Max stream x2-x5-x6 = 0 x3+x5-x7 = 0 x4+x6-x8 = 0 x7+x8-x0 = 0 Edge limits Flow factors x1 <= 12 1 2 x2 <= 9 x3 <= 10 x4 <= 3 10 x5 <= 4 7 12 4 x6 <= 10 3 4 6 5 x7 <= 7 3 x8 <= 13 9 13 end 10 Example3: Max-Flow Min-Cut ECE 665 - LP Duality

Slide 8

Primal Problem - Solution X3=7 X1=10 X7=7 X4=3 X0=19 X2=9 X8=12 X5=0 LP OPTIMUM FOUND AT STEP 3 min cut X6=9 OBJECTIVE FUNCTION VALUE 1) 19.000000 VARIABLE VALUE REDUCED COST 1 2 X0 19.000000 0.000000 X1 10.000000 0.000000 X2 9.000000 0.000000 10 7 X3 7.000000 0.000000 12 4 3 5 6 4 X4 3.000000 0.000000 3 X5 0.000000 1.000000 9 13 X6 9.000000 0.000000 10 X7 7.000000 0.000000 X8 12.000000 0.000000 Example3: Max-Flow Min-Cut (2) Saturated edges : x2=9 x4=3 x7=7 Max stream = 19 = min cut of forward immersed eges ECE 665 - LP Duality

Slide 9

Dual Problem - detailing x3 x7 x1 x4 x0 max x0 st x2 x5 x8 z1 - x1-x2+x0 = 0 x6 x1-x3-x4 = 0 Node limitations: double factors z x2-x5-x6 = 0 x3+x5-x7 = 0 x4+x6-x8 = 0 z6 Dual target vector: [ z1,… , z6 , w1,… ,w8 ] x7+x8-x0 = 0 w1 x1 <= 12 1 2 Dual target cost: [ 0, … , 0 , c1, … , c8 ] x2 <= 9 x3 <= 10 Edge imperatives: double factors w x4 <= 3 10 Edge limits ( 12,9,10,3,4,10,7,13 ) x5 <= 4 7 12 4 x6 <= 10 3 4 6 5 x7 <= 7 3 w8 x8 <= 13 9 13 end 10 Example3: Max-Flow Min-Cut (3) Convert primal issue : Dual obj work: F double = 0 z1 +… +0 z2 + 12 w12 +… + 13 w8 ECE 665 - LP Duality

Slide 10

Dual Problem st z1-z6 >= 1 - z1+z2+w1 >= 0 z2 z4 w3 - z1+z3+w2 >= 0 w7 w1 - z2+z4+w3 >= 0 z1 z6 - z2+z5+w4 >= 0 w4 - z3+z4+w5 >= 0 w5 - z3+z5+w6 >= 0 1 2 w2 w8 - z4+z6+w7 >= 0 w6 z5 - z5+z6+w8 >= 0 z3 z = hub factors end w = edge factors 3 4 6 5 Example3: Max-Flow Min-Cut (4) min 12w1 +9w2 +10w3 +3w4 +4w5 +10w6 +7w7 +13w8 ECE 665 - LP Duality

Slide 11

Dual Problem - arrangement z4=1 z2=1 min cut w3=0 w1=0 w7=1 z1=1 z6=0 w4=1 w5=0 OBJECTIVE FUNCTION VALUE S T w2=1 1) 19.000000 w8=0 z3=0 w6=0 z5=0 VARIABLE VALUE REDUCED COST W1 0.000000 2.000000 W2 1.000000 0.000000 1 2 W3 0.000000 3.000000 W4 1.000000 0.000000 W5 0.000000 4.000000 z i = 1 if hub i is in set S 0 in the event that it is in set T W6 0.000000 1.000000 W7 1.000000 0.000000 W8 0.000000 1.000000 3 4 5 6 Z1 1.000000 0.000000 Z6 0.000000 w i = 1 if edge i is in the min-cut 0 generally Z2 1.000000 0.000000 Z3 0.000000 Z4 1.000000 0.000000 Z5 0.000000 Example3: Max-Flow Min-Cut (5) LP OPTIMUM FOUND AT STEP 9 Interpretation of double factors ECE 665 - LP Duality