1
$\begingroup$

I am trying to analyze supply chains in a game and have come across this problem:

First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, each consumer requieres a certain amount of goods. Each producer is connected to some consumers (these connections have infinite capacity).

Is there a way to transport goods from producers to consumers so that each consumer has sufficiently many goods? Each producer can provide goods to multiple consumers and each consumer can accept goods from multiple producers. A producer also doesn't have to deliver the entire production, as the rest can be discarted.

The connections form a bipartite graph with producers $p \in P$ and consumers $c \in C$ as vertices (so $V = P \mathbin{\unicode{x228D}} C$) and edges $E \subseteq (P \times C)$. Each producer has a positive production rate and each consumer a positive consumption rate.

We model how much is transported over each connection with a weight function $w: E -> \mathbb{R}$. For each producer $p$ , we get the required production by summing up the weights of all edges incident to $p$. This must not be higher than the production of $p$.

Similarly, for each consumer $c$, we get the total delivery by summing up the weights of all edges incident to $c$. This must not be lower than the consumption of $c$.

Does such a $w$ exist for a given graph, production rate and consumption rate?

The left example has such a function, the right one does not:

Instance where such a weight function exists enter image description here

I am pretty sure that if we allow negative $w(e)$, the problem is very easy (for connected graphs, just compare total production to total consumption). Therefore, it probably makes sense to restrict $w(e) \geq 0$.

I have tried to find similar problems, but most flow problems have limited flow rates and sources with infinite capacity (whereas here, it's exactly the other way around). I also know about the Assignment problem, but I don't think it applies here.

Perhaps there is a way to slowly remove consumers and producers. In the first example, we know that the top producer can only supply the top consumer, so we could just remove the producer and reduce the consumption rate on the right. It might also be possible to merge multiple producers and consumers if they all supply each other. However, I don't think that these operations alone suffice to solve the problem in all instances.

Perhaps there is no efficient algorithm, so I've also tried proving that the problem is NP-complete, but my attempt to reduce SAT to this problem wasn't successful.

This probably isn't the most enjoyable way to play Anno, but at this point, it don't want to give up...

$\endgroup$
2
$\begingroup$

I'm not sure I understand the problem statement, but it looks like this can be modelled as a network flow problem. Here's how. First, create a new source vertex $s_0$. Then, for each producer $p$, if its capacity is $c_p$, and add an edge $s_0 \to p$ with capacity $c_p$. Do that for every producer, then look for a max flow in the resulting flow graph.

$\endgroup$
  • 1
    $\begingroup$ Thank you for the idea! As far as I can tell, I would have to do a similar construction on the consumer side to model the demand of each consumer. If the max flow in the resulting flow graph then matches the total consumption, I know that all consumption demands have been met. $\endgroup$ – jalgames May 7 at 16:08
  • $\begingroup$ @jalgames, good point, I missed that. That makes sense. $\endgroup$ – D.W. May 7 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.