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

Theorem: The simplex method is not strongly polynomial.

Proof and algorithm: Let be M := {x ∈ ^{κ}ℝ^{n} : Ax ≤ b, b ∈ ^{κ}ℝ^{m}, A ∈ ^{κ}ℝ^{m×n}, m, n ∈ ^{κ}ℕ*} the feasible domain of the LP max {c^{T}x : c ∈ ^{κ}ℝ^{n}, x ∈ M}. If we dualise it or set x := x^{+} - x^{-} mit x^{+}, x^{-} ≥ 0, we get x ≥ 0. We solve first max {-z : Ax - ze ≤ b, z ∈ ^{κ}ℝ_{≥0}} with aim z = 0 and e = (1, ..., 1)^{T} ∈ ^{κ}ℝ^{m}, in order to obtain 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 achieves b ≥ 0.

Let be i, j, k ∈ ^{κ}ℕ* and a_{i}^{T} the i-th row vector of A. If we have c_{j} ≤ 0 for all j, the LP is solved. If there is a c_{j} > 0 for that we have a_{ij} ≤ 0 for all a_{ij}, the LP is unbounded. Otherwise, we divide all a_{i}^{T}x ≤ b_{i} by ||a_{i}|| and all c_{j} resp. a_{ij} by min |a_{ij}| for a_{ij} ≠ 0 per j. At the end, we undo the latter. We repeat the normalisation by ||a_{i}||. By this, we achieve a favourable behaviour of the runtime, also for severely deformed polytopes.

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, since it otherwise 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 the potential next vertex is given by x_{j}* = x_{j} + b_{k}/a_{kj}, with always feasible x*. 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}|c_{j}|/(1 + Σ a_{ij}^{2}) in the k-th constraint. 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 values b_{i} equal 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 factor. We need not to note this in the tableau itself: We simply set b_{i} = ||a_{i}||. If a multiple vertex occurs anew, although this is not very likely, we simply add ||a_{i}|| to the b_{i} just stated.

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.

The simplex method cannot prevent an exponential "drifting", since a polytope of the Klee-Minty or Jeroslow type or otherwise can be constructed that deviates immensely form the shortest path, because we are forced to choose in each case the less favourable edge. This is in accordance with existing proofs and it follows the assertion.⃞

Theorem: The normal method solves the LP maximally in O(mn) and is strongly polynomial.

Proof and algorithm: The normal method has the two phases of the simplex method and solves the LP, if possible, by moving in a direction computed from O(n) orthogonal normal directions in the interior of the feasible domain as main step onto the potential maximum. Hereby, we solve all two-dimensional LPs (per direction) in each case by bisection method in O(m). Beginning and treating multiple vertices compare to the simplex method.

We set the *height* h := c^{T}x and eliminate w. l. o. g. x_{1} with c_{1} > 0.. There is a conservative sub-procedure to be executed first for a dome-marginal maximum and an afterwards progressive one for a dome-central one. Then it follows again the conservative sub-procedure and so forth, until the maximum maybe is reached. We solve first the LPs max h_{j} in h_{j}, u ∈ ^{κ}ℝ_{≥0} for all j > 1 mit x* := (h_{j}, x_{2}, ..., x_{j-1}, u, x_{j+1}, ..., x_{n})^{T} and constant x_{k} for 1 ≠ k ≠ j.

We should maybe scale the x_{j}* > 0 to the same minimal value. We set then successively x_{j} := (max x_{j} + min x_{j})/2, until we could alter all x_{j} crucially. Otherwise, we relax the constraints minimally that x satisfies with equality and compute similarly a favourable direction r ∈ ^{κ}ℝ^{n}, in which we can leave x. We solve thereon again the LPs as above and continue afterwards progressively.

We compute then a favourable direction r ∈ ^{κ}ℝ^{n} with r_{j} := x_{j}h_{j}/max h_{j}. We solve the LP max h in ∈ ^{κ}ℝ_{≥0} with x* := x + (v, 0, ..., 0)^{T} + wr ∈ M. If we reach a predefined upper limit of h, we abort the procedure as unlimited. Since all main steps of complexity O(mn) in each case process h almost logarithmically, also to the base of 2, it follows their constant number, and thus the assertion, if the LP can be solved at all.⃞

Corollary: Each linear system (LS) Ax = b with x ∈ ^{κ}ℝ^{n} can be solved, if at all, maximally in O(mn).

Proof: We write Ax = b as Ax ≤ b and -Ax ≤ -b resp. x = x^{+} - x^{-} with x^{+}, x^{-} ≥ 0.⃞

Theorem: Each convex programme min {f_{1}(x) : x ∈ ^{κ}ℝ^{n}, x ≥ 0, (f_{2}(x), …, f_{m}(x))^{T} ≤ 0} with convex posynomials f_{i} ∈ ^{κ}ℝ is strongly polynomial and can be solved per normal and Newton's method, which processes the f_{i}, maximally in O(p), if it can be solved at all, p ∈ ^{κ}ℕ* specifies the number of operands x_{j} of the f_{i} and the objective function f_{1} is linearised.

Proof: The assertion follows from the normal method.⃞

Remarks: The normal method is presently the fastest known LS resp. LP algorithm and numerically very stable, since we alter the initial data hardly. It is also suitable for branch and bound, especially in the non-convex optimisation. We can parallelise the simplex and well the normal method. The transfer to convex programmes with vector-valued or other convex f_{i} is easily possible.

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

Proof: 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. The theorem can be transferred analogously to polyhedra if we only drop the finite constraint.⃞

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

© 04.10.2016 by Boris Haase

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