RE: [Fwd: Discussion on GLPK]

[Michael Hennebry]

I expect that 50 million wss not quite arbitrary.
If GLPK runs out of real RAM,
'twill become grindingly slow running from swap.
Even with enough RAM, the time required is superlinear in problem size.

On Tue, 19 Apr 2022, Meketon, Marc wrote:

> Typically when I see that many coefficients, it suggests that you need to 
> reformulate your problem.

+1

That said, if you must:

Use the API.
Start with a subset of the constraints.
Include variable bounds and equalities.
repeat
    Solve the reduced problem.
    If all constraints are satisfied:
        done
    Add a violated constraint
forever

Major details are left as an exercise for the reader.


My guess is that this is the fastest solution.
Another possibility is to recompile GLPK with a larger limit.
My guess is that you will discover that 50 million was not a bad choice.

Yet another possibility for the skilled, brave or foolish
programmer is to rewrite GLPK to use mostly floats.
Simple variables and 1D array can still be doubles,
but 2D arrays become arrays of floats.
'Tain't just a matter of changing types.
Some thresholds will need to be changed.
Arithmetic should probably be done with double intermediates.
Also, GLPK is written in C89.
It's been a long time since I looked at the GLPK code.
I'm not sure what if anything GLPK does to deal with some of the
more interesting things some platforms do with floating point arithmetic.
Some platforms use long doubles for all floating point temporaries.
Often that just adds to the accuracy.
Sometimes the result is double rounding.
When done badly, as in the case of at least some versions of gcc,
one can get truly anomalous results: values that, according to the C,
are computed identically turn out to be unequal.
C99 introduced the types float_t and double_t
to help deal with the situation.
If you want to use them, you will need to use at least C99
or define float_t and double_t as part of your configuration.

BTW I've been assuming that the problem is a pure LP.
If it's an integer problem, lots of luck.
Reformulation would really seem to be in order.

--
Michael   hennebry@web.cs.ndsu.NoDak.edu
"Well, before my sword can pass all the way through your neck, it has
to pass *half way* through your neck. But before it can do *that*, it
has to first pass *one-fourth* of the way through your neck. And
before it can do *that*...."  -- Ray Radlein quoting Zeno, Warrior Princess