Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14max 15xa + 20xb + 18xc + 13xd + 12xe st 18xa + 10xb + 21xc + 11xd + 11xe <= 50 end int xa int xb int xc int xd int xeInteger ProgrammingKey characteristic of an Integer Program (IP) or Mixed IntegerLinear Program (MILP): One or more of the decision variable must be integer.In some cases a problem that requires an Integer solution can besolved as a Linear program.When?When rounding off a real number to an integer number has no“effect” on your solution.Integer Programming! Homework 7-2)!! x1 - model 1 ovens! x2 - model 2 ovens!max 12 x1 + 8.5 x2st x1 <= 300 x2 <= 100 2.3 x1 + 1.6 x2 <= 500endfree x1 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 2623.913 VARIABLE VALUE REDUCED COST X1 147.826080 0.000000 X2 100.000000 0.000000You cannot manufacture 147.82608 model 1 ovens. Simplyrounding off to 147 model 1 ovens is an acceptable solution.Integer Programming - ExampleClassic Knapsack Problem:You want to maximize the value of items you can pack into a single suitcase (or knapsack). However, you are limited to a weight of 50 lbs. xi = 0 if not chosen = 1 if put in knapsackItem Value ($) Weight (lbs)A 15 18B 20 10C 18 21D 13 11E 12 1110,,,,501111211018..1213182015orxxxxxxxxxxtsxxxxxMaxEDCBAEDCBAEDCBAInteger Programming - ExampleClassic Knapsack Problem: If integer constraint relaxed -1,,,,0,,,,501111211018..1213182015EDCBAEDCBAEDCBAEDCBAxxxxxxxxxxxxxxxtsxxxxxMax LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1) 60.42857 VARIABLE VALUE REDUCED COST XA 0.000000 0.428571 XB 1.000000 0.000000 XC 0.857143 0.000000 XD 1.000000 0.000000 XE 1.000000 0.000000Integer Programming - ExampleClassic Knapsack Problem: With integer constraint -10,,,,501111211018..1213182015orxxxxxxxxxxtsxxxxxMaxEDCBAEDCBAEDCBAOBJECTIVE FUNCTION VALUE 1) 60.00000 VARIABLE VALUE REDUCED COST XA 1.000000 -15.000000 XB 1.000000 -20.000000 XC 0.000000 -18.000000 XD 1.000000 -13.000000 XE 1.000000 -12.000000Integer Programming - ExampleClassic Knapsack Problem:How would you modify this formulation if you realized that you could not select item A without selecting item D?Add constraint: xA <= xD How would you modify if you could select at most 3 items?Add constraint: xA + xB + xC + xD + xE <= 3 10,,,,501111211018..1213182015orxxxxxxxxxxtsxxxxxMaxEDCBAEDCBAEDCBAInteger Programming - ExampleOther examples of formulating problems: see handoutsSolving IPs and MIPsApproaches:Solve to Optimality• Branch and Bound – lesson 6• Implicit Enumeration – lesson 6• Cutting Plane Method – lesson 7Good and sometimes Optimal Solutions• Heuristics (problem specific) – lesson 7• Meta-Heuristics – lesson 8 & 9Solving IPs – Branch and BoundSee Branch and Bound On-Line ExampleSolving IPs – Implicit EnumerationSimilar to Binary IP Branch and BoundGeneral Idea: Fixed variables – those for which a value has been fixed.Free Variable – variables which whose values are unspecified.Completion – when all variables have been assigned a value.Upper Bound (minimization problem) – Best feasible solution found thus far.Lower Bound (minimization problem) – Optimal solution for a relaxed problem at a given node (e.g. some variables fixed, some free).Solving IPs – Implicit EnumerationExample Sequencing Problem:Sequence a series of jobs to minimize the maximum lateness (Lmax) for a set of jobs to be processed on a single machine. Each job belongs to a given part family. Jobs are denoted with an (i,j) subscript indicating the jth job from family i. Family (i) Job (j)Processing Time (pij)Due Date (dij)1 1 3 51 2 2 72 1 4 62 2 3 93 1 4 43 2 2 10Lmax = Max{Lij}Lij = Cij – dijCij is the completiontime of job ij.Solving IPs – Implicit EnumerationExample Sequencing Problem cont:Also, when starting the processing of a new family, a family setup time is incurred. All jobs are ready to be scheduled at time 0.Family (i)Setup TIme12223 2Optimality Condition: All jobs within a family must be sequenced in earliest due date order (EDD).Solving IPs – Implicit EnumerationStep 1 – Find an initial Upper boundWhat is a good upper bound?Step 2 – Perform implicit enumeration.Start building partial sequences and fathom nodes if lower bound for partial sequence exceeds upper bound. Update upper bound whenever a better value is found for a completion.What is a good lower bounding scheme?Solving IPs – Implicit EnumerationInsert Hand Slides For Example ProblemSolving IPs – Using LindoStatements – INT and GININT – forces binary solution (1 or 0) for decision variable.GIN – forces non-negative integer (0,1,2,3,4…) for decision variable.Knapsack problem:max 15xa + 20xb + 18xc + 13xd + 12xest 18xa + 10xb + 21xc + 11xd + 11xe <= 50endint xaint xbint xcint xdint