Test cases for slow simplex ? Klee-Minty cube, scaling

[denis]

'm looking for smallish test cases for which the simplex algorithm is slow, preferably AMPL.
I gather that the [Klee-Minty cube](https://en.wikipedia.org/wiki/Klee-Minty_cube)
is bad theoretically -- 2^D vertices for `A` D x D --
but cplex runs D=100 in ~ 0 seconds.
Can anyone point me to other LP problems that run slowly in student AMPL,
simplex or interior-point, not MIP ?

(Klee-Minty is so badly scaled, `xopt` 0 ... 0 5^D`,
that several of the solvers in student AMPL fail e.g. with max 0.
Maybe I missed options to prescale ? grep scal doc/README* -> only cplex minos xpress.)

Add this to your collection of silly corner cases:

    # Klee-Minty-cube.mod  see https://en.wikipedia.org/wiki/Klee-Minty_cube
    # D vars, D constraints, 2^D vertices => slow simplex ?
    # badly scaled, xopt 0 .. 0 5^D => numerical problems for some solvers

    param D default 100;
    set I := {1 .. D};
    set J := {1 .. D};

    param b{i in I} := 5. ^ i;
    param c{j in J} := 2. ^ (D - j);
    param A{ i in I, j in J } =
            if i < j then 0  else
            if i == j then 1
            else 2. ^ (i - j + 1);  # lower diagonals 4 8 ...
    # scale A ?

    #...............................................................................
    var x{J} >= 0;

    maximize z: sum {j in J}  c[j] * x[j];

    subject to rows {i in I}:
            sum {j in J}  A[i,j] * x[j] <= b[i];

    solve;

    printf "Klee-Minty-cube D=%d: max %g  x[D] %g  should both be 5^D := %g \n",
                            D, z, x[D], 5^D;

[AMPL Google Group]

I think you are looking for the following:

• A class of linear programs such that, for each number n, there is a member of the class "of size n".
• A widely used solver for which the number of iterations grows exponentially in n when applied to problems of the above class.

I don't know of any such example. The Klee-Minty example established that the number of iterations in the simplex method can increase exponentially for a certain problem class and a certain choice of entering variable. I believe that this example was extended to encompass a few other simple choices of entering variable as well. But widely used simplex solvers have much more complex entering (and leaving) variable criteria, so it's questionable whether bad cases of this kind can be devised for them.

Interior-point methods have a very different theory. For the complex versions used in popular solvers, exponential behavior is a possibility in theory, but again I don't know of any real examples.

There's a further complication that computers use floating-point rather than exact arithmetic, so that difficult examples may only be hard because they are numerically ill-conditioned, rather than due to any inefficiency in the underlying algorithm. You have seen this in the Klee-Minty example, when n gets sufficiently large: the range of coefficient magnitudes is so great that the problems cannot be solved accurately on a computer.

Finally, regarding scaling: AMPL does not provide any scaling; you must rely on each solver's scaling options, if any. In fact I would advise setting "option presolve 0;" so that AMPL does not try to make any changes to the problem before it goes to the solver.

--
Robert Fourer
am...@googlegroups.com

{#HS:1001349509-59902#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/70d6862b-03da-4e26-ae36-76e00fbf6c2a%40googlegroups.com.

[denis]

Thanks.

How about a contest for the slowest-running LP in student AMPL (nvar, nconstr < 500),

say between universities, say in cplex ?

While it would be difficult to stay clear of floating-point / numerical difficulties,

it might be fun

and might bring up an interesting problem or two.

Theory and practice are closer in theory than they are in practice.