Script
LINEAR PROGRAMMING – Integer Models
Slide 1
· Welcome back.
· In this module we’ll look at linear programming models whose solutions are required to be integers.
Slide 2
· Frequently, whether or not the solution turns out be integers is not important – things are looked at over a longer term basis and if, for example, the optimal solution says to produce 8 2/7 units of an item every week, this simply means we will produce 58 of the item over a 7 week period. But sometimes there are variables that must turn out to be integers.
· If we are dealing with a one time production process
· Fractional values here make no sense, there will be no work in progress at the end of operations.
· But it would be a different story if it were an ongoing process where fractional values would be treated as work in progress over the long haul.
· If the decision variables represented houses or planes or personnel that must be scheduled, again fractional values would make no sense.
· Some problems even require some or all of the variables to be binary
· Meaning they must assume values of only 0 or 1
· Such as – do we build the plant or not with 1 meaning YES and 0 meaning NO.
Slide 3
· We can classify problems based on the extent of the integrality required. The solution technique used to solve integer problems depends on these problem classifications.
· An all-integer linear program, AILP, is one in which
· All the decision variables are required to be integers.
· A mixed integer linear programming model (MILP)
· Is one in which some, but not all of the decision variables are required to be integers.
· And a binary integer linear programming model (a BILP)
· Is one in which the variables are restricted to either 0 or 1
Slide 4
· Let’s look at an example in two variables where both are required to be integers.
· Boxcar Burger is looking to expand to the Washington D.C. area and it will build some restaurants in the suburbs and some downtown.
· Suburban locations
· Are expected to net a profit of $12,000 per day, each requires a $2,000,000 investment and each restaurant requires 3 managers.
· Downtown restaurants
· Are expected to net a profit of $20,000 per day, each requires a $6,000,000 investment and each restaurant requires only 1 manager.
· The expansion plan includes
· A $27 million dollar budget
· A requirement for at least two downtown restaurants
· And a budget for 19 managerial positions.
Slide 5
· As usual webegin by defining the decision variables
· Here they are the number of suburban area restaurants built and
· the number of downtown restaurants built.
· The objective is maximize the total daily profit
· This can be expressed in 1000’s of dollars as
· Max 12X1 + 20 X2
Slide 6
· The restrictions are
· That no more than $27 million can be invested in the restaurants
· The total amount invested in restaurants
· Cannot exceed
· 27 million dollars
· The total amount that will be invested is
· 2 million X1 plus 6 million X2
· is less than or equal to
· 27 million dollars – so written in millions we have 2X1 + 6X2 is less than or equal to 27
· They must build at least 2 downtown restaurants
· The number of downtown restaurants built
· Must be at least
· 2
· The symbol for the number of downtown restaurants built is
· X2
· It must be greater than or equal to
· 2
· The number of managerial positions cannot exceed 19
· The number of managerial positions used
· Cannot exceed
· 19
· The number of managerial positions used per suburban store is 3 and per downtown store is 1 so we have
· 3X1 + 1X2
· Is less than or equal to
· 19
Slide 7
· Thus the complete model is to
· Maximize 12000X1 plus 20000X2
· Subject to
· 2X1 + 6X2 is less than or equal to 27 (in millions of dollars), X2 is greater than or equal to 2, and 3X1 + 1X2 is less than or equal to 19
· We have the usual non-negativity constraints
· But this time we have constraints requiring that the variables turn out to be integers.
Slide 8
· Let’s ignore for a second the integer constraints and graphically solve this problem as a linear program. Here is the first quadrant where the X’s are greater than or equal to 0.
· The investment constraint is that 2X1 + 6X2 is less than or equal to 27
· The constraint that says they must build at least two downtown restaurants is X2 is greater than or equal to 2.
· And the constraint on managerial positions is 3X1 + 1X2 is less than or equal to 19.
· The shaded area is then
· the feasible region for the linear programming version of this model.
· If we solved this model as a linear program, we would impose the objective function Max 12 X1 plus 20 X2 which gives the daily profits in thousands of dollars and move the line out until it touches the last point of the feasible region.
· This last point is X1 = 5 7/16 and X2 = 2 11/16, with an optimal objective function of 119 (that’s 119 thousand dollars). We may be tempted to simply round this solution, figuring that will give us the optimal solution. Now there are many ways to round – we can round off, round up, or round down.
· When we round off we get X1 = 5, X2 = 3, which is not feasible.
· Neither is the rounded up point of X1 = 6, X2 = 3.
· When we round down we get X1 = 5 and X2 = 2 which is a feasible point with an objective function value of 100 (that’s 100 thousand dollars).
Slide 9
· But now let’s look at the integer model. Clearly all the constraints of the linear model must be satisfied – that is the shaded area,
· but also we have the constraints that the variables must be integer. So that means that only the points in the shaded area that have integer values are feasible for the integer model.
· Now when impose the objective function Maximize 12X1 + 20 X2,
· the last feasible integer point touched is X1 = 4, X2 =3, which gives an objective function value of 108 Thousand dollars (and 8% better value than the point we got by rounding. And it is interesting to note that there is no rounding policy that would have given this value – this is not a rounded version of the optimal linear programming optimal solution.
Slide 10
· Why shouldn’t we round the optimal linear programming solution? Three things may happen when we do this.
· We may get lucky and the rounded solution actually is the optimal integer solution
· None of our rounded values did this in our example, however.
· Rounding may give you an infeasible point
· Both rounding up and rounding off did in our example
· Or we may get a feasible solution that is not optimal
· As we did when we rounded down the optimal linear programming solution to our model
· Many times, but not always, when a solution is rounded and it gives an integer value, the result is at least a pretty good solution if it is not the optimal one. As pointed out in our example the feasible rounded point 5,2 gave a value that was 8% less than the optimal integer point!
Slide 11
· We are not going to get into many of the intricacies of integer models, but we will point out a few things.
· The solution time to solve an integer model is much longer than the solution time to solve the same model without the integer constraints.
· This is because the solution procedure solves many, sometimes millions, of linear programs, in an attempt to the corresponding integer model
· For maximization problems the optimal solution to the integer model will be less, or at least not greater than, than the corresponding model without the integer constraints.
· That is because more constraints – the integer constraints, have been added to the model.
· There is no sensitivity analyses printed by software programs including Excel.
· This is because the feasible region is not a continuous area any more but rather a lattice structure, so changes are not smooth but occur in “jumps”
Slide 12
· Integer programming models can be solved by Excel.
· In Solver to add the integer constraints
· We go to the Add Constraints dialogue box,
· highlight all the cells that are required to be integer, then in the pull down menu for the signs we select int for integer.
Slide 13
· Here is the spreadsheet for the Boxcar Burger example.
· We see in the Solver dialogue box that the integer constraints have been added
· In the Options dialogue box, we have checked our two boxes. Actually a few of the entries in this box could be modified (Tolerance and convergence being two of them), but we will keep the default values.
Slide 14
· When Solve is clicked we get this output
· We see that it sys the company should build 4 suburban restaurants and 3 downtown restaurants. Looking at the left hand side values we can see that this will cost $26 million and require only 15 managerial positions.
· If we clicked Sensitivity Report when the problem is solved we get this message, which does inform us that sensitivity reports are not valid for integer models.
Slide 15
· Let’s review what we’ve discussed in this module.
· We pointed out when it might be necessary to use integer models.
· We discussed why rounding may not give you the optimal or even a feasible solution,
· We pointed out that solution time for integer models is much greater than that for the corresponding linear model.
· We said that software packages do not provide us with meaningful sensitivity analyses for integer models.
· We pointed out that the objective function value cannot improve over the corresponding linear model
· And we showed how to solve integer models using Solver.
That’s it for this module. Do any assigned homework and I’ll be back to talk to you again next time.