[Help-glpk] financial compensation

[Zvonko Bregar]

Hello everyone,

I came across a certain combinatorial problem.

Of a mandatory debt compensation between firms.

The problem can be stated as:

You have a directed graph.

Each vortex presents a firm (a company).

Each (directed) link from A to B presents the money amount that the A-firm must pay to the B-firm.

And the problem is to reduce all the redundant cycles,

For example if A owes 7000 to B and B owes 5000 to C and C owes 2000 back to A then this cycle could be reduced by 2000 and the link between C and A becomes obsolete.

My question is whether or not this problem can be formulated as a mixed integer linear program.

If Yes, does it makes sense or it would be much better to apply some graph theory alghoritms for minimal trees, cycles etc.

If it does make sense to apply MILP please point me to the literature.

Thank you in advance

Zvonko

OPOZORILO: To elektronsko sporočilo in vse njegove morebitne priloge lahko vsebujejo zaupne in/ali privilegirane informacije, ki so last Elektroinštituta Milan Vidmar in so namenjene izključno naslovniku. Če ste sporočilo prejeli pomotoma zaradi napake v naslovu ali pri prenosu sporočila, Vas prosimo, da nas o tem obvestite s povratno pošto. V tem primeru vsebine prejetega sporočila ne smete uporabiti, kopirati, tiskati, objaviti ali distribuirati, ampak ga morate takoj uničiti.

DISCLAIMER: This e-mail is for the intended recipient only. It contains proprietary information some or all of which may be legally privileged. If you received this e-mail by mistake please notify us by replying to this e-mail. Consequently, the contents of this e-mail must be deleted and not be used, copied, printed, disclosed or distributed.