Homepage of Boris Haase

Previous | Next

#65: Improvement Linear Programming on 22.05.2016

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 {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} with aim z = 0, in order to obtain 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, since it otherwise 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 the potential next vertex is given by xj* = xj + bk/akj, 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 values bi equal 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 therefore ||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.

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)Tcn and t, u ∈ c≥0. Being located at the boundary reduces the dimension of the LP. As variant, we set z := cTx ∈ c≥0 and eliminate w. l. o. g. x1 with c1 ≠ 0. We solve now successively the LPs with x* := x + v e1 wj ej, v, wjc≥0 and canonical unit vectors ejcn for all cj > 0 as well as scalable wj, which we keep then constant. We need not to increase all wj.

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 cj ≤ 0, x is optimal. We solve each two-dimensional LP by determining all pk := cTai/||ai|| or -cj > 0 and sorting them by size. We insert then akTx* = bk with the greatest pk with pkc≥0 into the other constraints and the objective function by solving for one xj*.

If the one-dimensional LP, created by doing so, cannot be solved, we continue with the hyperplane of the next in size pk, 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(m2). Finally we undo z := cTx. 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(m2n) or, according to the next theorem, by O(mn2) 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. c1 < 0 and c2 ≤ 0, nothing must be shown. If we have c1, c2 > 0, we seek the maximum along t (c1, c2)T with t ∈ c≥0. If we have w. l. o. g. c1 > 0 and c2 ≤ 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 x1 or x2 we determine by intersecting the aiTx = bi 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 x1 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 xj, 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

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