Simplex Algorithm

[sirooseven7]

Is it possible for a Simplex Algorithm to reach a solution that does not meet all of the constraints?

[Guest]

The constraints may in general not be mathematically satisfiable e.g. [tex]x>2[/tex] and [tex]x<1[/tex]. This is why the simplex algorithm sometimes uses 2 phases. In phase 1 we try to find a solution that satisfies the constraints (but may not be optimal). (In phase 2 we try to optimize the solution according to the objective function.)

Assuming there is a solution (that is not necessarily optimal), if your algorithm runs with "perfect precision" then the simplex algorithm will either:
a) terminate with a correct optimal solution (it may not be unique)
b) terminate after determining the solution is unbounded (e.g. maximize [tex]x[/tex] under the constraints [tex]x>0[/tex])
c) not terminate (if you choose your pivoting rules carefully this situation can be avoided).

Of course in reality perfect precision is usually not realistic. If instead of the decimal 0.75 you use the fraction 3/4, and your program stores the integer numerator 3 and denominator 4 internally instead of the float 0.75, you can eliminate rounding errors, and achieve perfect precision. However, as the calculation progresses the fractions become more complicated and the integers being stored will become larger and larger, eventually making your program impractically slow (in my experience your program gets exponentially slower as your problem size increases). So either you limit yourself to very small linear programs, or you use floating point numbers and deal with rounding errors.

When you have rounding errors you can end up in the situation where one of the rows looks like [tex]0.001x_1+0.0005x_2 = 0.0003[/tex], now your program has to make a decision: are the coefficients non-zero or are they really zero with some rounding error? This could affect where you pivot and the solution you end up with. If you incorrectly decide they are really all zeroes then you will have essentially accidentally ignored a constraint, and your final solution won't satisfy all the constraints. If you incorrectly decide they are not zeros, you will have introduced a constraint that will mean your solution is suboptimal or even unfeasible. Worse still what if some of the coefficients are zero but some aren't and you haven't correctly guessed which are which (maybe 0.001 is really 0 with very high rounding errors and 0.0005 is not 0 (even though it is smaller than 0.001)). In this case you could end up with a suboptimal / superoptimal / unbounded / unfeasible solution which may or may not satisfy the constraints (anything could happen).

Even if you guess the zeros correctly at each stage, your solution will only satisfy the constraints to some tolerance. For example maximize [tex]x[/tex] such that [tex]3x=1[/tex]. Clearly the solution is [tex]x=1/3[/tex], however in double precision floating point it is impossible to represent [tex]1/3[/tex] exactly, the best we can do is [tex]0.3333333333333333148[/tex] which doesn't satisfy the constraints but is pretty close. What if instead I asked to maximize [tex]30000000000000000000x-10000000000000000000[/tex] such that [tex]3x=1[/tex], given the rounding error in [tex]x[/tex], the optimal objective value will come out as something like [tex]-556[/tex] instead of [tex]0[/tex]. (Generally rounding errors can accumulate and scale as one equation gets substituted into another, meaning our constraints could be very badly unsatisfied by the end of the calculation.)

In general you can't hope to get an exact answer using floating point but by choosing a higher precision format say quadruple-precision floats you can make your solution more accurate and lessen the amount the constraints are unsatisfied. (Of course you pay for higher precision by having your program consume more time and memory.)

In general dealing with rounding errors can be very tricky, and a lot of people have devoted a lot of thought and effort to try to come up with algorithms that minimize the effects or at least quantify how bad the effects are for certain algorithms. Making robust algorithms that use floating point isn't easy.

Hope this helped,

R. Baber.

[Guest]

Short answer: In theory No, in practice Yes.

Computing with higher precision makes it less likely for the constraints to be badly unsatisfied.

R. Baber.