In the following, we concern solving linear programmes (LP). The well-known simplex algorithm and its problems in the worst case is introduced as no longer strongly polynomial and a method is presented, which leaves fast each problematic multiple vertex. Then, this is opposed to the maximally quintic and strongly polynomial normal method as solution for the 9th Smale problem.

Theorem: The simplex method is no longer strongly polynomial.

Proof and algorithm: Let max {c^{T}x : Ax ≤ b, c, x ∈ ^{c}ℝ^{n}, b ∈ ^{c}ℝ^{m}, A ∈ ^{c}ℝ^{m×n}, m, n ∈ ^{c}ℕ*} to be solved. If we dualise this LP or split x into a difference of two positive vectors, we get x ≥ 0. We solve first max {-z : Ax - (z, …, z)^{T} ≤ b, z ∈ ^{c}ℝ_{≥0}, rest as before} with aim z = 0 (required for a feasible x), if b ≥ 0 is not true. We start here with z := |min {b_{1}, ..., b_{m}}| and as in the first case with x := 0. A suitable pivot step moreover achieves b ≥ 0.

Let be i, j, k ∈ ℕ* and a_{i}^{T} the i-th row vector of A. First, we check whether the objective function c^{T}x is unbounded positive. Sufficient for this is if it has at least one coefficient c_{j} > 0 for that we have a_{ij} ≤ 0 for all a_{ij}. We should replace all c_{j} resp. a_{ij} and b_{i} by c_{j}/||c_{j}|| resp. a_{ij}/||a_{i}|| and b_{i}/||a_{i}||. We can in each step remove multiple constraints and such with a_{i} ≤ 0, since they are redundant (avoidable with a further slack variable each).

All applies analogously to the second case. If we have in both cases b_{i} = 0 and a_{i} ≥ 0 for an i, the LP has the maximum 0 and the solution x = 0, provided we have b ≥ 0 (otherwise it cannot be solved). In each step, we choose for each c_{j} > 0 and non-base variables x_{j} a minimal quotient b_{k}/a_{kj} for a_{ij} > 0. The variables with * are the ones of each next step. Then x_{j}* = x_{j} + b_{k}/a_{kj} is the potential next vertex, with always feasible x*.

If we have c_{j} ≤ 0 for all j, we solved the LP. Choosing steepest edge, the a_{kj} is the pivot concerning x_{j} among them that maximises c^{T}(x* - x)/||x* - x|| resp. c_{j}^{2}/(s + Σ a_{ij}^{2}) in the k-th constraint as best possible direction. Here i attains only k and indices of b_{i} in the tableau that correspond to base variables, but does not do so to slack variables. We have s = 1 (else 0) if x_{j}* represents there the increased non-base variable, but no slack variable.

If we have several maxima, we can use the pivot rule of the best value max c_{j}b_{k}/a_{kj} or of the smallest angle min Σ c_{j}*/||c*||, equivalent to that. If more than n b_{i} are 0 and if we cannot maximise the objective function directly, we treat the constraints with b_{i} = 0 are equally by relaxing (perturbing) them by the same, but minimal modulus. We need not to note this in the tableau itself: We simply set b_{i} = ||a_{i}|| here.

A division by the greatest coefficient of the constraint may avoid that b_{i} becomes too big. We can store the scaling of the b_{i} (with the divisor) separately. It is not very likely that multiple vertices occur afterwards again, before the multiple vertex is left, since enough linearly independent hyperplanes must exist to form then a new vertex: We add then ||a_{i}|| to the b_{i} stated above.

This ensures that the relaxed polytope of the LP alters structurally only minimally, so that we can assume quasi always a simple polytope without multiple vertices. We avoid so to be confronted with several minimal relaxations differing heavily that were, however, not chosen with respect to optimality aspects, as we have using the lexicographic method. Also Bland's rule is not optimal.

The effort to leave a multiple vertex, after what we undo the relaxations left, corresponds to the task to solve a LP with b = 0. This task can also occur finally, when we want to check whether there are further solutions of the LP, if we have at least two c_{j} = 0. The objective function increases (quasi) strictly monotonically on the path passed. Afterwards we can easily calculate c_{j}*, a_{ij}* and b_{i}* according to the rectangle rule.

Remark: The simplex method is not strongly polynomial, in the worst case, despite the diameter theorem for polytopes (see below), under all pivot rules, since most probably an exponential "drifting" through a polytope of the Klee-Minty or Jeroslow type or otherwise can be constructed that deviates immensely form the shortest path, according to existing proofs.

Theorem: The normal method is maximally quintic and moreover strongly polynomial.

Proof and algorithm: The normal method has the two phases of the simplex method, and determines the possible maximal value of the objective function by optimising it in differently chosen two- up to four-dimensional cutting hyperplanes of a cuboid in the feasible domain, in always different vertices, if possible. This has the advantage that it can skip, as the case may be, more vertices than the simplex method.

If the feasible domain does not contain only the maximum, we mirror r ∈ ^{c}ℝ^{n} with r_{j} = 0 für c_{j} < 0 or max x_{j} = 0 and c_{j} at (|ℕ|, ..., |ℕ|)^{T} ∈ ℝ^{n} as s ∈ ^{c}ℝ^{n} and set x* := x + y r + z s s_{j} := 0 for max x_{j} = 0. To obtain a feasible new x, we solve solve the new LP with now two variables y, z ∈ ^{c}ℝ_{≥0}. Thereafter we identify the scalar products of the normal vector of the objective function with the normalised normal vectors of the constraints and sort them by size.

Afterwards we sort them by size. We insert the expression for one variable from the corresponding hyperplane equation, with the greatest scalar product, into the other constraints and the objective function. If the one-dimensional LP cannot be solved, we continue with the hyperplane of the next greatest scalar product, until the two-dimensional LP is solved, if it does not turn out as unbounded.

Determining y and z has maximally quadratic time complexity, computing into a vertex totally maximally cubic and processing a cuboid is linear for linearly many cuboids. Instead of a two-dimensional linear programme, we can also formulate a more flexible three- or four-dimensional one, if any, with cutting hyperplanes in favourable directions (for instance in, for a long time, not explored ones). This has also maximally quadratic time complexity.

Then we determine successively an interim solution v := x + t e ∈ ^{c}ℝ^{n} with t ∈ ^{c}ℝ_{≥0}, e ∈ ^{c}ℝ^{n}, e ≥ 0, e_{j} := 0 for max x_{j} = 0, e_{j} := -h c_{j} for c_{j} < 0 und e_{j} := c_{j} else and h as quotient of Σ c_{j}^{2} for c_{j} > 0 and Σ c_{j}^{2} for c_{j} < 0, by now maximising t with e ≥ 0 so that v comes to lie at the other side of the polytope boundary. We replace then t in v ≥ 0 by t/2. It applies thus c^{T}v = c^{T}x. We set temporarily for w ∈ ^{c}ℝ^{n}, w ≥ 0, w_{j} := 0, v_{j} := y and x* := v + z w, for an alternating j.

We solve now the new LP with y, z ∈ ^{c}ℝ_{≥0}. If x* is optimal vertex, we are done. Otherwise we equalise the hyperplane just reached, store all replacements and maximise the nonnegative components of c* in it. If all c_{j}* ≤ 0, x* is optimal. Else we proceed as before. If we reach a vertex, we transform it to x* = 0.

Then we continue with the full stored LP. The hyperplanes left form the ones to be exchanged, the ones reached the ones to be changed into for each determination of the pivot element. Since maximally m hyperplanes or cuboids can separate the starting point from the aiming point and, after maximally linearly many steps, the surrounding cuboids of the path edges of the diameter are passed, the assertion follows.

Remarks: Computing a vertex (further away) compensates too short cuts. Thus the normal method is especially superior to the simplex method in unfavourable cases. Various simplex techniques like dual programming, decomposition and sparse arrays also make sense here. The combination with interior point methods can help to select a favourable direction (e.g. along the central path).

To improve the interim solution we can also optimise the four-dimensional LP proceeding similarly as in the main steps that results with p, q ∈ ^{c}ℝ^{n}, p, q ≥ 0 and p_{j} := q_{j} := 0 for max x_{j} = 0 from x* := x + v p + w q + y r + z s, with v, w, y, z ∈ ^{c}ℝ_{≥0} and linearly independent p, q, r, s with r and s as above. The time complexity of the algorithm remains here unchanged, since the solution of it needs maximally quadratic many steps.

It also remains unchanged, if we put s = 0. Let be d ∈ ^{c}ℕ* the dimension of the space to be considered. Then maximally d hyperplanes can build a vertex of a (maybe distorted) cube. If we complete the polytope by adding or cutting with further hyperplanes, we obtain the assertion for the path to be passed and the following theorem, since for the former maximally two further edges emerge in each case.

Diameter theorem for polytopes: A d-dimensional polytope given by n restrictions with d, n ∈ ^{c}ℕ* has a diameter of no more than max {2(n - d), 0}.

Prospect: Gomory resp. Lenstra cuts can determine an integer solution of the initially proposed problem in polynomial time, if we presuppose A, b and c w.l.o.g. additionally as integer and m resp. n as fixed. By determining redundant constraints and hyperplanes reached we can establish a full-dimensional LP. Hence, we have refuted that (mixed) integer linear programming is NP complete.

Theorem: (Mixed) integer LPs are polynomial.

code of simplex method and data file example

© 15.04.2015 by Boris Haase

• disclaimer • mail@boris-haase.de • pdf-version • bibliography • subjects • definitions • statistics • php-code • rss-feed • top