0

I'm trying to solve a transportation problem using the networkX library. As my demand and supply values are floats my problem seems to be unsolvable by the networkX package? see documentation on Page 377. https://networkx.org/documentation/stable/_downloads/networkx_reference.pdf

Is there any workaround? My problem results from rounding errors as my floats are really small.

are there any other libraries that support floating point numbers for solving minimum cost flow problems in python?

import networkx as nx

#inputdata
producerDict = {'p1': 3.88, 'p2': 4.3225, 'p3': 24.41575}
consumerDict = {'c1':46.63775, 'c2': 85.44925, 'c3': 71.92425, 'c4': 
84.1755}

totalDemand = sum(consumerDict.values())
totalSupply = sum(producerDict.values())

#graph
G = nx.DiGraph()
G.add_edge("C1", "P1", weight=3)
G.add_edge("C1", "P2", weight=1)
G.add_edge("C1", "P3", weight=4)

G.add_edge("C2", "P1", weight=2)
G.add_edge("C2", "P2", weight=4)
G.add_edge("C2", "P3", weight=5)

G.add_edge("C3", "P1", weight=6)
G.add_edge("C3", "P2", weight=2)
G.add_edge("C3", "P3", weight=2)

G.add_edge("C4", "P1", weight=1)
G.add_edge("C4", "P2", weight=6)
G.add_edge("C5", "P3", weight=3)

#balancing the problem as demand > supply
newConsumerDict = {}
for consumer, demand in consumerDict.items():
    newDemand = (demand / totalDemand) * totalSupply
    newConsumerDict[consumer] = newDemand


# this sum has to be equal to total supply which 
# is not the case due to rounding errors
print(sum(newConsumerDict.values()))

flowCost, flowDict = nx.network_simplex(G)

cheers

learnPyt
  • 41
  • 5

1 Answers1

1

The documentation you link to says:

This algorithm is not guaranteed to work if edge weights or demands are floating point numbers (overflows and roundoff errors can cause problems). As a workaround you can use integer numbers by multiplying the relevant edge attributes by a convenient constant factor (eg 100).

My interpretation of this is that there may be cases where roundoff error is an issue. I would expect that the algorithm most likely will work fine unless you have a lot of weights that differ only at 10^{-10} sizes. But for practical purposes, I would expect it to be fine if you just multiply the weights by 100 (or 100000) and then just take the integer part.

Joel
  • 22,598
  • 6
  • 69
  • 93
  • I've tried out some examples with demand and supply values of: demand = [-0.2,1.8,3,4.5] supply = [3,4.3,1.7,0.5] and it didn't work while others with similiar values did. seems like the algorithm really can't handle floats. Do you know any other library I could use to solve this problem by any chance? – learnPyt May 31 '21 at 12:42
  • Did you try `[-2, 18, 30, 40, 50]` and `[30, 43, 17, 5]`? – Joel Jun 01 '21 at 11:46
  • Sorry my example had a little mistake as supply needs to be equal to demand. But I got your idea. Transforming the float values into ints will work for those floats from above. in my original problem I'm working with floats that have values like 0.00021232, 0.0000000123421. Transforming those floats into ints didn't work due to rounding errors... Do you have any suggestion on how to handle this? – learnPyt Jun 01 '21 at 14:57
  • Can you give a specific example where the floats don't work? (including the graph) – Joel Jun 02 '21 at 08:01
  • G.add_edge("C1", "P1", weight=3) G.add_edge("C1", "P2", weight=1) G.add_edge("C1", "P3", weight=4) G.add_edge("C2", "P1", weight=2) G.add_edge("C2", "P2", weight=4) G.add_edge("C2", "P3", weight=5) G.add_edge("C3", "P1", weight=6) G.add_edge("C3", "P2", weight=2) G.add_edge("C3", "P3", weight=2) G.add_edge("C4", "P1", weight=1) G.add_edge("C4", "P2", weight=6) G.add_edge("C5", "P3", weight=3) – learnPyt Jun 02 '21 at 09:48
  • If you could edit your original post to include this example including the networkx code that doesn't work, that would be helpful. – Joel Jun 03 '21 at 02:10
  • hey I've just updated my post with a not working example. – learnPyt Jun 03 '21 at 06:28
  • When I run that code, I get `32.61825000000001` and `32.61825`. These aren't equal, but there's no way to get around this unless you turn everything into integers. It's got nothing to do with the networkx implementation. If you take two sets of floats, both of which add up to the same value, you're going to need to be very lucky for them to actually add up to the same float to the precision of round off error. – Joel Jun 03 '21 at 08:30
  • see this for example: https://stackoverflow.com/questions/588004/is-floating-point-math-broken – Joel Jun 03 '21 at 09:04
  • yeah exactly its due to float rounding errors... but makes the problem infeasible. Do you know if adding the difference amount in between demand and supply as a demandDummy could solve this? Like instead of calculating the newConsumerDict we'd just add another node. Does this dummy node needs to have a cost of zero or a really high cost though? – learnPyt Jun 03 '21 at 11:43
  • Can you explain how this makes it infeasible? I very rarely encounter cases where I care about a 10^{-14} error. – Joel Jun 03 '21 at 16:32
  • well it makes it infeasible as due to rounding errors we won't get demand == supply... – learnPyt Jun 03 '21 at 20:33
  • In short, there is no getting around this, in any implementation I could imagine, in any standard computer language. The values for all of these nodes are all floats. It is highly unlikely that on any given realization you'll have them add up to match perfectly. – Joel Jun 09 '21 at 08:01
  • If you need demand to equal supply at 10^{-14}, you'll need to use a higher precision calculation (and then of course demand still won't equal supply at the limits of that precision). I really doubt however that you need demand to equal supply at that accuracy. – Joel Jun 09 '21 at 08:03