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, this is opposed to the maximally quartic and strongly polynomial normal method as solution for the 9th Smale problem.

Theorem: The simplex method is not 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}} with aim z = 0, 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 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, 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*.

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}|c_{j}|/(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 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 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 therefore ||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.

The simplex method is not strongly polynomial, in the worst case, despite the diameter theorem for polytopes (see below), under all pivot rules, since 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, 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 is maximally quartic 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 moving better than along (the projections of) the normal vector of the objective function in the interior (and at the boundary) of the feasible domain onto the maximum. By this, the path is more effective determined than an optimal pivot rule without previous knowledge for the simplex method can be.

First, we solve the two-dimensional LP with x* := x + t c + (u, ..., u)^{T} ∈ ^{c}ℝ^{n} and t, u ∈ ^{c}ℝ_{≥0}. Being located at the boundary reduces the dimension of the LP. As variant, we set z := c^{T}x ∈ ^{c}ℝ_{≥0} and eliminate w. l. o. g. x_{1} with c_{1} ≠ 0. We solve now successively the LPs with x* := x + v e_{1} ± w_{j} e_{j}, v, w_{j} ∈ ^{c}ℝ_{≥0} and canonical unit vectors e_{j} ∈ ^{c}ℝ^{n} for all ±c_{j} > 0 as well as scalable w_{j}, which we keep then constant. We need not to increase all w_{j}.

As in the main method, we compute us successively into the next vertex along t c*. Doing so, it is now again linearly transformed to x = 0. If all c_{j} ≤ 0, x is optimal. We solve each two-dimensional LP by determining all p_{k} := c^{T}a_{i}/||a_{i}|| or -c_{j} > 0 and sorting them by size. We insert then a_{k}^{T}x* = b_{k} with the greatest p_{k} with p_{k} ∈ ^{c}ℝ_{≥0} into the other constraints and the objective function by solving for one x_{j}*.

If the one-dimensional LP, created by doing so, cannot be solved, we continue with the hyperplane of the next in size p_{k}, until the two-dimensional LP is solved, provided it does not turn out as unlimited. Each of the two-dimensional LPs can be solved in O(m^{2}). Finally we undo z := c^{T}x. We return to the full LP and everything repeats as the case may be. We treat multiple vertices as for the simplex method.

According to the theorem after next, we need with skipping of vertices maximally O(n) steps, since the problem has discrete transitions. To obtain the time complexity, we multiply by the factor O(m^{2}n) or, according to the next theorem, by O(mn^{2}) and from this the assertion follows. We can use various techniques of the simplex method like revision, decomposition, big M method and dual programming also here.

Theorem: The corresponding two-dimensional LP can be solved in maximally linear time.

Proof: If we have w. l. o. g. c_{1} < 0 and c_{2} ≤ 0, nothing must be shown. If we have c_{1}, c_{2} > 0, we seek the maximum along t (c_{1}, c_{2})^{T} with t ∈ ^{c}ℝ_{≥0}. If we have w. l. o. g. c_{1} > 0 and c_{2} ≤ 0, we determine first the maximum along (u, 0)^{T} and then along (v, v)^{T} with u, v ∈ ^{c}ℝ_{≥0}. We continue with the non-less one of the two values. Upper limits for x_{1} or x_{2} we determine by intersecting the a_{i}^{T}x = b_{i} among each other resp. if applicable the coordinate axes.

Constraints to straight lines out of the interior of the computed rectangle are redundant and can be removed. An LP transformed to max x_{1} we can solve by the bisection method. Since for uniform distribution per step in each case the half of the corresponding constraints is processed or else the logarithm of the greatest floating point number is relatively small on a computer in ^{c}ℝ_{>0}, the assertion follows.

Remark: Therewith also d-dimensional LPs with not to big d ∈ ^{c}ℕ* can be solved in maximally linear time, since several vertices can be skipped (in one direction). By this, the normal method becomes concurrent to the simplex method. If upper and lower limits are known for all x_{j}, we can remove the redundant constraints out of the corresponding cuboids analogously.

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}.

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

© 22.05.2016 by Boris Haase

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