Re: [Help-glpk] Working with larger numbers

[Markus Pilz]

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.
> 
>> If glpk floating point gives you the correct basis,
>> glpk exact should give you the exact answer in fairly short order.
>> So long as the glpk floating point basis is near-optimal and feasible,
>> a subsequent call to glok exact should be fairly quick.
> 
> 
> 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.
> 

Yes, I expect the mentioned integral solutions as arc capacities are
integral.

The min cost flow is described as minimum cost circulation. Does this
formulation contain the "additional constraints" you mention?

(And of course, I have to check the code that prepares the constraint
matrix.)

Regards
Markus

-- 
______________________________________________________________________
Markus Pilz                          University of Bonn
                                     Institute of Computer Science IV
E-Mail: address@hidden          Roemerstrasse 164
Tel.:   +49 228 73-4549              53117 Bonn
Fax.:   +49 228 73-4571              Germany