A Tutorial on Integer Programming - Clemson University

1 A Tutorial on Integer ProgrammingG erard Cornu ejolsMichael A. TrickMatthew J. Saltzman1995 These notes are meant as an adjunct to Chapter 9 and 10 in Murty. Youare responsible for what appears in these notes as well as Sections { , { , , , in the Introduction22 Modeling with Integer CapitalBudgeting .. MultiperiodCapitalBudgeting .. Knapsack .. a Single-Constraint 0-1 IP to a KnapsackProblem .. and General Integer Knapsack prob -lems .. TheLockboxProblem .. 133 Solving Integer RelationshiptoLinearProgramming.}}

2 BranchandBound .. CuttingPlaneTechniques .. CutsforSpecialStructure .. 264 Solutions to Some Optional Problems3111 IntroductionConsider the manufacture of television sets. A linear Programming modelmight give a production plan of sets per week. In such a model, mostpeople would have no trouble stating that production should be 205 sets perweek (or even \roughly 200 sets per week"). On the other hand, suppose wewere buying warehouses to store nished goods, where a warehouse comes ina set size. Then a model that suggests we purchase warehouse at somelocation and somewhere else would be of little value.

3 Warehouses comein Integer quantities, and we would like our model to reflect that integrality restriction may seem rather innocuous, but in reality ithas far reaching e ects. On one hand, modeling with Integer variables hasturned out to be useful far beyond restrictions to integral production quanti-ties. With Integer variables, one can model logical requirements, xed costs,sequencing and scheduling requirements, and many other problem aspects. InAMPL, one can easily change a linear Programming problem into an downside of all this power, however, is that problems with as fewas 40 variables can be beyond the abilities of even the most sophisticatedcomputers.

4 While these small problems are somewhat arti cial, most realproblems with more than 100 or so variables are not possible to solve unlessthey show speci c exploitable structure. Despite the possibility (or evenlikelihood) of enormous computing times, there are methods that can beapplied to solving Integer programs. The CPLEX solver in AMPL is built ona combination of methods, but based on a method called branch and purpose of this chapter is to show some interesting Integer programmingapplications and to describe some of these solution techniques as well aspossible we introduce some terminology.

5 An Integer Programming problemin which all variables are required to be Integer is called apure Integer pro-gramming problem . If some variables are restricted to be Integer and someare not then the problem is amixed Integer Programming the Integer variables are restricted to be 0 or 1 comes up surprisingoften. Such problems are calledpure (mixed) 0-1 Programming problemsorpure (mixed) binary Integer Programming Modeling with Integer VariablesThe use of Integer variables in production when only integral quantities canbe produced is the most obvious use of Integer programs.

6 In this section, wewill look at some less obvious ones. The text also goes through a number ofthem (some are repeated here). Capital BudgetingSuppose we wish to invest $14,000. We have identi ed four investment op-portunities. Investment 1 requires an investment of $5,000 and has a presentvalue (a time-discounted value) of $8,000; investment 2 requires $7,000 andhas a value of $11,000; investment 3 requires $4,000 and has a value of $6,000;and investment 4 requires $3,000 and has a value of $4,000. Into which in-vestments should we place our money so as to maximize our total presentvalue?

7 As in linear Programming , our rst step is to decide on our can be much more di cult in Integer Programming because there arevery clever ways to use integrality restrictions. In this case, we will use a 0-1variablexjfor each investment. Ifxjis 1 then we will make is 0, we will not make the investment. This leads to the 0-1 programmingproblem:Maximize 8x1+11x2+6x3+4x4subject to 5x1+7x2+4x3+3x4 14xj2f0;1gj=1;:::4:Now, a straightforward \bang for buck" suggests that investment 1 is thebest choice. In fact, ignoring integrality constraints, the optimal linear pro-gramming solution isx1=1,x2=1,x3=0:5,x4= 0 for a value of $22, , this solution is not integral.

8 Roundingx3down to 0 gives afeasible solution with a value of $19,000. There is a better Integer solution,however, ofx1=0,x2=x3=x4= 1 for a value of $21,000. This exampleshows that rounding does not necessarily give an optimal are a number of additional constraints we might want to add. Forinstance, consider the following constraints:1. We can only make two If investment 2 is made, investment 4 must also be If investment 1 is made, investment 3 cannot be of these, and many morelogical restrictions, can be enforced using0-1 variables.

9 In these cases, the constraints +x2+x3+x4 x4 +x3 1(Optional)As the leader of an oil exploration drilling venture,you must determine the best selection of 5 out of 10 possible sites. La-bel the sitess1;s2;:::;s10and the expected pro ts associated with each asp1;p2;:::;p10.(i) If sites2is explored, then sites3must also be explored. Furthermore,regional development restrictions are such that(ii) Exploring sitess1ands7will prevent you from exploring sites8.(iii) Exploring sitess3ors4will prevent you from exploring an Integer program to determine the best exploration Multiperiod Capital BudgetingIn the preceding, we considered making a single investment in a project forthe duration of some term, and receiving its return at the end of the practice, we may face a choice among projects that require investments ofdi erent amounts in each of several periods (with possibly di erent budgetsavailable in each period), with the return being realized over the life of theproject.

10 In this case, we can still model the problem with variablesxj=(1 if we invest in projectj0otherwise,the objective is still to maximize the sum of the returns on the projectsselected, and there is now a budget constraint for each period. For example,suppose we wish to invest $14,000, $12,000, and $15,000 in each month of thenext quarter. We have identi ed four investment opportunities. Investment 14requires an investment of $5,000, $8,000, and $2,000 in month 1, 2, and 3,respectivey, and has a present value (a time-discounted value) of $8,000;investment 2 requires $7,000 in month 1 and $10,000 in period 3, and hasa value of $11,000; investment 3 requires $4,000 in period 2 and $6,000 inperiod 3, and has a value of $6,000; and investment 4 requires $3,000, $ 4,000,and $5,000 and has a value of $4,000.)