python networkX network simplex

Question

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

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