On Tue, 29 Jul 2008, Markus Pilz wrote: > Andrew Makhorin wrote: > > 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?
I think it doesn't. If all you have are flow conservation equations and flow limits, integer data should give you an integer solution, even with floating point arthmetic. -- 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
