Re: [Help-glpk] financial compensation

[Robbie Morrison]

Hello Zvonko

If I am not mistaken, you could also set this up as a
minimum cost flow problem:

  http://en.wikipedia.org/wiki/Minimum_cost_flow

The solver will remove all redundant flows, even when
these flows are allocated zero cost -- as they would in
your case (if not, then these costs would represent
"transactions costs" and we have shifted to the
economic "theory of the firm", I guess).  There are
specialist algorithms for doing this, although the
problem can also be converted to a standard LP and
solved with simplex.  Xypron earlier described this
LP formulation.

GLPK also offers these special solvers, see:

  http://en.wikibooks.org/wiki/GLPK/Literature#Official_GLPK_documentation

and in particular, the "GLPK graph and network
routines" manual.

One rather succinct book I found helpful in crossing
between these differing formulations is:

  Derigs, Ulrich.  1988.  Programming in networks and
      graphs : on the combinatorial background and
      near-equivalence of network flow and matching
      algorithms.  Berlin, Germany : Springer Verlag.
      ISBN 3-540-18969-6

HTH, Robbie

------------------------------------------------------------
To:           Zvonko Bregar <address@hidden>, address@hidden
Subject:      Re: [Help-glpk] financial compensation
Message-ID:  <address@hidden>
From:        "glpk xypron" <address@hidden>
Date:         Wed, 05 Sep 2012 16:53:28 +0200
------------------------------------------------------------

> this is a pure LP problem:
>
> [snip: model formulation]
>
> -------- 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

---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Institute for Energy Engineering (IET)
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]