ELEC 7770 Advanced VLSI Design Spring 2008 Linear Programming – A Mathematical Optimization Technique Vishwani D. Agrawal James J. Danaher Professor ECE Department, Auburn University, Auburn, AL 36849 [email protected] http://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr08/course.html Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 1 What is Linear Programming Linear programming (LP) is a mathematical method for selecting the best solution from the available solutions of a problem. Method: State the problem and define variables whose values will be determined. Develop a linear programming model: Write the problem as an optimization formula (a linear expression to be minimized or maximized) Write a set of linear constraints An available LP solver (computer program) gives the values of variables. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 2 Types of LPs LP – all variables are real. ILP – all variables are integers. MILP – some variables are integers, others are real. A reference: S. I. Gass, An Illustrated Guide to Linear Programming, New York: Dover, 1990. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 3 A Single-Variable Problem Consider variable x Problem: find the maximum value of x subject to constraint, 0 ≤ x ≤ 15. Solution: x = 15. Constraint satisfied 0 15 x Solution x = 15 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 4 Single Variable Problem (Cont.) Consider more complex constraints: Maximize x, subject to following constraints: 0 x≥0 5x ≤ 75 6x ≤ 30 x ≤ 10 (1) (2) (3) (4) 5 10 (3) 15 x (2) (1) (4) All constraints satisfied Solution, x = 5 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 5 A Two-Variable Problem Manufacture of chairs and tables: Resources available: Material: 400 boards of wood Labor: 450 man-hours Profit: Chair: $45 Table: $80 Resources needed: Chair 5 boards of wood 10 man-hours Table 20 boards of wood 15 man-hours Problem: How many chairs and how many tables should be manufactured to maximize the total profit? Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 6 Formulating Two-Variable Problem Manufacture x1 chairs and x2 tables to maximize profit: P = 45x1 + 80x2 dollars Subject to given resource constraints: 400 boards of wood, 5x1 + 20x2 ≤ 400 450 man-hours of labor, 10x1 + 15x2 ≤ 450 x1 ≥ 0 x2 ≥ 0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) (1) (2) (3) (4) 7 Solution: Two-Variable Problem 40 Tables, x2 30 Best solution: 24 chairs, 14 tables Profit = 45×24 + 80×14 = 2200 dollars (1) 20 (24, 14) 10 (3) (4) 0 0 10 20 30 40 50 60 Chairs, x1 (2) 70 80 90 increasing decresing Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 8 Change Profit of Chair to $64/Unit Manufacture x1 chairs and x2 tables to maximize profit: P = 64x1 + 80x2 dollars Subject to given resource constraints: 400 boards of wood, 5x1 + 20x2 ≤ 400 450 man-hours of labor, 10x1 + 15x2 ≤ 450 x1 ≥ 0 x2 ≥ 0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) (1) (2) (3) (4) 9 Solution: $64 Profit/Chair 40 Tables, x2 30 Best solution: 45 chairs, 0 tables Profit = 64×45 + 80×0 = 2880 dollars (1) 20 (24, 14) 10 (3) (4) 0 0 Spring 08, Feb 14 10 20 30 40 50 Chairs, x1 ELEC 7770: Advanced VLSI Design (Agrawal) 60 (2) 70 80 90 increasing decresing 10 A Dual Problem Explore an alternative. Questions: Should we make tables and chairs? Or, auction off the available resources? To answer this question we need to know: What is the minimum price for the resources that will provide us with same amount of revenue as the profits from tables and chairs? This is the dual of the original problem. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 11 Formulating the Dual Problem Revenue received by selling off resources: For each board, w1 For each man-hour, w2 Minimize 400w1 + 450w2 Subject to constraints: 5w1 + 10w2 ≥ 45 20w1 + 15w2 ≥ 80 w1 ≥0 w2 ≥0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 12 The Duality Theorem If the primal has a finite optimal solution, so does the dual, and the optimum values of the objective functions are equal. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 13 Primal-Dual Problems Primal problem Dual Problem Variables: Variables: Fixed resources Maximize profit Fixed profit Minimize value x1 (number of chairs) w1 ($ value/board of wood) x2 (number of tables) w2 ($ value/man-hour) Maximize profit 45x1+80x2 Minimize value 400w1+450w2 Subject to: Subject to: 5x1 + 20x2 ≤ 400 5w1 + 10w2 ≥ 45 10x1 + 15x2 ≤ 450 20w1 + 15w2 ≥ 80 x1 ≥0 w1 ≥0 x2 ≥0 w2 ≥0 Solution: Solution: x1 = 24 chairs, x2 = 14 tables w1 = $1, w2 = $4 Profit = $2200 value = $2200 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 14 LP for n Variables n minimize Σ cj xj Objective function j =1 n subject to Σ aij xj ≤ bi, i = 1, 2, . . ., m = di, i = 1, 2, . . ., p j =1 n Σ cij xj j =1 Variables: xj Constants: cj, aij, bi, cij, di Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 15 Algorithms for Solving LP Simplex method G. B. Dantzig, Linear Programming and Extension, Princeton, New Jersey, Princeton University Press, 1963. Ellipsoid method L. G. Khachiyan, “A Polynomial Algorithm for Linear Programming,” Soviet Math. Dokl., vol. 20, pp. 191-194, 1984. Interior-point method N. K. Karmarkar, “A New Polynomial-Time Algorithm for Linear Programming,” Combinatorica, vol. 4, pp. 373-395, 1984. Course website of Prof. Lieven Vandenberghe (UCLA), http://www.ee.ucla.edu/ee236a/ee236a.html Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 16 Basic Ideas of Solution methods Extreme points Constraints Extreme points Objective function Simplex: search on extreme points. Spring 08, Feb 14 Constraints Objective function Interior-point methods: Successively iterate with interior spaces of analytic convex boundaries. ELEC 7770: Advanced VLSI Design (Agrawal) 17 Integer Linear Programming (ILP) Variables are integers. Complexity is exponential – higher than LP. LP relaxation Convert all variables to real, preserve ranges. LP solution provides guidance. Rounding LP solution can provide a non-optimal solution. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 18 Solving TSP: Five Cities Distances (dij) in miles (symmetric TSP, general TSP is asymmetric) City j=1 j=2 j=3 j=4 j=5 i=1 0 18 10 12 27 i=2 18 0 5 12 20 i=3 10 5 0 15 19 i=4 12 12 15 0 6 i=5 27 20 19 6 0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 19 Search Space: No. of Tours Asymmetric TSP tours Five-city problem: 4 × 3 × 2 × 1 = 24 tours Nine-city problem: 362,880 tours 14-city problem: 87,178,291,200 tours 50-city problem: 49! = 6.08×1062 tours Time for enumerative search assuming 1 μs per tour evaluation = 1.93×1055 years Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 20 A Greedy Heuristic Solution Tour length = 10 + 5 + 12 + 6 + 27 = 60 miles (non-optimal) City j=1 j=2 j=3 j=4 j=5 i=1 (start) 0 18 10 12 27 i=2 18 0 5 12 20 i=3 10 5 0 15 19 i=4 12 12 15 0 6 i=5 27 20 19 6 0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 21 ILP Variables, Constants and Constraints x14 ε [0,1] d14 = 12 4 5 x15 ε [0,1] d15 = 27 x12 ε [0,1] d12 = 18 1 Integer variables: xij = 1, travel i to j xij = 0, do not travel i to j x13 ε [0,1] d13 = 10 2 Real variables: dij = distance from i to j 3 x12 + x13 + x14 + x15 = 2 four other similar equations Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 22 Objective Function and ILP Solution 5 i-1 Minimize ∑ ∑ xij × dij i=1 j=1 ∑ xij = 2 j≠i Spring 08, Feb 14 for all i xij j=1 2 3 4 5 i=1 0 0 1 0 0 2 1 0 0 0 0 3 0 1 0 0 0 4 0 0 0 0 1 5 0 0 0 1 0 ELEC 7770: Advanced VLSI Design (Agrawal) 23 ILP Solution d54 = 6 4 5 d45 = 6 1 d21 = 18 d13 = 10 2 3 d32 = 5 Total length = 45 but not a single tour Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 24 Additional Constraints for Single Tour Following constraints prevent split tours. For any subset S of cities, the tour must enter and exit that subset: ∑ xij ≥ 2 for all S, |S| < 5 iεS jεS Remaining set At least two arrows must cross this boundary. Any subset Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 25 ILP Solution d41 = 12 4 d54 = 6 5 1 d25 = 20 d13 = 10 2 3 d32 = 5 Total length = 53 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 26 Characteristics of ILP Worst-case complexity is exponential in number of variables. Linear programming (LP) relaxation, where integer variables are treated as real, gives a lower bound on the objective function. Recursive rounding of relaxed LP solution to nearest integers gives an approximate solution to the ILP problem. K. R. Kantipudi and V. D. Agrawal, “A Reduced Complexity Algorithm for Minimizing N-Detect Tests,” Proc. 20th International Conf. VLSI Design, January 2007, pp. 492-497. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 27 Why ILP Solution is Exponential? LP solution found in polynomial time (bound on ILP solution) Second variable Must try all 2n roundoff points Constraints First variable Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) Objective (maximize) 28 ILP Example: Test Minimization A combinational circuit has n test vectors that detect m faults. Each test detects a subset of faults. Find the smallest subset of test vectors that detects all m faults. ILP model: Assign an integer variable ti ε [0,1] to ith test vector such that ti = 1, if we select ti, otherwise ti= 0. Define an integer constant fij ε [0,1] such that fij = 1, if ith vector detects jth fault, otherwise fij = 0. Values of constants fij are determined by fault simulation. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 29 Test Minimization by ILP n minimize Σ ti Objective function i=1 n subject to Σ fij ti ≥ 1, j = 1, 2, . . ., m i=1 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 30 3V3F: A 3-Vector 3-Fault Example Test vector i fij i=1 i=2 i=3 Variables: t1, t2, t3 ε [0,1] Fault j Minimize t1 + t2 + t3 j=1 1 1 0 j=2 0 1 1 Subject to: t1 + t2 ≥ 1 t2 + t3 ≥ 1 j=3 Spring 08, Feb 14 1 0 1 ELEC 7770: Advanced VLSI Design (Agrawal) t1 + t3 ≥ 1 31 3V3F: Solution Space t3 ILP solutions (optimum) 1 Non-optimum solution 1st LP solution (0.5, 0.5, 0.5) Rounding and 2nd ILP solution (1.0, 0.5, 0.5) t2 1 Rounding and 3rd LP solution (1.0, 1.0, 0.0) 1 t1 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 32 3V3F: LP Relaxation and Rounding ILP – Variables: t1, t2, t3 ε [0,1] LP relaxation: t1, t2, t3 ε (0.0, 1.0) Minimize t1 + t2 + t3 Solution: t1 = t2 = t3 = 0.5 Subject to: Recursive rounding: t1 + t2 ≥ 1 t2 + t3 ≥ 1 t1 + t3 ≥ 1 (1) round one variable, t1 = 1.0 Two-variable LP problem: Minimize t2 + t3 subject to t2 + t3 ≥ 1.0 LP solution t2 = t3 = 0.5 (2) round a variable, t2 = 1.0 ILP constraints are satisfied solution is t1 = 1, t2 = 1, t3 = 0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 33 Recursive Rounding Algorithm 1. Obtain a relaxed LP solution. Stop if each variable in the solution is an integer. 2. Round the variable closest to an integer. 3. Remove any constraints that are now unconditionally satisfied. 4. Go to step 1. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 34 Recursive Rounding ILP has exponential complexity. Recursive rounding: ILP is transformed into k LPs with progressively reducing number of variables. A solution that satisfies all constraints is guaranteed; this solution is often close to optimal. Number of LPs, k, is the size of the final solution, i.e., the number of non-zero variables in the test minimization problem. Recursive rounding complexity is k × O(np), where k ≤ n, n is number of variables. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 35 Four-Bit ALU Circuit ILP Recursive rounding Initial vectors Vectors CPU s Vectors CPU s 285 14 0.65 14 0.42 400 13 1.07 13 1.00 500 12 4.38 13 3.00 1,000 12 4.17 12 3.00 5,000 12 12.95 12 9.00 10,000 12 34.61 12 17.0 16,384 12 87.47 12 37.0 Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 36 ILP vs. Recursive Rounding 100 ILP CPU s 75 Recursive Rounding 50 25 0 0 Spring 08, Feb 14 5,000 10,000 ELEC 7770: Advanced VLSI Design (Agrawal) 15,000 Vectors 37 N-Detect Tests (N = 5) Relaxed LP/Recur. rounding ILP (exact) Circuit Unoptimized vectors c432 608 196.38 197 1.0 197 1.0 c499 379 260.00 260 1.2 260 2.3 c880 1,023 125.97 128 14.0 127 881.8 c1355 755 420.00 420 3.2 420 4.4 c1908 1,055 543.00 543 4.6 543 6.9 c2670 959 477.00 477 4.7 477 7.2 c3540 1,971 467.25 477 72.0 471 20008.5 c5315 1,079 374.33 377 18.0 376 40.7 c6288 243 52.52 57 39.0 57 34740.0 c7552 2,165 841.00 841 52.0 841 114.3 Spring 08, Feb 14 Lower bound Min. Min. CPU s vectors vectors ELEC 7770: Advanced VLSI Design (Agrawal) CPU s 38 Finding LP/ILP Solvers R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, South San Francisco, California: Scientific Press, 1993. Several of programs described in this book are available to Auburn users. B. R. Hunt, R. L. Lipsman, J. M. Rosenberg, K. R. Coombes, J. E. Osborn and G. J. Stuck, A Guide to MATLAB for Beginners and Experienced Users, Cambridge University Press, 2006. Search the web. Many programs with small number of variables can be downloaded free. Spring 08, Feb 14 ELEC 7770: Advanced VLSI Design (Agrawal) 39

Descargar
# ELEC7770 Advanced VLSI Design Spring 2007