[Lemon-user] Using NetworkSimplex Algorithm
Kovács Péter
kpeter at inf.elte.hu
Thu Jul 18 15:39:34 CEST 2013
Hi All,
Theoretically, NetworkSimplex could support non-integer input data, but
it would require careful modifications to avoid potential issues related
to inexact computations. We did not implement this feature yet, but only
for technical reasons and lack of time.
On the other hand, CapacityScaling algorithm already supports
non-integer arc costs (although it is usually slower than
NetworkSimplex), but other data (supply, capacity, flow) should be
integer-valued.
Here is an issue about this topic:
http://lemon.cs.elte.hu/trac/lemon/ticket/261
Regards,
Peter
On 2013.07.18. 14:44, Matthew Galati wrote:
> What part of the network simplex implementation fails if you use double
> data type instead of integer? Theoretically, you lose the guarantee that
> the output (flows) are integer. But, do you lose correctness?
>
> Scaling can be difficult to maintain accuracy as you must keep all your
> input below INT_MAX to use integer types. You also then have to worry
> about overflow issues.
>
>
> On Wed, Jul 17, 2013 at 9:43 AM, Kovács Péter <kpeter at inf.elte.hu
> <mailto:kpeter at inf.elte.hu>> wrote:
>
> Hi Heba,
>
> The min cost flow algorithms currently do not support fractional
> input data. There is a warning about that on the doc page of
> NetworkSimplex as well:
> lemon.cs.elte.hu/pub/doc/1.2.__3/a00231.html
> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html>
>
> Have you tried your example scaling up all supply values by a factor
> of 2? It should provide correct results.
>
> In general, you can always find a suitable scaling factor to convert
> the supply values to integers. And this factor can also be used to
> convert the flow values back in order to obtain a fractional
> solution for the original problem.
>
> Best regards,
> Peter
>
>
>
> On 2013.07.17. 14 <tel:2013.07.17.%2014>:03, T.A. Heba Essam wrote:
>
> Dears,
>
> 1- For the supply map in network simplex algorithm, can it
> accept fractional numbers?
>
> I'm having the attached problem and my first guess is (maybe
> fractions are rounded up leading to unbalanced supply and demand
> values). Kindly have a look.
>
> Best regards,
> Heba
> __________________________________________
> From: Kovács Péter [kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>]
> Sent: Sunday, June 23, 2013 2:28 PM
> To: T.A. Heba Essam
> Cc: lemon-user at lemon.cs.elte.hu <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>
> Hi Heba,
>
> Dear all,
>
> The first question is more of a theoritical one,
>
> 1- Is there a way to avoid that a supply value of a node
> doesn't get splitted into two arcs?
> I mean, any settings for capacity values or graph
> formation to achieve that?
>
>
> In general, this requirement leads to a "unsplittable flow" problem,
> which cannot be transformed to the standard min cost flow
> problem. It is
> actually a much harder, NP-complete problem. See e.g.:
> http://www.redaktion.tu-__berlin.de/fileadmin/i26/__download/AG_DiskAlg/FG___KombOptGraphAlg/preprints/__2000/Report-685-2000.pdf
> <http://www.redaktion.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/preprints/2000/Report-685-2000.pdf>
>
> In a special case, when all supply values are the same, there is a
> trivial transformation: scaling down all capacity and supply/demand
> values by this value so as to have 1 as supply value at each supply
> node. However, the general case cannot be handled this way.
>
> 2- Can't I get an arc length in Lemon? unless I'm previously
> defining a length map for it?
>
>
> No, you can't. In LEMON, graph nodes and arcs cannot store any
> attached
> value (length, label, color etc.), maps should be used for all such
> purposes.
>
> Regards,
> Peter
>
>
> __________________________________________
> From: Kovács Péter [kpeter at inf.elte.hu
> <mailto:kpeter at inf.elte.hu>]
> Sent: Wednesday, June 19, 2013 10:08 PM
> To: T.A. Heba Essam
> Cc: lemon-user at lemon.cs.elte.hu
> <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>
> Hi Heba,
>
> Dears,
>
> For a minimum cost flow problem, can the network simplex
> algorithm gives information about nodes movement. I.e.
> n1 goes to n2 goes to n3 & n5 -> n6 -> n7...etc?
>
> - Is it the flowmap or potentialmap data member? and,
>
> - How it can be interpreted/accessed, please?
>
>
> The flow map provides the information you are looking for.
> Although it
> is a bit more complex stuff than paths. You could check the
> documentation here:
> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00005.html
> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00005.html>
>
> The (primal) solution of the problem is the flow function
> (map) that
> associates a flow value with each arc of the graph (which is
> between the
> lower and upper bounds given for that arc). This function is
> denoted as
> f in the above doc and can be accessed using either the
> flow() or the
> flowMap() function of NetworkSimplex (after running the
> algorithm):
> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00231.html
> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00231.html>
>
> For Dijkstra's algorithm, I used "dijkstra(dijGraph,
> length).run(source, target);"
>
> - Does "path" gives me the shortest path between source
> & target? and,
> - "dist" gives me the shortst path distance between them?
>
>
> Yes.
>
> as I see in the documenation that "path" and "dist"
> takes a variable "node" and calculate it to the root.
> What about having a specific source and target nodes?
>
>
> In the following example:
> bool reached = dijkstra(g, length).path(p).dist(d).run(s, t);
>
> The results are obtained as follows: the return value
> indicates if a
> directed path can be found from s to t; p is a Path
> structure in which a
> shortest s->t path will be copied; d is a number type
> variable (e.g. int
> or double), which will be set to the shortest path distance
> of s and t.
>
> Note that there are two interfaces for using Dijsktra: a
> simpler,
> function-type interface:
> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00531.html#__ga6aa57523fe00e2b8fe2f5cd17dd1__5cea
> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00531.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>
> and a class interface:
> http://lemon.cs.elte.hu/pub/__doc/1.2.3/a00110.html
> <http://lemon.cs.elte.hu/pub/doc/1.2.3/a00110.html>
>
> It seems that you used the former one, so I wrote about this
> solution,
> but the path(Node), dist(Node) functions are for the
> class-type interface.
>
> Regards,
> Peter
>
>
> Thanks a lot,
> Heba
>
>
>
> __________________________________________
> From: Alpár Jüttner [alpar.juttner at gmail.com
> <mailto:alpar.juttner at gmail.com>] on behalf of Alpar
> Juttner [alpar at cs.elte.hu <mailto:alpar at cs.elte.hu>]
> Sent: Friday, June 14, 2013 3:03 PM
> To: T.A. Heba Essam
> Cc: Kovács Péter; lemon-user at lemon.cs.elte.hu
> <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>
> On Thu, 2013-06-13 at 11:46 +0000, T.A. Heba Essam wrote:
>
> Dear Alpar,
>
> I tried so many alternatives, the only thing that
> compiles for me is
> your piece of advice of including header files of
> lemon before VS ones.
>
>
> That's great. I still highly recommend isolating (direct
> or indirect)
> any use of windows.h (or any other nasty headers) in
> dedicated object
> files.
>
> Regards,
> Alpar
>
>
>
> Thanks,
> Heba
> __________________________________________
> From: Alpár Jüttner [alpar.juttner at gmail.com
> <mailto:alpar.juttner at gmail.com>] on behalf of Alpar
> Juttner [alpar at cs.elte.hu <mailto:alpar at cs.elte.hu>]
> Sent: Wednesday, June 12, 2013 4:01 PM
> To: T.A. Heba Essam
> Cc: Kovács Péter; lemon-user at lemon.cs.elte.hu
> <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using NetworkSimplex Algorithm
>
> Hi,
>
> Well, I actually found out that many other
> "#include" cause the
> problem, not only stdafx.h :(
>
> Seems like it doesn't accept including files
> rather than lemon ones or
> else it gives compilation errors!! which I can't
> do as I'm using LEMON
> as a part of my project. Sounds weird, having no
> clue how this can be
> handled.
>
>
> LEMON should work seamlessly with _any_ correctly
> written header files,
> we put high emphasis on compatibility, and are very
> conservative to put
> nothing into the global namespace in order to avoid
> conflicts with other
> packages.
>
> Note that, however, the Visual Studio header files
> are _not_ written
> correctly. They are ridiculously badly designed and
> fails to follow even
> the most basic coding principles. For example
> windows.h has #define
> declarations (yes, #define not const values or
> enums) for random keyword
> such as "Arc", "IN" or "OUT". This means that you
> shoot yourself in the
> foot e.g. if the try to name class as "Arc" even if
> it is in your own
> namespace.
>
> It may help if you include the window header _after_
> the LEMON ones.
> Then it cannot overwrite LEMON's code with its
> stupid #define
> declarations. But it will still spoil your codes.
>
> The only safe solution is to completely avoid
> including windows.h (or
> using in separated .cc files only, see below),
> whether or not you use
> LEMON.
>
> mmmmm I may separate the Lemon usage parts in
> different simple files
> (where I won't need to include any external
> headers) and call them far
> from any other place within my project. Will try
> it and keep you
> updated.
>
>
> Why not do it the other way around? Put the guilty
> one in the prison,
> not every one else!
> Write wrapper functions for your windows.h calls and
> place them into a
> separate .cc.
>
> In fact, LEMON does the same internally, and does it
> for the very same
> reason. All Windows system call are placed in
> lemon/bits/windows.cc, and
> nowhere else do we use #include<windows.h>.
>
> See http://lemon.cs.elte.hu/trac/__lemon/ticket/215
> <http://lemon.cs.elte.hu/trac/lemon/ticket/215> for
> more details.
>
> Regards,
> Alpar
>
>
>
> Regards,
> Heba Essam
>
> __________________________________________
> From: Kovács Péter [kpeter at inf.elte.hu
> <mailto:kpeter at inf.elte.hu>]
> Sent: Wednesday, June 12, 2013 10:52 AM
> To: T.A. Heba Essam
> Cc: Alpar Juttner; lemon-user at lemon.cs.elte.hu
> <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using NetworkSimplex
> Algorithm
>
> Hi Heba,
>
> I checked your code example. Without #include
> "stdafx.h", it compiles
> and runs correctly for me using GCC compiler
> (well, INFINITE must be
> defined then, e.g. #define INFINITE 1000000).
>
> Therefore, the problem may be related to your
> stdafx.h or the compiler.
> Could you try compiling the code without
> including stdafx.h?
>
> Regards,
> Peter
>
>
> On 2013.06.12. 12 <tel:2013.06.12.%2012>:24,
> T.A. Heba Essam wrote:
>
> Thanks Alpar :)
>
> Then, I still hope if we can figure out the
> cause of these errors.
>
> Regards,
> Heba
> __________________________________________
> From: Alpár Jüttner [alpar.juttner at gmail.com
> <mailto:alpar.juttner at gmail.com>] on behalf
> of Alpar Juttner [alpar at cs.elte.hu
> <mailto:alpar at cs.elte.hu>]
> Sent: Wednesday, June 12, 2013 10:14 AM
> To: T.A. Heba Essam
> Cc: Kovács Péter;
> lemon-user at lemon.cs.elte.hu
> <mailto:lemon-user at lemon.cs.elte.hu>
> Subject: Re: [Lemon-user] Using
> NetworkSimplex Algorithm
>
> Hi,
>
> Note: as VS 2010 is 32-bit while LEMON
> is 64,
>
>
> There is nothing 64-bit specific in LEMON.
>
> can this cause the problem by any
> means?
>
>
> No, it cannot.
>
> Regards,
> Alpar
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> _________________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu <mailto:Lemon-user at lemon.cs.elte.hu>
> http://lemon.cs.elte.hu/__mailman/listinfo/lemon-user
> <http://lemon.cs.elte.hu/mailman/listinfo/lemon-user>
>
>
More information about the Lemon-user
mailing list