Bland's Rule

Bland’s rule When selecting pivot variables, always select the candidate with the smallest index (e.g., select x2 over x4). Then cycling cannot occur and the simplex algorithm terminates. 1 Using Anti-cycling rules We only need to use Blands rule in degenerate situations. If the value of z increases, we are not in a cycle and can pivot in any way we want. 2 Some pivoting rules to consider in non-degenerate case • Largest coefficient rule: Let the variable with the largest coefficient in z enter the basis. • Largest increase rule: Let the variable which will bring about the largest increase in z enter the basis. • . . . 3 Local Search - To do list 1. How to find first feasible solution. Done for origo-feasible case. 2. Define neigborhood structure. Done. 3. Strategy for choosing neighbor. Done. 4. Partial correctness (Terminatation ⇒ Correctness). Done. 5. Termination. Done. 6. Complexity. 4 Solving non-origo feasible standard instances Maximize ∑n j=1 cjxj subject to n∑ j=1 aijxj ≤ bi, i = 1, 2, . . . , m xj ≥ 0, j = 1, 2, . . . , n Assume b1 < 0 and ∀i : b1 ≤ bi. Generate Auxillary Program: Minimize x0 subject to ( n∑ j=1 aijxj)− x0 ≤ bi, i = 1, 2, . . . , m xj ≥ 0, j = 0, 1, 2, . . . , n 5 Maximize −x0 subject to ( n∑ j=1 aijxj)− x0 ≤ bi, i = 1, 2, . . . , m xj ≥ 0, j = 0, 1, 2, . . . , n Crucial property: The auxillary instance has optimal value x0 = 0 iff the original instance is feasible. If so, a solution with this value is also a feasible solution to the original instance. A feasible solution for the auxillary instance is • x0 = −b1, • x1 = x2 = · · · = xn = 0. 6 Dictionary for auxillary instance xn+i = bi − n∑ j=1 aijxj + x0, i = 1, . . . , m w = −x0 Dictionary infeasible but pivoting on x0 and xn+1 yields dictionary corresponding to • x0 = −b1, • x1 = x2 = · · · = xn = xn+1 = 0 and with • xn+j = bj − b1 ≥ 0 for j ≥ 2. 7 The two-phase simplex algorithm Apply the simplex algorithm to the auxillary instance. If optimal solution has value w < 0, the orginal instance is INFEASIBLE. If optimal solution has value w = −x0 = 0, the solution is a solution to the original instance. The variable x0 must be non-basic (if Bland’s rule was used). Removing the variable x0 from the dictionary yields a feasible dictionary for the original instance, because.. 8 Final dictionary for auxillary instance xi = bi − ∑ j a¯ijxj + αix0, i ∈ B equivalent to ( n∑ j=1 aijxj)− x0 ≤ bi, i = 1, 2, . . . , m 9 Restricting to x0 = 0: xi = bi − ∑ j a¯ijxj , i ∈ B equivalent to n∑ j=1 aijxj ≤ bi, i = 1, 2, . . . , m 10 Fundamental theorem of linear programming For every linear program in standard form: 1. If it has no optimal solution, it is either infeasible or unbounded. 2. If it has a feasible solution, then it has a basic feasible solution. 3. If it has an optimal solution, then it has a basic optimal solution. Proof: The two-phase simplex algorithm! 11 Complexity Complexity of Local search ≈ Time for one improve × Number of improve steps. 12 Pivot method Pivot: Identify variable xi and xj to switch place. Rewrite expression for xj as an expression for xi; Substitute this expression for xi in all other equations in D; Return resulting system of equations. 13 Time for one improvement Assume dictionaries represented as arrays. Identify the variable xi to enter the basis: Time O(n). Identify the variable xj to leave the basis: Time O(m). Rewrite equation for xj to equation for xi: Time O(n). Substitute equation for xi everywhere: Time O(nm). 14 A Catch! 51251253262362354532452352623 113236236236236236236236236236 vs. 4.861616365 ... will be resolved later. 15 A Catch! 51251253262362354532452352623 113236236236236236236236236236 vs. 4.861616365 ... will be resolved later. 15-a Number of improve steps Number of improve steps ≤ Number of possible feasible dictionaries ≤ Number of possible partitions into basic/non-basic variables = ( m + n m ) = ( m + n n ) Exponential in m og n! 16 Assume m = n = 50. If we actually have to go through ( 100 50 ) pivotings on a GigaHertz computer with 109 pivotings per second, how long time will it take us to terminate? 4000 billion years! 17 Assume m = n = 50. If we actually have to go through ( 100 50 ) pivotings on a GigaHertz computer with 109 pivotings per second, how long time will it take us to terminate? 4000 billion years! 17-a Harmlessness revisited Suppose a reduction to a special case (made for convenience) blows up the input size by a factor of 2. 225 ns = 34 ms. 250 ns = 13 days. 2100 ns = 40000 billion years. For exponential algorithms, harmless restrictions may not be so harmless 18 Harmlessness revisited Suppose a reduction to a special case (made for convenience) blows up the input size by a factor of 2. 225 ns = 34 ms. 250 ns = 13 days. 2100 ns = 40000 billion years. For exponential algorithms, harmless restrictions may not be so harmless 18-a Can we find much better upper bounds? Klee-Minty examples: When we choose the variable with the largest coefficient to enter the basis (largest coefficient rule), we may go through 2n − 1 iterations (Exercises). Bland rule: More complicated examples show similar behavior. Other rules: More complicated examples show similar behavior. Is there some pivot rule that will yield a polynomial upper bound on the number of iterations? This is an open problem! 19 Can we find much better upper bounds? Klee-Minty examples: When we choose the variable with the largest coefficient to enter the basis (largest coefficient rule), we may go through 2n − 1 iterations (Exercises). Bland rule: More complicated examples show similar behavior. Other rules: More complicated examples show similar behavior. Is there some pivot rule that will yield a polynomial upper bound on the number of iterations? This is an open problem! 19-a Simplex algorithm in Practice Countless experimental reports: For “natural” instances more than m log2 n iterations is rare. In other words, the simplex algorithm is efficient on most “natural” instances. In practice, an implicit representation of dictionaries is used (revised simplex algorithm). 20 Chvatal (1983): Even though [asymptotic worst case complexity] does reflect to some extent the reasons why practitioners are satisfied by some algorithms and unsatisfied by others, it fails to capture these reasons fully. 21 Theoretical Result(s) Let Dm,n be a “suitable” probability distribution on LP-instances with parameter m, n. Then, if the instance is drawn at random from Dm,n, the expected number of iterations is polynomial in n, m. Thus, the simplex algorithm has good average case complexity. 22 A Theoretical Conjecture Random pivot rule: When selecting pivot variables, select a random one among the candidates. Randomized Simplex Algorithm: Simplex algorithm using the random pivot rule. Conjeture: For all instances it holds if pivotings are done using the random pivot rule, the expected number of iterations performed by the simplex algorithm is polynomial. This is one of the most important open problems in the theory of Linear Programming. 23 A Theoretical Conjecture Random pivot rule: When selecting pivot variables, select a random one among the candidates. Randomized Simplex Algorithm: Simplex algorithm using the random pivot rule. Conjeture: For all instances it holds if pivotings are done using the random pivot rule, the expected number of iterations performed by the simplex algorithm is polynomial. This is one of the most important open problems in the theory of Linear Programming. 23-a