Re: [Help-glpk] Working with larger numbers

[Michael Hennebry]

On Tue, 29 Jul 2008, Andrew Makhorin wrote:

> > In a specialized single-commodity network flow solver,
> > the arithmetic is normally exact even if done in floating point.
>
> > That is usually not true with multi-commodity flows.


> I think that Markus obtains a solution, where some flows are
> non-integral while he expects them to be integral due to network
> structure and integral arc capacities (I mean max flow and min cost flow
> problems). On the other hand, it is unclear to me why this could happen,
> because the constraint matrix is an indicent matrix of the network, so
> the basis matrix being an incident matrix of the spanning tree is
> triangular and therefore its LU-factorization is trivial and should be
> exact even in floating-point arithmetic. I suspect that there are some
> additional constraints in the model.

If the reason is an additional constraint,
then the correct solution is probably fractional.
If integers are needed,
one could lagrangeanize the non-network-flow constraints.
The solution would be guaranteed integral,
but not necessarily optimal or feasible.
Artificially tightening constraints might help with feasibility.

Also, once one has a feasible solution,
it could be used as the starting point in a "trust region" algorithm.
Restate the problem in terms of the differences
between the solution and a starting point.
Artificially limit the differences.
The subproblem should have reasonable numbers.
If none of the artificial limits are reached, you might be done,
otherwise you have a new starting point.


-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."