Slide 1Slide 2Slide 3Slide 4Slide 5max 15xa + 20xb + 18xc + 13xd + 12xe st 18xa + 10xb + 21xc + 11xd + 11xe <= 50 end int xa int xb int xc int xd int xeSolving 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 TIme1 22 23 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