ELEC 7770 Advanced VLSI Design Spring 2008 Linear Programming – A Mathematical Optimization TechniqueWhat is Linear ProgrammingTypes of LPsA Single-Variable ProblemSingle Variable Problem (Cont.)A Two-Variable ProblemFormulating Two-Variable ProblemSolution: Two-Variable ProblemChange Profit of Chair to $64/UnitSolution: $64 Profit/ChairA Dual ProblemFormulating the Dual ProblemThe Duality TheoremPrimal-Dual ProblemsLP for n VariablesAlgorithms for Solving LPBasic Ideas of Solution methodsInteger Linear Programming (ILP)Solving TSP: Five CitiesSearch Space: No. of ToursA Greedy Heuristic SolutionILP Variables, Constants and ConstraintsObjective Function and ILP SolutionILP SolutionAdditional Constraints for Single TourSlide 26Characteristics of ILPWhy ILP Solution is Exponential?ILP Example: Test MinimizationTest Minimization by ILP3V3F: A 3-Vector 3-Fault Example3V3F: Solution Space3V3F: LP Relaxation and RoundingRecursive Rounding AlgorithmRecursive RoundingFour-Bit ALU CircuitILP vs. Recursive RoundingN-Detect Tests (N = 5)Finding LP/ILP SolversSpring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)11ELEC 7770ELEC 7770Advanced VLSI DesignAdvanced VLSI DesignSpring 2008Spring 2008 Linear Programming – A Mathematical Linear Programming – A Mathematical Optimization TechniqueOptimization TechniqueVishwani D. AgrawalVishwani D. AgrawalJames J. Danaher ProfessorJames J. Danaher ProfessorECE Department, Auburn University, Auburn, AL 36849ECE Department, Auburn University, Auburn, AL [email protected]@eng.auburn.eduhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr08/course.htmlhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr08/course.htmlSpring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)22What is Linear ProgrammingWhat 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 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)33Types of LPsTypes 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 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)44A Single-Variable ProblemA Single-Variable ProblemConsider variable xProblem: find the maximum value of x subject to constraint, 0 ≤ x ≤ 15.Solution: x = 15.015Constraint satisfiedxSolution x = 15Spring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)55Single Variable Problem (Cont.)Single Variable Problem (Cont.)Consider more complex constraints:Maximize x, subject to following constraints: x ≥ 0 (1) 5x ≤ 75 (2) 6x ≤ 30 (3) x ≤ 10 (4)0 5 10 15x(1)(2)(3)(4)All constraints satisfiedSolution, x = 5Spring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)66A Two-Variable ProblemA 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 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)77Formulating Two-Variable ProblemFormulating 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 (1)450 man-hours of labor, 10x1 + 15x2 ≤ 450 (2) x1 ≥ 0 (3) x2 ≥ 0 (4)Spring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)88Solution: Two-Variable ProblemSolution: Two-Variable ProblemChairs, x1Tables, x2(1)(2)0 10 20 30 40 50 60 70 80 90403020100(24, 14)Profit increasing decresingP = 2200P = 0Best solution: 24 chairs, 14 tablesProfit = 45×24 + 80×14 = 2200 dollars(3)(4)Material constraintMan-power constraintSpring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)99Change Profit of Chair to $64/UnitChange 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 (1)450 man-hours of labor, 10x1 + 15x2 ≤ 450 (2) x1 ≥ 0 (3) x2 ≥ 0 (4)Spring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1010Solution: $64 Profit/ChairSolution: $64 Profit/ChairChairs, x1Tables, x2(1)(2)Profit increasing decresingP = 2880P = 0Best solution: 45 chairs, 0 tablesProfit = 64×45 + 80×0 = 2880 dollars0 10 20 30 40 50 60 70 80 90(24, 14)403020100(3)(4)Material constraintMan-power constraintSpring 08, Feb 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1111A Dual ProblemA 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 14Spring 08, Feb 14ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1212Formulating the Dual ProblemFormulating the Dual ProblemRevenue received by selling off resources:For each board,