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: 3 Mass transfer: 4 Reactor design: Beno t Chachuat ( McMaster University )MILP: Model Formulation4G033 / 26 Mixed-Integer Linear ProgrammingLinear vs.

2 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!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.

3 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: 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: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.

4 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: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: 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.

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

6 ,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: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.

7 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:pj = estimated process time for taskjrj = release time at which taskjbecomes available for processingdj = due date by which taskjshould be completedBeno t Chachuat ( McMaster University )MILP: Model Formulation4G0318 / 26 Process Scheduling Models (cont d) x1x2x3r1r2r3d1d2d3p1p2p3 Feed 1 Feed 2 Feed 3 Product 1 Product 2 Product 3 TimeTimeTimeTime Decision Variables and Related Constraints:xj = start time for taskjresource availability:xj rj, jHandling of Due Dates:Due dates are usually handled asgoalsto be reflected in the objectivefunction rather than explicit constraintsThis avoids the situation where there is no feasible schedule thatmeets all due datesDates thatmustbe met are termeddeadlinesto distinguish and canbe easily enforced as:xj+pj dj, jBeno t Chachuat ( McMaster University )MILP: Model Formulation4G0319 / 26 Process Scheduling Models (cont d) x1x2x3r1r2r3d1d2d3p1p2p3 Feed 1 Feed 2 Feed 3 Product 1 Product 2 Product 3 TimeTimeTimeObjective Functions Often minimizes one of the following:Max.

8 Completion time (makespan)max{xj+pj:j= 1, .. ,n}Mean completion time1nnXj=1(xj+pj)Max. latenessmax{xj+pj dj:j= 1, .. ,n}Mean lateness1nnXj=1(xj+pj dj)Max. tardinessmax{0,max{xj+pj dj:j= 1, .. ,n}}Mean tardiness1nnXj=1max{0,xj+pj dj}Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0320 / 26 Process Scheduling Models (cont d)Class Exercise:The following table shows the process time, release times,due dates, and scheduled starts for three jobs. Compute the correspondingvalue of each of the six objective functions listed 1 Job 2 Job 3 Process time,pi1569 Release time,ri5100 Due Date,di202536 Scheduled start,xi92401 Completiontimes (xi+pi) are:9 + 15 = 24,24 + 6 = 30,0 + 9 = 9 Maximum completion time is max{24,30,9}= 30 Mean completion time is13(24 + 30 + 9) = 212 Latenessof the three jobs (xj+pj dj) is:9 + 15 20 = 4,24 + 6 25 = 5,0 + 9 36 = 27 Maximum lateness is max{4,5, 27}= 5 Mean completion time is13(4 + 5 27) = 6 Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0321 / 26 Process Scheduling Models (cont d) x1x2x3r1r2r3d1d2d3p1p2p3 Feed 1 Feed 2 Feed 3 Product 1 Product 2 Product 3 TimeTimeTimeConflict Constraints:xj+pj xj xj +pj xj, j,j = 1.

9 ,n,j6=j Reformulation Using Disjunctive Variables:yj,j = 1,ifjbinding comes beforej 0,ifj binding comes beforejIllustrative Example:y1,2=y1,3= 1,y2,3= 0 Beno t Chachuat ( McMaster University )MILP: Model Formulation4G0322 / 26 Process Scheduling Models (cont d) x1x2x3r1r2r3d1d2d3p1p2p3 Feed 1 Feed 2 Feed 3 Product 1 Product 2 Product 3 TimeTimeTimeBig-M MethodConflicts between tasksjandj can be prevented withdisjunctiveconstraint pairs:xj+pj xj +M(1 yj,j )xj +pj xj+Myj,j whereMis alarge positive constant( , the max. makespan)Class Exercise:Formulateinteger Linear constraintsfor feasible scheduleson a single process with 3 tasks having process times 14, 3, and t Chachuat ( McMaster University )MILP: Model Formulation4G0323 / 26 Separable ProgrammingConsider the following mathematical program:minxz =nXj=1fj(xj) =f1(x1) + +fn(xn) ,jxj bi,i= 1, .. ,mxj 0,j= 1.

10 ,n The objective consists ofnnonlinear,separabletermsfj(xj), each afunction of asinglevariable only Themconstraints are linearWheneachfjis convex or concave on the feasible region, theseparable program can beapproximated with an LPOtherwise, the separable program can beapproximated with anMILPBeno t Chachuat ( McMaster University )MILP: Model Formulation4G0324 / 26 Approximating General Separable Programs as MILPsPiecewise affine approximation:(Njintervals)c2=f(2)j f(1)jx(2)j x(1)jfj(xj)f(0)jf(1)jf(2)jf(3)jxjx(0)jx( 1)jx(2)jx(3)j0 j,2 x(2)j x(1)jDefine:c(k)j=f(k)j f(k 1)jx(k)j x(k 1)j0 j,k x(k)j x(k 1)jSubstituteeachvariablexjand functionfjby:xj x(0)j+NjXk=1 j,kfj(xj) f(0)j+NjXk=1c(k)j j,kBeno t Chachuat ( McMaster University )MILP: Model Formulation4G0325 / 26 Approximating General Separable Programs as MILPsPiecewise affine approximation:(Njintervals)c2=f(2)j f(1)jx(2)j x(1)jfj(xj)f(0)jf(1)jf(2)jf(3)jxjx(0)jx( 1)jx(2)jx(3)j0 j,2 x(2)j x(1)jDisjunctive Variables:yj,k = 0,if j,k= 01,if j,k>0 Disjunctive Constraints: j,k hx(k)j x(k 1)jiyj,k, k= 1.