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 .. 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").}}

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

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

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

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

6 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. 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.)

7 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. The corresponding Integer program isMaximize 8x1+11x2+6x3+4x4subject to 5x1+7x2+3x4 148x1+4x3+4x4 122x1+10x2+6x3+4x4 15xj2f0;1 KnapsackThe knapsack problem is a particularly simple Integer program: it has onlyone constraint. Furthermore, the coe cients of this constraint and the objec-tive are all non-negative. For example, the following is a knapsack problem:Maximize 8x1+11x2+6x3+4x4subject to 5x1+7x2+4x3+3x4 14xj2f0;1g:The traditional story is that there is a knapsack (here of capacity 14).

8 Thereare a number of items (here there are four items), each with a size and avalue (here item 2 has size 7 and value 11). The objective is to maximize thetotal value of the items in the knapsack. Knapsack problems are nice becausethey are (usually) easy to solve, as we will see in the dynamic programmingsection of this solve the associated linear program, it is simply a matter of determin-ing which variable gives the most \bang for the buck". If you takecj=aj(theobjective coe cient/constraint coe cient) for each variable, the one withthe highest ratio is the best item to place in the knapsack. Then the itemwith the second highest ratio is put in and so on until we reach an itemthat cannot t. At this point, a fractional amount of that item is placed inthe knapsack to completely ll it. In our example, the variables are alreadyordered by the ratio. We would rst place item 1 in, then item 2, but item3 doesn't t: there are only 2 units left, but item 3 has size 4.

9 Therefore,we take half of item 3. The solutionx1=1,x2=1,x3=0:5,x4=0istheoptima l solution to the linear already observed in Section , this solution is quite di erent fromthe optimal solution to the knapsack problem. Nevertheless, it will play animportant role in the solution of the problem by branch and bound as wewill see Converting a Single-Constraint 0-1 IP to a Knapsack Prob-lemThe nonnegativity requirement on the coe cients in the knapsack problemis not really a restriction. As mathematicians say, we can assume this re-quirement holdswithout loss of generality, since any single-constraint 0-1 IPcan be converted to knapsack form. The same cannot be said for generalinteger programs with one or more constraints. For 0-1 programs with morethan one constraint, the technique applies to columns whereallentries the general 0-1 IP with one constraint:MaximizenXj=1cjxjsubject tonXj=1wjxj w0xj2f0;1gj=1;:::;nIf anyxjhascj<0andwj 0 then it is clear that thisxjwill be 0 in anyoptimal solution, so we can xxj= 0 and remove it from the problem.

10 Ifanyxjhascj 0andwj<0 then it is clear thatxj= 1 in any optimalsolution (including itemjactually increases capacity byjwjjand increasesthe objective as well), so we can xxj= 1 and remove it from the problemas well (adjusting the capacity and objective values accordingly).Ifcj<0andwj<0 then including itemjincurs a cost but increasescapacity, so there is no obious justi cation for xingxjto either 0 or , we can de ne a new variableyj=1 xjand replacexjwith 1 yj. After collecting the constants, we have a new, equivalent problem withnonnegative coe cients example, consider the IPMaximize 8x1+11x2 6x3+4x4subject to 5x1+7x2 4x3+3x4 14xj2f0;1g:6De ningy3=1 x3and substitutingx3=1 y3givesMaximize 8x1+11x2 6(1 y3)+4x4subject to 5x1+7x2 4(1 y3)+3x4 14xj;y32f0;1g;or equivalently,Maximize 8x1+11x2+6y3+4x4 6subject to 5x1+7x2+4y3+3x4 18xj;y32f0;1 Multidimensional and General Integer Knapsack ProblemsA problem of the formMaximizecxsubject toAx bxj2f0;1g.