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 x_{1}, x_{2} and x_{3} as the number of books of the three types that are manufactured and sold. Also, define binary variables y_{1}, y_{2}, …, y_{5} that assume a value of one, if a machine is leased, and 0 otherwise. P: Max z = 40x_{1} + 60x_{2} + 70x_{3}

y_{1}, y_{2}, y_{3}, y_{4}, y_{5} = 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 x_{ij} to denote books of type i processed on machine j: P: Max z = 40x_{1} + 60x_{2} + 70x_{3}

x_{1}, x_{2}, x_{3}; x_{11}, x_{12}, …, x_{35} ≥ 0 and integer. The objective function has not changed. The first three constraints link x_{ij} and x_{i} 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.

4.2.5 Workload Balancing Goal: Distribute the workload evenly. Tasks cannot be split. Example: Processing times for worker-task combinations

T_{1}

T_{2}

T_{3}

T_{4}

T_{5}

W_{1}

5

1

9

4

9

W_{2}

4

3

8

3

8

W_{3}

7

5

6

4

7

Define variables y_{ij} = 1, if employee W_{i} is assigned to task T_{j}, and zero otherwise. Assign each task to exactly one employee. y_{1}_{j} + y_{2}_{j} + y_{3}_{j} = 1 for all j = 1, ..., 5. Actual working times of the employees: w_{1} = 5y_{11} + 1y_{12} + 9y_{13} + 4y_{14} + 9y_{15},

w_{3} = 7y_{31} + 5y_{32} + 6y_{33} + 4y_{34} + 7y_{35}, Possibility: Min z = max {w_{1}, w_{2}, w_{3}}. Rewrite as Min z, s.t. z ≥ w_{1}, z ≥ w_{2}, and z ≥ w_{3} + other constraints.

Min z s.t. z ≥ 5y_{11} + 1y_{12} + 9y_{13} + 4y_{14} + 9y_{15}

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 = y_{1} + y_{2}

s.t. 3y_{1} + 2y_{2} ≤ 6

y_{1} + 3y_{2} ≤ 3

y_{1}, y_{2} ≥ 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 5y_{1} + 10y_{2} ≤ 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 (n–m) variables. In case of primal degeneracy, the set N will include more than (n – m) variables, in which case we define N as any (n – m) 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 = 3y_{1} + 2y_{2} s.t. 3y_{1} + 7y_{2} 22

5y_{1} + 3y_{2} 17

y_{1} 2

y_{1}, y_{2} 0 and integer. Adding slack variables S_{1} and S_{2}and an excess variable E_{3}, we obtain the following formulation with n = 5 variables and m = 3 structural constraints: Max z = 3y_{1} + 2y_{2} s.t. 3y_{1} + 7y_{2} + S_{1} = 22

5y_{1} + 3y_{2} + S_{2} = 17

y_{1} – E_{3} = 2

y_{1}, y_{2}, S_{1}, S_{2}, E_{3} 0 and integer. The optimal solution is ,, , and with . Here, N = {S_{1}, S_{2}}, so that the Dantzig cut is S_{1} + S_{2} ≥ 1 (or 8y_{1} + 10y_{2} ≤ 38). Subtracting a new excess variable E_{4} from the left-hand side of this cut, we obtain S_{1} + S_{2} – E_{4} = 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).