Re: [Help-glpk] financial compensation

[glpk xypron]

Hello Zvonko,

this is a pure LP problem:

# partners
set S;
# given flows;
set F, dimen 3;
# minimized flows
var f{S,S}, >=0;

minimize obj :
  sum{i in S, j in S} f[i,j];
  
s.t. c1{i in S} :
  sum{(j,i,x) in F} x - sum{(i,j,x) in F} x =
  sum{j in S} f[j,i]  - sum{j in S} f[i,j];

solve;

display f;

data;

set S := A B C;
set F :=
 A B 7000
 B C 5000
 C A 2000;
end;

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Wed, 5 Sep 2012 08:13:18 +0000
> Von: Zvonko Bregar <address@hidden>
> An: "address@hidden" <address@hidden>
> Betreff: [Help-glpk] financial compensation

> 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.
>