Homepage of Boris Haase

Previous | Next

#63: Completion Introduction and Mathematics and Improvement Linear Programming on 15.04.2015

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 {cTx : Ax ≤ b, c, x ∈ cn, b ∈ cm, A ∈ cm×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 {b1, ..., bm}| and as in the first case with x := 0. A suitable pivot step moreover achieves b ≥ 0.

Let be i, j, k ∈ ℕ* and aiT the i-th row vector of A. First, we check whether the objective function cTx is unbounded positive. Sufficient for this is if it has at least one coefficient cj > 0 for that we have aij ≤ 0 for all aij. We should replace all cj resp. aij and bi by cj/||cj|| resp. aij/||ai|| and bi/||ai||. We can in each step remove multiple constraints and such with ai ≤ 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 bi = 0 and ai ≥ 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 cj > 0 and non-base variables xj a minimal quotient bk/akj for aij > 0. The variables with * are the ones of each next step. Then xj* = xj + bk/akj is the potential next vertex, with always feasible x*.

If we have cj ≤ 0 for all j, we solved the LP. Choosing steepest edge, the akj is the pivot concerning xj among them that maximises cT(x* - x)/||x* - x|| resp. cj2/(s + Σ aij2) in the k-th constraint as best possible direction. Here i attains only k and indices of bi in the tableau that correspond to base variables, but does not do so to slack variables. We have s = 1 (else 0) if xj* 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 cjbk/akj or of the smallest angle min Σ cj*/||c*||, equivalent to that. If more than n bi are 0 and if we cannot maximise the objective function directly, we treat the constraints with bi = 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 bi = ||ai|| here.

A division by the greatest coefficient of the constraint may avoid that bi becomes too big. We can store the scaling of the bi (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 ||ai|| to the bi 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 cj = 0. The objective function increases (quasi) strictly monotonically on the path passed. Afterwards we can easily calculate cj*, aij* and bi* 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 ∈ cn with rj = 0 für cj < 0 or max xj = 0 and cj at (|ℕ|, ..., |ℕ|)T ∈ ℝn as s ∈ cn and set x* := x + y r + z s sj := 0 for max xj = 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 ∈ cn with t ∈ c≥0, e ∈ cn, e ≥ 0, ej := 0 for max xj = 0, ej := -h cj for cj < 0 und ej := cj else and h as quotient of Σ cj2 for cj > 0 and Σ cj2 for cj < 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 cTv = cTx. We set temporarily for w ∈ cn, w ≥ 0, wj := 0, vj := 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 cj* ≤ 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 ∈ cn, p, q ≥ 0 and pj := qj := 0 for max xj = 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

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