Mixed-Integer Linear Programming - McMaster University

1 Mixed-Integer Linear Programming (MILP): ModelFormulationBeno t UniversityDepartment of Chemical EngineeringChE 4G03: Optimization in Chemical EngineeringBeno t Chachuat ( McMaster University )MILP: Model Formulation4G031 / 26 Mixed-Integer Linear ProgrammingInteger Programs (IP)An optimization model is anInteger Programifany ofits decisionvariables is discreteIfallvariables are discrete, the model is apure integer programOtherwise, the model is amixed-integer programInteger variables appear inmanyproblems:Trays in a distillation columnNumber of employees (1000 s)Number of parallel chemical reactorsWhether or not to operate boiler#2on MondayScheduling people and equipment totasks over timeCan be solved continuous, thenrounded to nearest integerNot appropriate to solve con-tinuous and round afterBeno t Chachuat ( McMaster University )MILP: Model Formulation4G032 / 26 Mixed-Integer Linear ProgrammingClass Exercise:Give more examples ofinteger decisionsin the field ofChemical Engineering:1 Fluid flow: 2 Heat transfer.

2 3 Mass transfer: 4 Reactor design: Beno t Chachuat ( McMaster University )MILP: Model Formulation4G033 / 26 Mixed-Integer Linear ProgrammingLinear vs. Nonlinear Integer ProgramsAn IP model is aninteger Linear program(ILP) if its (single)objective function andallits constraints are linearOtherwise, it is aninteger nonlinear program(INLP)Standard Mixed-Integer Linear Programming (MILP) Formulation:minx,yz =cTx+ +Ey = bxmin x xmax,y {0,1}nyMixed-Integer Nonlinear Programs (MINLPs) arevery difficultto solveThis is a great motivation for the continued use ofLP methods!

3 Beno t Chachuat ( McMaster University )MILP: Model Formulation4G034 / 26 OutlineModeling MILP requires knowledge and ingenuity We will learn sometypical MILP formulations here:1 Native MILP Formulations Lumpy Linear ProgramsKnapsack ModelsAssignment and Matching ModelsScheduling Models2 Approximations of Nonlinear Models as MILPsSeparable ProgrammingFor additional examples, see Rardin (1998), Chapter 11 Beno t Chachuat ( McMaster University )MILP: Model Formulation4G035 / 26 Lumpy Linear ProgramsOne broad class of lumpy LPs is wheneither/ordecisions are added towhat is otherwise an LP modelExpressingAll-or-NothingRequirement sAll-or-nothing variable requirements of the formxj= 0 xj=ujcan be modeled by substitutingxj ujyj, {0,1}Example:In a blending model, use none or all of a given ingredientminx1,x2,x318x1+ 3x2+ 2x1+x2+ 7x3 1500 x1 600 x2 30x3= 0 x3= 20 Beno t Chachuat ( McMaster University )MILP.

4 Model Formulation4G036 / 26 Lumpy Linear Programs (cont d)Another source of lumpy LP models iswhen the objective involvesfixed charges( , start-up cost) (xj)ujxjcjfjExpressingFixed-ChargeRequir ementsFixed-cost requirements of the form: (xj) = fj+cjxj,ifxj>00,otherwisewith nonnegative fixed chargefj>0 and variablexj uj, can be modeledby substituting (xj) fjyj+cjxj, ujyjandyj {0,1}Beno t Chachuat ( McMaster University )MILP: Model Formulation4G037 / 26 Formulating Models for Fixed-Charged ObjectivesClass Exercise:Consider a fixed-charge objective functionminx1,x2 1(x1) + 2(x2)where 1(x1) = 150 + 7x1,ifx1>00,otherwise 2(x2) = 110 + 9x2,ifx2>00,otherwiseandx1,x2satisfyx1+x 2 80 x1 30 x2 a corresponding MILP t Chachuat ( McMaster University )MILP: Model Formulation4G038 / 26 Lumpy Linear Programs (cont d)Yet another source of lumpy LPmodels is when a decision variable issemi-continuouscjxjujxjcjljExpressingS emi-ContinuousRequirementsSemi-continuou s variables of the form.

5 Xj= 0 lj xj uj, withlj>0can be modeled by introducing2 new continuous variablesxlj,xuj 0,1new binary variableyj {0,1}, and2 additional constraints:xj=ljxlj+ujxuj1 =yj+xlj+xujBeno t Chachuat ( McMaster University )MILP: Model Formulation4G039 / 26 Formulating Models for Semi-Continuous VariablesClass Exercise:Consider the following blending problem, where theingredientx3is a semi-continuous variable:minx1,x2,x318x1+ 3x2+ 2x1+x2+ 7x3 1500 x1 600 x2 30x3= 0 10 x3 20 Formulate a corresponding MILP t Chachuat ( McMaster University )MILP: Model Formulation4G0310 / 26 Knapsack ModelsThe problem is to select a maximumvalue collection of items subject tolimitations on resources consumedKnapsack models are the simplestof all (pure) integer Linear programs(ILPs) element is eitherall inorall outof the selection:yj = 1,if itemjselected0,otherwiseExample:Selectio n of projects subject to limitations on budgetsClass Exercise.

6 Readily available Canadian coins are 1 , 5 , 10 and 25 .Formulate an ILP model to minimize the number of coins neededtoprovide change amount forq .Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0311 / 26 Knapsack Models (cont d)1 Dependenceof choicejon choiceican be enforced oncorresponding binary variables by adding constraints of the form:2 Mutually exclusivenessconditions allowingat most oneof a set ofchoicesJcan be enforced by adding constraints of the form:Similarly,at mostpof a set of choicesJcan be enforced as:3 Constraints can also enforce selection ofexactlyporat leastpof aset of choicesJBeno t Chachuat ( McMaster University )MILP.

7 Model Formulation4G0312 / 26 Formulating ILP ModelsClass Exercise:The Department of Chemical Engineering at McMaster isacquiring optimization software for use in ChE 4 codes available and the types of algorithms they provide areindicated by s in the following table:AlgorithmCode,jType1 2 3 4LP IP NLP Cost3 4 6 141 Formulate a MILP model to acquire a minimum cost collection ofcodes providing LP, IP and NLP capability2 Formulate a MILP model to acquire a minimum cost collection ofcodes with exactly one providing LP, one providing IP, and oneproviding NLP capabilityBeno t Chachuat ( McMaster University )MILP.

8 Model Formulation4G0313 / 26 Assignment ModelsThe issue here is optimal matchingor pairing of objects of two distincttypesIt is standard to model allassignment forms with the decisionvariables:yi,j = 1,ifiof the 1st set is matched withjof the 2nd0,otherwiseSetISetJExamples:Assign sales personnel to customers, jobs to machine, constraintsforcing everyiand/or everyjto be assignedare of the form:Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0314 / 26 Assignment Models (cont d)Generalized assignment constraintsencompass cases where allocationofitojrequires fixed spacesi,jwithinjcapacitybj: Linear assignment modelsminimize/maximize a Linear objectivefunction of the form:Xi IXj Jci,jyi,jwhereci,jis the cost of assigningitojClass Exercise:Itemsi= 1.

9 ,100 of volumeciare being stored in anautomated warehouse. Storage locationj= 1, .. ,20 are at a distancedjfrom the input/output station, and all have a MILP model to store all items at minimum total travel t Chachuat ( McMaster University )MILP: Model Formulation4G0315 / 26 Matching ModelsUnlike assignment models, matchingmodels eliminate the distinctionbetween the setsDecision variables of matchingmodels typically are:SetIyi,i = 1,ifiis paired withi 0,otherwisewherei >i, by convention, to avoid double countingMatching constraintsforcing somei Ito pair with and only withsome otheri Iare of the form.

10 Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0316 / 26 Matching Models (cont d)Class Exercise:The instructor of ChE 4G03 wants to assign his studentsto 2-person teams for a graded tutorial. each studentshas scored his/herpreferenceps,s for working with each other students .1 Formulate a MILP model to form teams in a way that maximizestotal t Chachuat ( McMaster University )MILP: Model Formulation4G0317 / 26 Process Scheduling ModelsSchedulingis the allocation of resources over timeSingle-process schedulingproblems seek anoptimal sequenceinwhich to complete a given collection of tasks on a single process thatcan accommodateonly one job at a time r1r2r3d1d2d3p1p2p3 Feed 1 Feed 2 Feed 3 Product 1 Product 2 Product 3 TimeTimeTimeTypical Data.