Re: [Help-glpk] financial compensation

[Jeffrey Kantor]

Hi Zvonko,

Here's an article concerning this particular application --
http://www.opf.slu.cz/vvr/akce/turecko/pdf/SLGazda.pdf

Jeff Kantor

On Wed, Sep 5, 2012 at 10:53 AM, glpk xypron <address@hidden> wrote:
> 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.
>>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk