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 [EMAIL PROTECTED] "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." _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
