Optimization Methods - Recitation 4

Recitation 4 1 Sensitivity Analysis Exerise 5.7 BT Solve the problem with b1 = 300, 000, b2 = 240, 000, and b3 = 30, 000. Solution x1 : number of pads produced, x2 : number of small notebooks produced, and x3 : number of large notebooks produced. The problem can be formulated as follows min s.t. −0.2x1 + 0.1x2 − 0.7x3 x1 + 2x2 + 3x3 ≤ b1 x1 + 1.75x2 + 2.5x3 ≤ b2 x2 + 3x3 ≤ b3 −x1 + 5x2 + 20x3 ≤ 0 x1 , x2 , x3 ≥ 0 Introducing four slack variables and we have the initial tableau 0 −0.2 0.1 −0.7 0 0 0 0 1 2 3 1 0 0 0 x4 = 300 1 1.75 2.5 0 1 0 0 x5 = 240 0 1 3 0 0 1 0 x6 = 80 −1 5 20 0 0 0 1 x7 = 0 The final tableau is 50 x1 = 215 x3 = 10 x4 = 55 x7 = 15 0 1.55/3 0 0 0.2 0.2/3 0 1 2.75/3 0 0 1 −2.5/3 0 0 1/3 1 0 0 1/3 0 0 0.25/3 0 1 −1 −0.5/3 0 0 −0.75 0 0 1 −7.5 1 With these two tableaux, we can do various sensitivity analyses. 2 Column Generation Method Given a linear programming problem in standard form min c
x s.t. Ax = b x≥0 1 The number of variables (number of columns of A) is very large and we cannot to store the matrix in memory. The idea of column generation is used to solve problems of this kind. Fact: The optimal basic solution of a linear programming problem in standard form has at most m variables with positive values, where m is the number of rows of the matrix A. In order to find the optimal solution, we just need to find these m basic variables. Idea: Starting with a small number of variables and introducing (or replacing) new variables when needed. In each iteration of column generation method, we will solve a linear programming problem of the kind min c
I xI s.t. AI xI = b xI ≥ 0 I is the set of all variables indices we have so far, |I| ≥ m. How to check optimality? The optimality condition is cj − c
B B −1 Aj ≥ 0 for all non basic variables or cj − p
Aj ≥ 0. However, we do not have the information of all columns Aj . What can we do? If we can find the minimum value minj cj − p
Aj , all problems are solved. If this value is nonnegative, we have the optimal solution and we can stop. If this minimum value is negative, we add the corresponding variable index j ∗ into the index set I and continue with another iteration of the column generation method. How to find the minimum reduced cost? The answer depends on the structure of the problem. We have to know properties of the columns Aj in order to formulate the minimization problem minj cj − p
Aj . Example There are n machines and m jobs that need to be done. Each job has a different start and end time, and a delay limit. At any time, one machine can only process one job. The setup time depends on the job sequence on each machine. The objective is to minimize the total delay. Formulate the problem in such a way that the column generation method can be used. Solution The problem can be formulated as follows �m � minz(S) f (S)zi (S) �mi=1� S∈Ri i s.t. i=1� S∈Ri ,j∈S zi (S) = 1 S∈Ri zi (S) ≤ 1 zi (S) ∈ {1, 0} � The reduced cost for a job sequence S of the machine i is ci (S) = fi (S) − j∈S πj − ri . It turns out that the problem to minimize the job sequence reduced cost � for a machine i is an instance of the original problem with one machine and modified cost fi (S) − j∈S πj . This problem is an integer problem and we need some heuristics to find a good solution for it within a reasonable time. 2