# 4 Integer Programming

 Page 3/4 Date 11.10.2016 Size 299.78 Kb. #8
1   2   3   4

The capacities of the three printing machines are 120 100, and 110 hours (7,200, 6,000, and 6,600 minutes).
Capacities of the binding machines: 333⅓ and 300 hours, respectively (or 20,000 and 18,000 minutes).
The costs to lease the machines are independent of the number of books made with them. They are \$10,000, \$8,000, \$9,000, \$20,000, and \$23,000, respectively. The profit contributions of the three books (other than the leasing costs) have been identified as \$40, \$60, and \$70.
Also, produce at least 500 copies of the landmark ROR book in order to maintain a good academic image.
Define variables x1, x2 and x3 as the number of books of the three types that are manufactured and sold.
Also, define binary variables y1, y2, …, y5 that assume a value of one, if a machine is leased, and 0 otherwise.
P: Max z = 40x1 + 60x2 + 70x3

 10,000y1  8,000y2  9,000y3  20,000y4 23,000y5
s.t. 3x1 + 2x2 + 4x3  7,200 + M(1−y1)

6x1 + 3x2 + 5x3  6,000 + M(1−y2)

4x1 + 3x2 + 5x3  6,600 + M(1−y3)

10x1 + 12x2 + 15x3  20,000 + M(1−y4)

10x1 + 11x2 + 14x3  18,000 + M(1−y5)

x3  500

y1 + y2 + y3 = 1

y4 + y5 = 1

x1, x2, x3  0 and integer

y1, y2, y3, y4, y5 = 0 or 1.
With M = 1,000,000, the optimal solution is == 1 and = 0 (i.e., we lease the second printing and the first binding machine), and make = 0 GB books, = 1,039 HFS books, and = 502 ROR books. The profit associated with this plan is \$69,480. Note that the slack capacities indicate huge (and meaningless) values for machines not leased. Their right-hand side values have the artificial value of M = 1,000,000, from which nonexistent usage is subtracted.
Now allow more than one printing and/or binding machine to be used. We now need additional variables xij to denote books of type i processed on machine j:
P: Max z = 40x1 + 60x2 + 70x3

10,000y1–8,000y2–9,000y3–20,000y4–23,000y5

s.t. x1 = x11 + x12 + x13

x2 = x21 + x22 + x23

x3 = x31 + x32 + x33

3x11 + 2x21 + 4x31 ≤ 7,200y1

6x12 + 3x22 + 5x32 ≤ 6,000y2

4x13 + 3x23 + 5x33 ≤ 6,600y3

10x14 + 12x24 + 15x34 ≤ 20,000y4

10x15 + 11x25 + 14x35 ≤ 10,000y5

x3 ≥ 500

y1 + y2 + y3 ≥ 1

y4 + y5 ≥ 1

x11 + x12 + x13 = x14 + x15

x21 + x22 + x23 = x24 + x25

x31 + x32 + x33 = x34 + x35

y1, …, y5 = 0 or 1

x1, x2, x3; x11, x12, …, x35 ≥ 0 and integer.
The objective function has not changed. The first three constraints link xij and xi so that they define the amounts of the products actually made. The next five constraints are capacity constraints restricting the number of units we can make by the machine capacities (zero if we do not lease the machine). The next constraint ensures that we make at least 500 units of the ROR book, and the next two constraints specify that we must choose at least one of each of the two types of machines. The last three structural constraints require books printed also to be bound.
The optimal solution is to lease the first printing machine and both binding machines. As before, we make no GB books, but 2,600 HFS books and 500 ROR books. The only significant change is the increase of HFS books from 1,039 to 2,600, resulting in a doubling of the profit from \$69,480 to \$138,000.

Example:

 T1 T2 T3 T4 T5 W1 5 1 9 4 9 W2 4 3 8 3 8 W3 7 5 6 4 7

Define variables yij = 1, if employee Wi is assigned to task Tj, and zero otherwise.
Assign each task to exactly one employee.
y1j + y2j + y3j = 1 for all j = 1, ..., 5.
Actual working times of the employees:
w1 = 5y11 + 1y12 + 9y13 + 4y14 + 9y15,

w2 = 4y21 + 3y22 + 8y23 + 3y24 + 8y25, and

w3 = 7y31 + 5y32 + 6y33 + 4y34 + 7y35,
Possibility:
Min z = max {w1, w2, w3}.
Rewrite as
Min z, s.t. zw1, zw2, and zw3 + other constraints.

Min z
s.t. z ≥ 5y11 + 1y12 + 9y13 + 4y14 + 9y15

z ≥ 4y21 + 3y22 + 8y23 + 3y24 + 8y25

z ≥ 7y31 + 5y32 + 6y33 + 4y34 + 7y35

y11 + y21 + y31 = 1

y12 + y22 + y32 = 1

y13 + y23 + y33 = 1

y14 + y24 + y34 = 1

y15 + y25 + y35 = 1

yij = 0 or 1 for i=1, 2, 3; j=1, …, 5.
Solution: W1T2 & T5, W2T1 & T4, W3T3. Workloads: 10, 7, and 6 hours.
Alternative: Min z

= ((1/3)ww1)2 + ((1/3)ww2)2 + ((1/3)ww3)2.
Always combine “equity” with an efficiency objective (otherwise workloads of 12, 12, & 12 are preferred to 7, 8, 9).

4.3 Solution Methods for Integer

Programming Problems
4.3.1 Cutting Plane Methods

The first exact techniques for solving integer programming problems were cutting plane techniques.
General idea: Solve linear programming relaxation, i.e., the given problem without integrality requirements.
If the optimal solution is integer, we are done.

Otherwise, introduce a cutting plane, i.e., an additional constraint that (1) cuts off (i.e., makes infeasible) the present optimal solution, while (2) not cutting off any feasible integer point.
Example: Consider the all-integer programming problem:
P: Max z = y1 + y2

s.t. 3y1 + 2y2 ≤ 6

y1 + 3y2 ≤ 3

y1, y2 ≥ 0 and integer.

The shaded area shows the feasible set of the linear programming relaxation, and = (12/7, 3/7) is the optimal solution of the linear programming relaxation.
The triangle shown by the broken lines connecting (0, 0), (2, 0), and (0, 1) is the convex hull of the feasible set.
The dotted line is the cutting plane 5y1 + 10y2 ≤ 12. It is indeed a cutting plane, as the present optimal solution is cut off as 90/7 = 12, and since all four feasible integer points satisfy the condition & are thus not cut off.
Computation performance of cutting planes has been disappointing.
Example: We use a simple Dantzig cut, which does not require any knowledge beyond the solution typically provided by a solver. Other, more efficient, cutting planes work on the same principle.
Given: an all-integer linear programming problem. Include all slack and excess variables, so that all constraints are equations. Let there be n nonnegative variables (including the slack and excess variables) and m structural equation constraints, and assume that the present optimal solution of the linear programming relaxation has at least one noninteger component.
Separate the variables into two disjoint sets B and N, where B includes all variables that are presently positive, while N includes all variables that are presently zero. If the solution is nondegenerate, the set B will include exactly m variables, and the set N exactly (nm) variables. In case of primal degeneracy, the set N will include more than (nm) variables, in which case we define N as any (nm) variables presently at zero.
A Dantzig cut requires the sum of all variables in the set N to be at least “1.” Validity: (1) Since all variables in the set N equal zero, the cutting plane invalidates the present solution. (2) Any feasible solution to the original integer problem will need to have at least one variable in N assume a positive value, which, since this is an all-integer optimization problem, must be at least one. Hence, the sum of all the variables that are presently zero, must be at least one.
Add the cut to the problem & re-solve the problem (preferably with a warm start). Stop, if the new solution is integer; else, repeat. The the process, the z-value cannot increase (decrease) for max (min) problems.
In each step, the feasible set shrinks. Unfortunately, for Dantzig cuts, this is not necessarily finite.
Example: Consider the integer programming problem:
Max z = 3y1 + 2y2
s.t. 3y1 + 7y2  22

5y1 + 3y2  17

y1  2

y1, y2  0 and integer.
Adding slack variables S1 and S2 and an excess variable E3, we obtain the following formulation with n = 5 variables and m = 3 structural constraints:
Max z = 3y1 + 2y2
s.t. 3y1 + 7y2 + S1 = 22

5y1 + 3y2 + S2 = 17

y1E3 = 2

y1, y2, S1, S2, E3  0 and integer.
The optimal solution is ,, , and with . Here, N = {S1, S2}, so that the Dantzig cut is
S1 + S2 ≥ 1
(or 8y1 + 10y2 ≤ 38). Subtracting a new excess variable E4 from the left-hand side of this cut, we obtain S1 + S2E4 = 1. Adding this cut to the problem and solving it again, we obtain the new solution , , , and with an objective value . Clearly, another cut is required. The sequence of cutting planes generated in the process is shown in the table below.

 Optimal solution Cutting plane , , , , with (optimal solution of the LP relaxation). S1 + S2 ≥ 1 or S1 + S2 – E4 = 1 , , , , , with . S2 + E4 ≥ 1 or S2 + E4 – E5 = 1 , , , , , , with . S2 + E5 ≥ 1 or S2 + E5 – E6 = 1 , , , , , , , with . S2 + E6 ≥ 1 or S2 + E6 – E7 = 1 , , , , , , , , with . S2 + E7 ≥ 1 or S2 + E7 – E8 = 1 , , , , , , , , , with . S2 + E8 ≥ 1 or S2 + E8 – E9 = 1 , , , , , , , , , , with . S2 + E9 ≥ 1 or S2 + E9 – E10 = 1   , , , , with (optimal all-integer solution)