Integer Programming
 When all variables are requited to be integers, then we have a pure integer programming problem (IP).
 When some of the variables are requited to be integers, then we have a mixed integer programming problem (MIP).
 An integer programming problem in which all the variables must equal 0 or 1 is called a 01 IP ot Binary IP.
The concept of LP relaxation of an IP problem plays a key role in the solution of IP’s.
Definition: The LP obtained by omitting all integer or 0 – 1 constraints on variables is called the LP relaxation of the IP.
e.g. Max Z = 3x_{1} + 2x_{2} Max Z = 3x_{1} + 2x_{2}
IP s.t. x_{1} + x_{2} ≤ 6 → s.t. x_{1} + x_{2} ≤ 6 LP relaxation
x_{1}, x_{2} ≥ 0 x_{1}, x_{2} integer x_{1}, x_{2} ≥ 0
An IP may be viewed as the LP relaxation plus additional constraints (e.g. integer values). Hence, the feasible region for any IP must be contained in the feasible region for the corresponding LP relaxation. For any IP that is a max. problem implies that,
Optimal Zvalue for LP relaxation ≥ Optimal Zvalue for IP.
Many practical solutions can be formulated as IP’s (see section 9.2 on p.477 in text book).
Examples: Capital budgeting (choosing among investments), fixed charge problem (cost related to activity, not on level of activity), credit card processing operations, facility locations, etc. The following are some examples.
i) Formulating IPs (Examples are from Winston or based on Winston)
a) Capital Budgeting Example
Suppose we wish to invest $14 000. We have identified four investment opportunities. Investment 1 requires an investment of $5 000 and has a net present value (NPV) of $16 000; investment 2 requires $7,000 and has a NPV of $22 000; investment 3 requires $4 000 and has a NPV of $12 000; and investment 4 requires $3 000 and has a NPV of $8 000. Into which investments should we place our money so as to maximize our total NPV?
As in LP, we begin by defining a variable for each decision.
In this case, we use a 01 variable x_{j}_{ }for each investment.
If x_{j}_{ }is 1 then we will make investment j.
If it is 0, we will not make the investment. Then, the problem is,
Max Z = 16 x_{1 }+ 22x_{2 }_{ }+ 12x_{3}_{ }+ 8x_{4}
s.t 5x_{1 }+7x_{2 }+ 4x_{3 }+ 3x_{4 }_{ }< 14
x_{j }_{ }= 0 or 1 (j = 1, 2, 3, 4)
Note: The optimal solution to above is x1 = 0, x2 = x3 = x4 = 1, Z = $42 000. Investment 1, even though it yields a higher NPV per dollar, is not chosen because investing in 1 would only allow $12 000 to be invested whereas the optimum choices allow all $14 000 to be invested).
Capital Budgeting (Continued)
There are a number of additional constraints we might want to add. Logical restrictions can be enforced using 01 variables. For instance, consider the following requirements:
We can only invest in at most two investments – simply add the constraint,
x_{1 }+ x_{2}_{ }_{ }+ x_{3 }_{ }+ x_{4 }_{ }≤ 2
If we invest in 2,must also invest in investment 1 – we add the constraint,
x_{2 }_{ }< x_{1 }or x_{2 }– x_{1}_{ }< 0
^{I}^{f}^{ }^{x}_{2}_{ }^{is}^{ }^{1,}^{ }^{then}^{ }^{x}_{1 }^{is}^{ }^{al}^{s}^{o}^{ }^{1}^{ }^{as}^{ }^{required;}^{ }^{if}^{ }^{x}_{2}_{ }^{is}^{ }^{0,}^{ }^{then}^{ }^{there}^{ }^{is}^{ }^{no}^{ }^{restriction}^{ }^{for}^{ }^{x}_{1 }^{(}^{x}_{1 }is 0 or 1)
If investment 2 is made, can not invest in 4 – add the constraint,
x_{2 }+ x_{4 }_{ }< 1
^{I}^{f}^{ }^{x}_{2 }^{is 1, then}^{ }^{x}_{4 }^{is}^{ }^{0}^{ }^{a}^{s}^{ }^{required;}^{ }^{if}^{ }^{x}_{2}_{ }^{is}^{ }^{0,}^{ }^{then}^{ }^{there}^{ }^{is}^{ }^{no}^{ }^{restriction}^{ }^{for}^{ }^{x}_{4}_{ }^{(}^{x}_{3}_{ }^{is}^{ }^{0 }or 1)
b) Fixed Charge Problems
This example illustrates an important trick can be used to formulate many production and location problems as IPs.
Gandhi Cloth Company is capable of manufacturing three types of clothing: shirts, shorts, and pants. The manufacture of each type of clothing requires that Gandhi have the ap propriate type of machinery available. The machinery needed to manufacture each type of clothing must be rented at the following rates: shirt machinery, $200 per week; shorts machinery, $150 per week; pants machinery, $100 per week. The manufacture of each type of clothing also requires the amounts of cloth and labor shown in Table 2. Each week, 150 hours of labor and 160 sq yd of cloth are available. The variable unit cost and sell ing price for each type of clothing are shown in Table 3. Formulate an IP whose solution will maximize Gandhi’s weekly profits.
As in LP formulations, we define a decision variable for each decision that Gandhi must make. We define,
x_{1 = }number of shirts produced each week
x_{2}_{ = }number of shorts produced each week
x_{3 = }number of pants produced each week
Resource Requirements for Gandhi Revenue and Cost Information for Gandhi
Clothing Labour Cloth Clothing Sales Variable
Type (Hours) (Sq Yards) Type Price ($) Cost ($)
Shirt 3 4 Shirt 12 6
Shorts 2 3 Shorts 8 4
Pants 6 4 Pants 15 8
Note that the cost of renting machinery depends only on the types of clothing produced, not on the amount of each type of clothing. This enables us to express the cost of renting machinery by using the following variables:
y1 = 1 if any shirts are manufactured, y1 = 0 otherwise
y2 = 1 if any shorts are manufactured, y2 = 0 otherwise
y3 = 1 if any pants are manufactured, y3 = 0 otherwise
In short, if xj_{ }_{> }0, then yj = 1, and if xj = 0, then yj = 0. Thus, Gandhi’s weekly profits
= (weekly sales revenue)  weekly variable costs)  (weekly costs of renting machinery).
_{Also, w}eekly cost of renting machinery = 200y_{1 + }150y_{2}_{ + }100y_{3}_{ (A)}
To justify (A), note that it picks up the rental costs only for the machines needed to manufacture those products that Gandhi is actually manufacturing. For example, suppose that shirts and pants are manufactured. Then y_{1}_{ = } y_{3 =} 1 and y_{2}_{ = }0, and the total weekly rental cost will be (200 + 100) = $300.
Because the cost of renting, say, shirt machinery does not depend on the number of shirts produced, the cost of renting each type of machinery is called a fixed charge. A fixed charge for an activity is a cost that is assessed whenever the activity is undertaken at a nonzero level. The presence of fixed charges will make the formulation of the Gandhi problem much more difficult.
Gandhi’s weekly profits will be,
Weekly profit = (12x_{1}_{ + }8x_{2 + }15x_{3})  (6x_{1}_{ + }4x_{2}_{ + }8x_{3})  (200y_{1 + }150y_{2}_{ + }100y_{3})
= 6x_{1}_{ + }4x_{2}_{ + }7x_{3}_{  }200y_{1}_{ } 150y_{2}_{  }100y_{3}
Thus, Gandhi wants to maximize
z = 6x_{1}_{ + }4x_{2}_{ + }7x_{3}_{  }200y_{1}_{  }150y_{2}_{  }100y_{3}
Because its supply of labor and cloth is limited, Gandhi faces the following two constraints:
Constraint 1: At most, 150 hours of labor can be used each week.
Constraint 2: At most, 160 sq yd of cloth can be used each week. Then,
3x_{1}_{ + }2x_{2}_{ + }6x_{3}_{ ≤ }150 (Labor constraint)
4x_{1}_{ + }3x_{2}_{ + }4x_{3}_{ ≤ }160 (Cloth constraint) (IP1)
Combining above,
Max z = 6x_{1}_{ + }4x_{2}_{ + }7x_{3}_{  }200y_{1}_{  }150y_{2}_{  }100y_{3}
s.t. 3x_{1}_{ + }2x_{2}_{ + }6x_{3}_{ ≤ }150
4x_{1}_{ + }3x_{2}_{ + }4x_{3}_{ ≤ }160
x_{1}, x_{2}, x_{3}_{ ≥ }0; x_{1}, x_{2}, x_{3 }_{ }integer
s.t. 3x_{1}_{ } y_{1}, y_{2}, y_{3 = }0 or 1
The optimal solution to this problem is found to be x_{1}_{ = }30, x_{3}_{ = }10, x_{2}_{ = }y_{1}_{ =}y_{2}_{ = }y_{3}_{ = }0. This cannot be the optimal solution to Gandhi’s problem because it indicates that Gandhi can manufacture shirts and pants without incurring the cost of renting the needed machinery. The current formulation is incorrect because the variables y_{1}, y_{2}, and y_{3 }_{ }are not present in the constraints. This means that there is nothing to stop us from setting y_{1 = }y_{2}_{ = }y_{3}_{ = }0. Setting y_{i}_{ }_{= }0 is certainly less costly than setting y_{i}_{ }_{= }1, so a minimum cost solution to IP1 will always set y_{i }_{= }0. Somehow we must modify (IP 1) so that whenever x_{i }_{> }0, y_{i}_{ }_{= }1 must hold. The following trick will accomplish this goal. Let M_{1}, M_{2}, and M_{3 }_{ }be three large positive numbers, and add the following constraints to (IP 1):
x1 ≤ M1y1 (a)
x2 ≤ M2y2 (b)
x3 ≤ M3y3 (c)
Adding these to IP 1 will ensure that if x_{i}_{ }_{> }0, then y_{i}_{ }_{= }1. To illustrate, if x_{1}_{ > }0, then y_{1}_{ }_{ }cannot be 0. For if y_{1}_{ = }0, then the above (a) would imply x_{1}_{ ≤ }0 or x_{1}_{ = }0. Thus, if x_{1 > }0, y_{1}_{ = }1 must hold. If any shirts are produced (x_{1}_{ >} 0), (a) ensures that y_{1}_{ = }1, and the objective function will include the cost of the machinery needed to manufacture shirts. Note that if y_{1}_{ = }1, then (a) becomes x_{1}_{ ≤ }M_{1}, which does not unnecessarily restrict the value of x_{1}. If M_{1 }were not chosen large, however (say, M_{1 = }10), then (a) would unnecessarily restrict the value of x_{1}. In general, M_{i }should be set equal to the maximum value that x_{i }can attain. In the current problem, at most 40 shirts can be produced (if Gandhi produced more than 40 shirts, the company would run out of cloth), so we can safely choose M_{1 = }40. Also, M_{2 = }53 and M_{3}_{ = }25.
If x_{1}_{ = }0, (a) becomes 0 ≤ M_{1}y_{1}. This allows either y_{1}_{ = }0 or y_{1}_{ = }1. Because y_{1}_{ = 0 }^{is}^{ }^{less}^{ }^{cost}^{l}^{y}^{ }^{than}^{ }^{y}_{1 = }^{1,}^{ }^{the}^{ }^{optimal}^{ }^{solution}^{ }^{will}^{ }^{choose}^{ }^{y}_{1}_{ = }^{0}^{ }^{if}^{ }^{x}_{1}_{ = }^{0.}^{ }^{In}^{ }^{summa}^{r}^{y}^{,}^{ }^{if}^{ }^{(a)–(c)}^{ }^{are}^{ }^{added}^{ }^{to}^{ }^{(IP}^{ }^{1),}^{ }^{then}^{ }^{x}_{i}_{ }_{> }^{0}^{ }^{will}^{ }^{imp}^{l}^{y}^{ }^{y}_{i}_{ }_{= }^{1, and}^{ }^{x}_{i}_{ }_{= }^{0}^{ }^{will}^{ }^{imp}^{l}^{y}^{ }^{y}_{i}_{ }_{= }^{0.}
^{The}^{ }^{optimal}^{ }^{solution}^{ }^{to}^{ }^{the}^{ }^{Gandhi}^{ }^{pro}^{b}^{lem}^{ }^{is}^{ }^{z }^{= $75,}^{ }^{x}_{3}_{ = }^{25,}^{ }^{y}_{3}_{ = }^{1.}^{ }^{Thus,}^{ }^{Gandhi }should produce 25 pants each week.
The Gandhi problem is an example of a fixedcharge problem. In a fixedcharge problem, there is a cost associated with performing an activity at a nonzero level that does not depend on the level of the activity. Thus, in the Gandhi problem, if we make any shirts at all (no matter how many we make), we must pay the fixed charge of $200 to rent a shirt machine. Problems in which a decision maker must choose where to locate facilities are often fixedcharge problems. The decision maker must choose where to locate various facilities (such as plants, warehouses, or business offices), and a fixed charge is often associated with building or operating a facility.
c) The Lockbox Example
Consider a national firm that receives checks from all over the United States. There is a variable delay from when the check is postmarked (and hence the customer has met her obligation) and when the check clears (the firm can use the money). It is in the firm's interest to have the check clear as quickly as possible since then the firm can use the money. To speed up this clearing, firms open offices (lockboxes) in different cities to handle the checks.
For example, suppose we receive payments from four regions (West, Midwest, East, and South). The average daily value from each region is as follows: $70,000 from the West, $50,000 from the Midwest, $60,000 from the East, and $40,000 from the South. We are considering opening lockboxes in L.A., Chicago, New York, and/or Atlanta. Operating a lockbox costs $50,000 per year. The average days from mailing _{to}_{ }_{clearing is given in the table.}


LA

Chicago

NY

Atlanta

West

2

6

8

8

Midwest

6

2

5

5

East

8

5

2

5

South

8

5

5

2

Which lockboxes should we open? Formulate an IP that we can use to minimize the sum of costs due to lost interest and lockbox operations. Assume that each region must send all its money to a single city and investment rate is 20%.
First we must calculate the losses due to lost interest for each possible assignment. For example, if the West sends to New York, then on average there will be $560,000 (= 8 * $70.000) in process on any given day. Assuming an investment rate of 20%, this corresponds to a yearly loss of $112,000. We can calculate the losses for the other possibilities in a similar fashion to get the following table.


LA

Chicago

NY

Atlanta

West

28

84

112

112

Midwest

60

20

50

50

East

96

60

24

60

South

64

40

40

16

Let y_{j}_{ }be a 01 variable that is 1 if lockbox j is opened and 0 if it is not.
Let x_{i}_{j}_{ }be 1 if region i sends to lockbox j; and 0 otherwise.
Our objective is to minimize our total yearly costs. That is,
Min z = 28 x_{11}_{ }+ 84 x_{12}_{ }+ 112 x_{13}_{ }+ … + 50 y_{1 }+ 50 y_{2 }+ 50 y_{3 }+ 50 y_{4}
One set of constraint is that each region must be assigned to one lockbox:
A more difficult set of constraint is that a region can only be assigned to an open lockbox. This can be written as
x_{1j}_{ }+ x_{2j}_{ }+ x_{3j}_{ }+ x_{4j }_{ }< M y_{j}
M is any number that should be at least 4 as there are four regions.
(Suppose we do not open LA lockbox; then y_{1 =} 0, so all of x_{11}, x_{21}, x_{31}, and x_{41 }_{ }must also be 0. If y_{1}_{ =} 1, then there is no restriction on the x values.)
For this problem we would have twenty variables (four y variables, sixteen x variables) and eight constraints. This gives the following 01 linear program:
Min Z = 28 x_{11}_{ }+ 84 x_{12}_{ }+ 112 x_{13}_{ }+ 112 x_{14 }+ 60 x_{21}_{ }+ 20 x_{22}_{ }+ 50 x_{23}_{ }+ 50x_{24}
+ 96 x_{31}_{ }+ 60 x_{32}_{ }+ 24 x_{33}_{ }+ 60 x_{34 }+ 64 x_{41}_{ }+ 40 x_{42}_{ }+ 40 x_{43}_{ }+ 16 x_{44}
+ 50 y_{1 }+ 50 y_{2 }+ 50 y_{3 }+ 50 y_{4}
_{s.t.}
x_{11}_{ }+ x_{1}_{2}_{ }+ x_{13}_{ }+ x_{1}_{4 }= 1
x_{21}_{ }_{ }+ x_{2}_{2}_{ }+ x_{23}_{ }+ x_{2}_{4}_{ }= 1
x_{31}_{ }_{ }+ x_{3}_{2}_{ }+ x_{33}_{ }+ x_{3}_{4}_{ }= 1
x_{41}_{ }_{ }+ x_{4}_{2}_{ }+ x_{43}_{ }+ x_{4}_{4}_{ }= 1
x_{11}_{ }_{ }+ x_{2}_{1}_{ }+ x_{31}_{ }+ x_{4}_{1}_{ }< 4y_{1 }
x_{12}_{ }+ x_{2}_{2}_{ }+ x_{32}_{ }+ x_{4}_{2}_{ }< 4y_{2 }
x_{13}_{ }+ x_{2}_{3}_{ }+ x_{33}_{ }+ x_{4}_{3}_{ }< 4y_{3 }
x_{14}_{ }+ x_{2}_{4}_{ }+ x_{34}_{ }+ x_{4}_{4}_{ }< 4y_{4}
All x_{i}_{j}_{ }and y_{j}_{ }= 0 or 1
_{There}_{ }_{are}_{ }_{other}_{ }_{formulations, however.}
For instance, instead of four constraints of the form x_{1j}_{ }+ x_{2j }_{ }+ x_{3j}_{ }+ x_{4j }_{ }< M y_{j ,}
consider the sixteen constraints of the form:
x_{i}_{j}_{ }< y_{j }i = 1, 2, 3, 4; j = 1, 2, 3, 4
These constraints also force a region to only use open lockboxes.
(Suppose y_{j }_{ }is 0, so by using four corresponding constraints all of x_{1}_{j}, x_{2}_{j}, x_{3}_{j}, and x_{4j }
must also be 0. If y_{j}_{ }is 1, then there is no restriction on the x values.
Another point of view: If x_{i}_{j}_{ }= 1, then y_{j }_{ }= 1 as required. Also if x_{1j }= x_{2j }= x_{3j }= x_{4j }= 0, then there is no restriction on the y values. The act of minimizing costs will result y_{j}_{ }= 0.
_{d) SetCovering Problems}
_{Th}_{e}_{ }_{foll}_{o}_{win}_{g}_{ e}_{xampl}_{e}_{ }_{i}_{s}_{ }_{typica}_{l}_{ }_{o}_{f}_{ }_{a}_{n}_{ }_{impo}_{r}_{tan}_{t}_{ }_{clas}_{s}_{ }_{o}_{f}_{ }_{IP}_{s}_{ }_{kn}_{o}_{w}_{n}_{ }_{a}_{s}_{ }_{setc}_{o}_{v}_{erin}_{g}_{ }_{pro}_{b}_{lems.}
Example: There are six cities (cities 1–6) in Kilroy County. The county must determine where to build fire stations. The county wants to build the minimum number of fire stations needed to ensure that at least one fire station is within 15 minutes (driving time) of each city. The times (in minutes) required to drive between the cities in Kilroy County are shown in Table below. Formulate an IP that will tell Kilroy how many fire stations should be built and where they should be located.
For each city, Kilroy must determine whether to build a fire station there. We define the 0–1 variables x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, and x_{6 }_{ }by
xi = 1 if a fire station is built in city 1, otherwise xi = 0.
Then the total number of fire stations that are built is given by ( x_{1}_{ +} x_{2}_{ +} x_{3}_{ +} x_{4}_{ +}_{ }^{x}_{5}_{ +}^{ }^{x}_{6)}^{,}^{ }^{and}^{ }^{Kilr}^{o}^{y}^{’}^{s}^{ }^{object}^{i}^{v}^{e}^{ }^{function}^{ }^{is}^{ }^{to}^{ }^{minimize}
z = x_{1}_{ } + x_{2}_{ } + x_{3}_{ } + x_{4}_{ } + x_{5}_{ } + x_{6}
What are Kilroy’s constraints? Kilroy must ensure that there is a fire station within 15 minutes of each city. Table below indicates which locations can reach the city in 15 minutes or less. To ensure that at least one fire station is within 15 minutes of city 1, we add the constraint
x_{1}_{ } + x_{2}_{ } ≥ 1 (City 1 constraint)
This constraint ensures that x_{1 = }x_{2}_{ = }0 is impossible, so at least one fire station will be built within 15 minutes of city 1. Similarly the constraint
x_{1}_{ +} x_{2}_{ } + x_{6}_{ } ≥ 1 (City 2 constraint)
ensures that at least one fire station will be located within 15 minutes of city 2. In a similar fashion, we obtain constraints for cities 3–6. Combining these six constraints with the objective function ( and the fact that each variable must equal 0 or 1), we obtain the following 0 – 1 IP:
Time Required to Travel between Cities in Kilroy County

From

City 1

City 2

City 3

To

City 4

City 5

City 6

City 1

0

10

20


30

30

20

City 2

10

0

25


35

20

10

City 3

20

25

0


15

30

20

City 4

30

35

15


0

15

25

City 5

30

20

30


15

0

14

City 6

20

10

20


25

14

0

Cities within 15 Minutes of
Given City
City Within 15 Minutes

1

1, 2

2

1, 2, 6

3

3, 4

4

3, 4, 5

5

4, 5, 6

6

2, 5, 6

Min z = x1 + x2 + x3 + x4 + x5 + x6
s.t. x1 + x2 ≥ 1 (City 1 constraint)
x1 + x2 x6 ≥ 1 (City 2 constraint)
x3 + x4 ≥ 1 (City 3 constraint)
x3 + x4 + x5 ≥ 1 (City 4 constraint)
x4 + x5 + x6 ≥ 1 (City 5 constraint)
x2 + x5 + x6 ≥ 1 (City 6 constraint)
xi = 0 or 1 ( i = 1, 2, 3, 4, 5, 6)
One optimal solution to this IP is z =2, x_{2}_{ = }x_{4}_{ = }1, x_{1}_{ = }x_{3}_{ }= x_{5 =} x_{6}_{ = }0. Thus, Kilroy County can build two fire stations: one in city 2 and one in city 4.
e) Dealing with Either – or Constraints
The following is a commonly occurring mathematical programming problem. We have two constraints:
f(x_{1}, x_{2},...... ,x_{n}) ≤ 0
g(x_{1}, x_{2},...... ,x_{n}) ≤ 0
We want to ensure that at least one of the constraints is satisfied. To ensure that, we write
f(x_{1}, x_{2},...... ,x_{n}) ≤ My (1)
g(x_{1}, x_{2},...... ,x_{n}) ≤ M(1 – y) (2)
where y is a 0 – 1 variable and M is a number chosen large enough to ensure that f(x_{1},x_{2},......,x_{n}) ≤ M and g(x_{1}, x_{2},...... ,x_{n}) ≤ M are satisfied for all values of x_{1}, x_{2}, ..., x_{n} that satisfy other constraints in the problem. [y = 0, (1) is satisfied, possibly also (2). If y = 1, (2) is satisfied and possibly (1) also]
f) If – The Constraints
We want to ensure that if a constraint f(x_{1}, x_{2}, ...,x_{n}) > 0 is satisfied, then the constraint g(x_{1},x_{2},.....x_{n}) ≥ 0 must be satisfied while if f(x_{1}, x_{2}, .... x_{n}) > 0 is not satisfied, then g(x_{1},x_{2},......x_{n}) ≥ 0 may or may not be satisfied. To ensure this, we include the following constraints in the formulations:
 g(x_{1}, x_{2}, ......, x_{n}) ≤ My (3)
f(x_{1}, x_{2}, ......., x_{n}) ≤ M(1 – y) (4)
y = 0 or 1
(M is chosen large enough that f ≤ M and –g ≤ M for all values of x_{1}, x_{2}, ...., x_{n} that satisfy the other constraints). f > 0 can only be satisfied if y = 0; then (3) is satisfied. If f > 0 is not satisfied and y = 1, (3) is satisfied, then g < 0 or g ≥ 0 are both possible.
Primary determinants of computational difficulty for an IP problem are (1) the number of integer variables and (2) any special structure in the problem. In LP, the number of functional constraints is much more important than the number of variables. In IP, number of functional constraints are of secondary importance. For MIP problems, it is the number of integer variables rather than the total number of variables that is important.
ii) The Branch – and – Bound Method for Solving IP Problems
a) Pure IP Problems
In practice, most IP’s are solved by using this technique.
Note: If we solve the LP relaxation of a pure IP and obtain a solution in which all variables are integers, then the optimal solution to the LP relaxation is also the optimal solution to the IP.
Let us consider the example of pure IP:
Max Z = 8x_{1} + 5x_{2}
s.t. x_{1} + x_{2} ≤ 6
9x_{1} + 5x_{2} ≤ 45
x_{1}, x_{2} ≥ 0; x_{1}, x_{2} integer.
The branchandbound method begins by solving LP relaxation of the IP ( i.e. no integer constraint). If in the optimal solution variables are integers, then it is also optimal solution for the IP. However, LP relaxation solution yields Z = 165/4, x_{1} = 15/4, x_{2} = 9/4.
We now know that optimal Zvalue for IP ≤ 165/4 (= 41.25). Upper bound = 41 since we have integer values in IP.
The next step is to partition the feasible region for the LP relaxation. We arbitrarily choose a variable that is fractional in the optimal solution to the LP relaxation – say x_{1}. Now, every point in the feasible region for the IP must have either x_{1} ≤ 3 or x_{1} ≥ 4.
Subproblem 2 = Subproblem 1 (LP relaxation) + constraint x_{1} ≥ 4
Subproblem 3 = Subproblem 1 (LP relaxation) + constraint x_{1} ≤ 3
10
9 9x_{1} + 5x_{2} = 45
8
7 x_{1} + x_{2} = 6
6
5
4
3
2 F Optimal LP solution to Subproblem 1
1 C x_{1} = 3.75, x_{2} = 2.25
0
0 1 2 3 4 A 5 6 7
We see that every point described by integer numbers in the feasible region are the feasible points (intersections of dotted lines and intersections of the dotted lines and the axes). We also see that every feasible point is included in the feasible region for subproblem 2 or subproblem3. We say that subproblems 2 and 3 were created by branching on x_{1}.
We now choose arbitrarily to solve subproblem 2.
Solution is the point C where Z = 41, x_{1} = 4, and x_{2} = 9/5
Solution step at this stage is as follows.
Subproblem 1
Z = 165/4
x_{1}= 15/4
x_{2} = 9/4
t = 1
x_{1} ≥ 4 x_{1} ≤ 3
Subproblem 2
Z = 41
x_{1}= 4
x_{2} = 9/5
Subproblem 3
A display of all subproblems that have been created is called a tree. Each subproblem is referred to as a node of the tree and each line connecting two nodes is called an arc.
Subproblem 2 did not yield all integer solution. So, we choose subproblem 2 to create two new subproblems. In this case we branch on x_{2} (only fractional variable).
Subproblem 4 = Subproblem 1 + constraint x_{1} ≥ 4 and x_{2} ≥ 2 = subproblem 2 + constraint x_{2} ≥ 2
Subproblem 5 = Subproblem 2 + constraint x_{2} ≤ 1
For feasible regions for subproblems 4 and 5 see figure. (B,A,I,H for subpr. 5).
C x_{2} = 2
H I x_{2} = 1
B A
4 5
Now, unsolved problems are: Subproblems 3, 4, and 5. We now choose one to solve. We choose to solve the most recently created subproblem (LIFO, last in first out rule). We should then solve subproblem 4 or 5. Arbitrarily we choose subproblem 4. However, we see that subproblem 4 is infeasible and, therefore, can not yield optimal solution. We place an ‘X’ by the subproblem 4 as any branch from it will not yield useful information. When further branching on a subproblem can not yield any useful information, we say that the subproblem (or node) is fathomed.
Now, unsolved problems are Subpr. 3 and Subpr. 5. With LIFO rule, we choose to solve subpr. 5. Solution is point I where Z = 365/9, x_{1} = 40/9, and x_{2} = 1. No immediate useful information (one variable is not an integer). We therefore choose to partition Subpr. 5 by branching on x_{1}.
Subpr. 6 – Subpr. 5 + Constraint x_{1} ≥ 5
Subpr. 7 – Subpr. 5 + Constraint x_{1} ≤4
We should now solve subpr. 6 or 7. Arbitrarily we choose subpr. 7. Solution point is H where Z = 37, x_{1} = 4, and x_{2} =1.
Both variables have integer values, so this solution is feasible for the original IP. (Subpr. 7 can not yield any solution where Z > 37).
Further branching will not yield new information, hence subpr. 7 is fathomed (see tree). This, at the same time, is a candidate solution since all variables are integer values. We keep the candidate solution until a better one is found. This is now a lower bound for Z. Optimal Z ≥ 37. We indicate Lower Bound by placing LB = 37 in the box corresponding to the next solved subproblem.
Next to sove is Subpr. 6. The solution is point A where Z = 40, x_{1} = 5, and x_{2} = 0.
All decision variables are integers. Z = 40 is larger than Z = 37 of subpr. 7. We then place ‘X’ by subproblem 7, we update LB to 40 and make this solution candidate solution.
Subproblem 3 is the only unsolved problem. Solution is point F where Z = 39, x_{1} = x_{2} = 3. Subpr. 3 can not yield a Zvalue exceeding the current lower bound 40, so it can not yield the optimal solution. We place an ‘X’ next to it (it is fathomed). Optimal solution is,
x_{1} = 5, x_{2} = 0, and Z = 40.
Subpr. 1
Z = 165/4
x_{1}= 15/4
x_{2} = 9/4
t = 1
x_{1} ≥ 4 x_{1} ≤ 3
Subpr. 3
Z = 39
x_{1} = 3
x_{2} = 3
LB = 40
Subpr. 2
Z = 41
x_{1}= 4
x_{2} = 9/5
t = 2 t = 7 X
x_{2} ≥ 2 x_{2} ≤ 1
Subpr. 4
Infeasible
Subpr. 5
Z = 365/9
x_{1} = 40/9
x_{2} = 1
t = 3 t = 4
X
x_{1} ≥ 5 x_{1} ≤ 4
Subpr.7
Z = 37
x_{1} = 4
x_{2} = 1
Cand. Soln
Subpr. 6
Z = 40
x_{1} = 5
x_{2} = 0
LB = 37
Cand. Soln
t = 6 t = 5 X
Optimal Solution
Key Aspects of Branchand Bound Method for Solving pure IP’s
Step 1 – If it is unnecessary to branch on a subproblem, then it is fathomed. The following three situations result in a subproblem being fathomed:
(1) The optimal Z value for the subproblem does not exceed (in a max. problem) the current LB.
(2) The subproblem is infeasible, and
(3) The subproblem yields an optimal solution in which all variables have integer values.
Step 2 – A subproblem may be eliminated from consideration in the following situations: (1) The subproblem is infeasible, (2) The LB is at least as large as the Zvalue for the subproblem.
b) BranchandBound Method for Solving Mixed Integer Programming Problems
These problems are solved with similar procedure to the IP method. For these problems, the procedure is modified by branching only on variables that are required to be integers.
c) BranchandBound Method for Solving Binary Integer Programming Problems
There are many problems which are binary IP problems. Often, they are of decision making variety with “Yes”, “No” decisions (1, 0). The method used to solve these problems is similar to the method described earlier.
Example.
Max. Z = 9x_{1} + 5x_{2} + 6x_{3} + 4x_{4}
s.t. 6x_{1} + 3x_{2} + 5x_{3} + 2x_{4} ≤ 10
x_{3} + x_{4} ≤ 1
 x_{1} + x_{3} ≤ 0
x_{2} + x4 ≤ 0
and x_{j} is binary for j = 1, 2, 3, 4
We first solve the LP relaxation of the problem. Usually we remove the set of constraints that make the problem difficult to solve. For IP, it is the integer requirement.
The LP relaxation is as shown before with the x_{j} is binary for j = 1, 2, 3, 4 replaced by
x_{j} ≤ 1 and x_{j} ≥ 0 for j = 1, 2, 3, 4
Solution yields (x_{1}, x_{2}, x_{3}, x_{4}) = (5/6, 1, 0, 1) with Z = 16 1/2
Therefore, Z ≤ 16 1/2 for all feasible solutions for the BIP problem. (Bound for the problem: Z ≤ 16 since variables are integers).
Branching for BIP problems start by fixing one of the variables, say x_{1}, at x_{1} = 0 for one subproblem and x_{1} = 1 for another subproblem.
Subproblem 1 : For x_{1} = 0
Max. Z = 5x_{2} + 6x_{3} + 4x_{4}
s.t. 3x_{2} + 5x_{3} + 2x_{4} ≤ 10
x_{3} + x_{4} ≤ 1
x_{3} ≤ 0
x_{2} + x_{4} ≤ 0
and x_{j} is binary for j = 2, 3, 4
Subproblem 2: x_{2} = 1
Max. Z = 9 + 5x_{2} + 6x_{3} + 4x_{4}
s.t. 3x_{2} + 5x_{3} + 2x_{4} ≤ 4
x_{3} + x_{4} ≤ 1
x_{3} ≤ 1
x_{2} + x_{4} ≤ 0
and x_{j} is binary for j = 2, 3, 4
LP relaxation of subproblem 1: (x_{1}, x_{2}, x_{3}, x_{4}) = (0, 1, 0, 1) with Z = 9
(Solution obtained by removing integer requirement and adding constraint x_{j} ≤ 1 and x_{j} ≥ 0 for j = 1, 2, 3, 4.
LP relaxation of subproblem 2: (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 4/5, 0, 4/5) with Z = 16 1/5
Solution to subproblem 1 is integer, we therefore fathome it with Z = 9 which now becomes candidate solution or incumbent. The subproblem 1 has been fathomed by test 3, as indicated by F(3) in diagram below.
x_{1}
0
All
9 = Z* candidate solution or incumbent
(0, 1, 0, 1)
1
Bound 16
16
(1, 4/5, 0, 4/5)
To complete the solution, similar steps are taken. To summarize the steps to reach a solution:
1. Branching: Among the remaining (unfathomed) subproblems select the one that was created most recently (break ties according to which has the larger bound). Branch from the node for this subproblem to create two new subproblems by fixing the next variable at either 0 or 1.
2. Bounding: For each new subproblem, obtain its bound by applying the simplex method to its LP relaxation and rounding down the value of Z for the resulting optimal solution.
3. Fathoming: For each new subproblem, apply the three fathoming tests summarized earlier, and discard those subproblems that are fathomed by any of the tests.
Optimality test: Stop when there are no remaining subproblems. Then, the candidate solution or the current incumbent is optimal solution. Otherwise, return to perform another iteration. (If there is no candidate solution, the conclusion is that the problem has no feasible solutions).
To complete solution of problem, we branch on subproblem 2:
Subproblem 3: x_{1} = 1, x_{2} = 0
Subproblem 4: x_{1} = 1, x_{2} = 1
LP relaxation solutions:
Subproblem 3: (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 0, 4/5, 0) Z = 13 4/5
Subproblem 4: (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 2, 0, 1/2) Z = 16
Bound for subproblem 3: Z ≤ 13
Bound for subproblem 4: Z ≤ 16
Both of these subproblems fail fathoming tests.
We next branch on subproblem 3 or 4; subproblem 4 has higher bound, we choose subproblem4.
Subproblem 5: x_{1} = 1, x_{2} = 1, x_{3} = 0 LP relaxation: (1, 1, 0, 1/2) Z = 16
Subproblem 6: x_{1} = 1, x_{2} = 1, x_{3} = 1 LP relaxation: No feasible solution.
Bound for subproblem 5: Z ≤ 16
Subproblem 5 can not be fathomed (fails test); Subproblem 6 is fathomed F(2).
Since, now, the resulting branching variable x_{4} is the last variable, fixing its value at either 0 or 1 actually creates a single solution rather than subproblems requiring full investigation. These single solutions are:
x_{4} = 0: (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 1, 0, 0) is feasible with Z = 14.
x_{4} = 1: (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 1, 0, 1) is infeasible.
Fathoming tests: First solution passes test 3, second passes test 2. Furthermore, first solution is better than the candidate or incumbent solution (14 > 9), so it becomes the new candidate solution or incumbent with Z* = 14.
The only remaining subproblem is now the node subproblem 3 (x_{1} = 1, x_{2} = 0). Its bound is 13 which is less than 14. Therefore, subproblem 3 is also fathomed by test 1.
We now have the solution tree shown below. The candidate solution or the incumbent is,
(x_{1}, x_{2}, x_{3}, x_{4}) = (1, 1, 0, 0) is optimal with Z = 14.
x_{1} x_{2} x_{3} x_{4}
0
Subpr 1
F(3)
0
0
All
9 = Z* Subpr 3
F(1)
Subpr 5 F(3)
1
0
16 13 14 = Z*
(1, 1, 0, 0) = candidate soln.
1
Subpr 2 Subpr 4 16
1
16
F(2)
1
16 Subpr 6
F(2)
iii) Cutting Plane Algorithm
An alternative method to branchandbound method is the Cutting Plane Algorithm.
Reconsidering the problem that was solved by branchandbound method:
Max Z = 8x_{1} + 5x_{2}
s.t. x_{1} + x_{2} ≤ 6
9x_{1} + 5x_{2} ≤ 45
x_{1}, x_{2} ≥ 0; x_{1}, x_{2} integer.
Optimal tableau for the LP relaxation, i.e. without integer constraint, is:
Z x_{1} x_{2} s_{1} s_{2} RHS
1 0 0 1.25 0.75 41.25
0 0 1 2.25 0.25 2.25
0 1 0 1.25 0.25 3.75
To apply cutting plane method, we begin by choosing any constraint in the LP relaxation’s optimal tableau in which a basic variable is fractional. Arbitrarily, we choose 2^{nd} constraint.
x_{1} – 1.25s_{1} + 0.25s_{2} = 3.75 (*)
We now define [x] to be the largest integer less than or equal to x, i.e. [3.75] = 3 and [1.25] =  2.
Any number can be written in the form [x] + f where 0 ≤ f < 1.
Then, 3.75 = 3 + 0.75 or  1.25 =  2 + 0.75
Now, 2^{nd} constraint becomes,
x_{1} – 2s_{1} + 0.75s_{1} + 0s_{2} + 0.25s_{2} = 3 + 0.75 or
x_{1} – 2s_{1} + 0s_{2} – 3 = 0.75 – 0.75s_{1} – 0.25s_{2} (**)
Cutting plane algorithm now suggests adding the following constraint to the LP relaxation’s optimal tableau:
0.75 – 0.75s_{1} – 0.25s_{2} ≤ 0
This constraint is called c cut (Gomory cut).
Note: The logic for the above cut is that,
 0.75s_{1} – 0.25s_{2} + 0.75 ≤ 0.75 since s1 and s2 are integers.
Also, in equation (**) LHS is integer, therefore, RHS is also integer.
Then, 0.75 – 0.75s_{1} – 0.25s_{2} ≤ 0 since integer less than 0.75 is zero.
This cut “cuts off” the current optimal solution to the LP relaxation, but not any feasible solutions to the IP. If solution with this constraint added yields an integer solution, then we have found the optimal solution to the original IP. If the new optimal solution (to LP relaxation + cut) has some fractionalvalued variables, then we generate another cut and continue the process.
We now add the “cut” constraint to the LP relaxation’s optimal tableau after adding slack variable s_{3}: (i.e.  0.75s_{1} – 0.25s_{2} + s_{3} =  0.75)
Z x_{1} x_{2} s_{1} s_{2} s_{3} RHS
1 0 0 1.25 0.75 0 41.25
0 0 1 2.25 0.25 0 2.25
0 1 0 1.25 0.25 0 3.75
0 0 0 0.75 0.25 1 0.75
Dual simplex algorithm is most appropriate for this solution. s_{1} should enter the basis in the third constraint (Ratios: 1.25/0.75 for s_{1}, 0.75/0.25 for s_{2}). The tableau becomes:
Z x_{1} x_{2} s_{1} s_{2} s_{3} RHS
1 0 0 0 0.33 1.67 40
0 0 1 0 1 3 0
0 1 0 0 0.67 1.67 5
0 0 0 1 0.33 1.33 1
Solution yields the optimal solution with Z = 40, x_{1} = 5, x_{2} = 0.
Note: The algorithm requires that all coefficients of variables in the constraints and all RHS’s of constraints be integers. This is to ensure that if the original decision variables are integers, then the slack and excess variables will also be integers. Thus, a constraint such as
x_{1} + 0.5x_{2} ≤ 3.6 must be replaced by 10x_{1} + 5x_{2} ≤ 36.
Example. Max Z = 7x_{1} + 10x_{2}
s.t.  x_{1} + 3x_{2} ≤ 6
7x_{1} + x_{2} ≤ 35
x_{1}, x_{2} ≥ 0 and integer.
Given the slacks s1 and s2 for constraints 1 and 2, the optimum LP relaxation tableau is:
BV Z x_{1} x_{2} s_{1} s_{2} RHS
Z 1 0 0 63/22 31/22 66 1/2
x_{2} 0 0 1 7/22 1/22 3 1/2
x_{1} 0 1 0 1/22 3/22 4 1/2
Optimal solutin  Z = 66 1/2 , x_{1} = 4 1/2, x_{2} = 3 1/2, s_{1} = s2 = 0
The cut is developed under the assumption that all the variables are integers (including s_{1} and s_{2}).
We can generate cut from any row above, row 0 or row 1 or row 2, and any one can be used in the first iteration.
Row 0: Z + 2s_{1} + s_{2} – 66 = (19/22)s_{1} – (9/22)s_{2} + 1/2
Then, the cut is (19/22)s_{1} – (9/22)s_{2} + 1/2 ≤ 0
Row 2 (for x1): x_{1} + ( 1 + 21/22)s_{1} + (0 + 3/22)s_{2} = (4 + 1/2)
Then, the cut is  (21/22)s_{1} – (3/22)s_{2} + 1/2 ≤ 0
Row 1 (for x2): x_{2} + (0 + 7/22)s_{1} + (0 + 1/22)s_{2} = (3 + 1/2)
Then, the cut is  (7/22)s_{1} – (1/22)s_{2} + 1/2 ≤ 0
Note: A constraint equation can be used as a source row for generating a cut provided its RHS is fractional. We also note that Z row , i.e. row 0, can be used as a source row because Z happens to be integer in this example.
We select x_{2} row (row 1) and add,
 (7/22)s_{1} – (1/22)s_{2} + s_{3} =  1/2 cut I
BV Z x_{1} x_{2} s_{1} s_{2} s_{3} RHS
Z 1 0 0 63/22 31/22 0 66 1/2
x_{2} 0 0 1 7/22 1/22 0 3 1/2
x_{1} 0 1 0 1/22 3/22 0 4 1/2
s_{3} 0 0 0 7/22 1/22 1 1/2
Tableau is optimal but infeasible. We apply the dual simplex method. Solution becomes,
BV Z x_{1} x_{2} s_{1} s_{2} s_{3} RHS
Z 1 0 0 0 1 9 62
x_{2} 0 0 1 0 0 1 3
x_{1} 0 1 0 0 1/7 1/7 4 4/7
s_{1} 0 0 0 1 1/7 22/7 1 4/7
Still non integer x_{1} and s_{1}.
Arbitrarily select row 2 (x_{1} row) for the next cut.
x_{1} + (0 + 1/7)s_{2} + (1 + 6/7)s_{3} = 4 + 4/7
The cut is,  (1/7)s_{2} – (6/7)s_{3} + 4/7 ≤ 0 cut II
We add constraint,  (1/7)s_{2} – (6/7)s_{3} + s_{4} =  4/7 s_{4} ≥ 0
BV Z x_{1} x_{2} s_{1} s_{2} s_{3} s_{4} RHS
Z 1 0 0 0 1 9 0 62
x_{2} 0 0 1 0 0 1 0 3
x_{1} 0 1 0 0 1/7 1/7 0 4 4/7
s_{1} 0 0 0 1 1/7 22/7 0 1 4/7
s_{4} 0 0 0 0 1/7 6/7 1  4/7
Applying dual simplex method,
BV Z x_{1} x_{2} s_{1} s_{2} s_{3} s_{4} RHS
Z 1 0 0 0 0 3 7 58
x_{2} 0 0 1 0 0 1 0 3
x_{1} 0 1 0 0 0 1 1 4
s_{1} 0 0 0 1 0 4 1 1
s_{2} 0 0 0 0 1 6 7 4
We have optimum solution with x_{1} = 4, x_{2} = 3, and Z = 58.
Share with your friends: 