MTL103: Practice Sheet 5
Integer Programming
1. Convert the following constraints into linear by using integer variables:
(a) either x = 0 or x ∈ [1, 2].
(b) x takes only one of the value in {0, 1, 2, 3, 4, 5}.
(c) (either 2x1 + 9x2 ≤ 18 or x1 + x2 ≤ 6), and x1 , x2 ≥ 0.
(d) (either 2x1 − 3x2 = 0 or 3x1 + x2 ≥ 1), and x1 , x2 ≥ 0.
(e) at least one of the two but not necessarily both (x1 + x2 ≤ 1, 4x1 + x2 ≤ 2) and x1 , x2 ≥ 0.
(f) at least two of the following three (6x1 + 5x2 ≤ 60, 4x1 + 5x2 ≤ 50 3x1 + 7x2 ≤ 80).
(g) If 6x1 + 5x2 > 30 then 4x1 + 7x2 ≤ 28.
2. Consider the example of a manufacturer of animal feed who is producing feed mix for dairy cattle. In our
simple example the feed mix contains two active ingredients and a filler to provide bulk. One kg of feed mix
must contain a minimum quantity of each of four nutrients as below:
Nutrient A B C D
gram 90 50 20 2
The ingredients have the following nutrient values and cost
A B C D Cost/Kg
Ingredient 1 (gm/Kg) 100 80 40 10 40
Ingredient 2 (gm/Kg) 200 150 20 - 60
If we use any of ingredient 2 we incur a fixed cost of Rs 15. Also, we need not satisfy all four nutrient constraints
but need only satisfy three of them (i.e., now the optimal solution could only have three (any three) of these
nutrient constraints satisfied and the fourth violated). Give the complete MIP formulation of the problem with
these two new conditions added.
3. Suppose a bakery sells eight varieties of doughnuts. The preparation of varieties 1, 2, and 3 involves a rather
complicated process, and so the bakery has decided that it would rather not bake these varieties unless it can
bake and sell at least 10 dozen doughnuts of varieties 1, 2, and 3 combined. Suppose also that the capacity
of the bakery prohibits the total number of doughnuts baked from exceeding 30 dozens, and that the per unit
profit f or a variety j doughnut is Rs Pj . Formulate the problem as mixed integer programming problem.
4. Suppose a Research and Development company has a sum of money, Rs M , available for investment. The
company has determined that there are N projects suitable for investment and at least Rs pj must be invested
in project j if it is decided that project j is worthy of investment. The company net profit that can be made
by an investment in project j is Rs Pj . The company’s dilemma is that it cannot invest in all N projects.
Formulate the optimization model so to advise in which projects company should invest to maximize the profit.
(This problem is resource allocation problem).
5. A thief enters in a Mall with a knapsack (shoulder bag) of carrying capacity V Kg of weight. There are n
number of distinct items available for him to carry in the bag. Each item i with a size si and a worth value vi .
The objective is to maximize the total value of the items in the knapsack. Advise (!) a thief as to what items
he should pick by constructing a model for him. (This problem is called knapsack problem and undoubtedly
the most studied one in the MIP literature).
6. A company has selected m possible sites for distribution of its products in a certain area. There are n customers
in the area and the transport cost of supplying all the customer j requirements over the given planning period
from site i is cij . If the site i is constructed and developed for distribution purposes then it incurs a cost fi to
the company. Which sites should be selected by the company to minimize the total construction plus transport
cost? Formulate it as an integer programming problem. (This problem is known as facility location problem).
7. Consider maximization of a piecewise linear function
0 x=0
0.5x + 1 0 < x ≤ 10
f (x) = x−4 10 ≤ x ≤ 15
1.6x − 8 15 ≤ x ≤ 25
−2x + 82 25 ≤ x ≤ 30
over the interval [0, 30]. Convert this optimization problem into a mixed integer programming problem.
8. Use the Gomory cut technique to solve the following problems:
(i). max v = 4x1 + 3x2
subject to 3x1 + 5x2 ≤ 11, 4x1 + x2 ≤ 8, x1 , x2 ≥ 0, x1 is integer
(ii). max v = x1 + x2
subject to 2x1 + 5x2 ≤ 16, 6x1 + 5x2 ≤ 30 x1 , x2 ≥ 0, are integer
(iii). min v = 3x1 − x2
subject to − 10x1 + 6x2 ≤ 15, 14x1 + 18x2 ≤ 63, x1 , x2 ≥ 0, x1 is integer
(iv). max v = 2x1 + 20x2 − 10x3
subject to 2x1 + 20x2 + 4x3 ≤ 15, 6x1 + 20x2 + 4x3 = 20, x1 , x2 , x3 ≥ 0, x1 , x2 are integer
9. Consider the integer program:
max v = 15x1 + 32x2
subject to 7x1 + 16x2 ≤ 52
3x1 − 2x2 ≤ 9
x1 , x2 ≥ 0
x1 , x2 are integer
()
3
Show that the optimal solution of relaxed problem is 4,
. Rounding the optimal solution will yield two
2
infeasible points. Use Gomory cut technique to obtain the optimal solution.
10. Use Branch and Bound technique to solve:
(i.) max v = x1 − 3x2
11
subject to x1 + x2 ≤ 5, −x1 + 2x2 ≤ , x1 , x2 ≥ 0, x2 is integer
2
(ii.) max v = 9x1 + 10x2
subject to 2x1 + 5x2 ≤ 15, x1 ≤ 3, x1 , x2 ≥ 0, are integer
