Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints

Question

I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are capable of delivering to each urn. The objective is to fill the urns with all the available sand while minimizing total cost. Here's a motivating example:

Black circles show porters. The value in the center of the porter circles show the total amount of sand they can transport. Gray squares show urns. The value in the center of the urns show the amount of sand an urn can hold. Porter_Urn edges show the cost of transporting 1 unit of sand to a given urn. Using this example, Porter 1, which has 100 units of sand could transport 1 unit of sand for a cost of 50 to Urn 3, which can hold a total of 65 units of sand. That would be very expensive!

Is there an algorithm to solve this optimization problem? It seems like maybe a maximum flow problem or maybe a multi-knapsack problem? Or some other algorithm from Operations Research?

Answer 1

This is straight up a minimum-cost flow problem. All it's missing is a an edge from the source to each porter with zero cost and capacity equal to the porter, and a zero cost edge from each urn to the sink with capacity equal to that urn.