[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Working with larger numbers
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] Working with larger numbers |
Date: |
Tue, 29 Jul 2008 13:04:59 -0500 (CDT) |
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."
- Re: [Help-glpk] Working with larger numbers, (continued)
- Re: [Help-glpk] Working with larger numbers, Andrew Makhorin, 2008/07/28
- Re: [Help-glpk] Working with larger numbers, Markus Pilz, 2008/07/29
- Re: [Help-glpk] Working with larger numbers, Andrew Makhorin, 2008/07/29
- Re: [Help-glpk] Working with larger numbers, Michael Hennebry, 2008/07/29
- Re: [Help-glpk] Working with larger numbers, Andrew Makhorin, 2008/07/29
- Re: [Help-glpk] Working with larger numbers,
Michael Hennebry <=
- Re: [Help-glpk] Working with larger numbers, Markus Pilz, 2008/07/29
- Re: [Help-glpk] Working with larger numbers, Michael Hennebry, 2008/07/29