Find max total revenue in a directed graph

Problem:

Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy fixed commodity or to sell it (but only to buy or to sell, never both). Prices are known and available; available volume is also known for each city: $Vol_{C_i}, Price_{C_i}$. So, each city has three values: volume, price and offer_side $\in [ buy, sell ]$.

Question:

• What is an algorithm to decide, in which cities to buy this commodity and in which to sell and with what volume to maximize total revenue? The constraint is that you cannot carry more than 100 of volume in a knapsack at each point of time.

Methods:

-
I was thinking about knapsack problem, but it is not the case, because I can choose, which volume to put in a knapsack and I can "throw things away" from a knapsack by selling the commodity.

-
I was also thinking about flow algorithms, but they usually maximize the flow with given edge capacity, but flow algorithms do not have constraints on "total flow" at each time. Moreover, flow algorithms do not have a revenue, but only the max flow...

Your problem can be solved by reducing it to a min-cost max-flow problem where a unit of flow represents one unit of commodity. A negative cost represents a profit.

Create a directed graph containing $n+3$ vertices in total: there are three vertices named $s$, $t$ and $t'$, and the remaining $n$ vertices are $C_1, \dots, C_n$ (each representing a city).

The edges are as follows:

• For ever $i=1, \dots, n-1$ add an edge from $C_i$ to $C_{i+1}$. This edge has capacity $100$ and cost $0$.

• Add an edge $(s, C_i)$ for ever city $C_i$ in which you can buy the commodity. The capacity of this edge is $\text{Vol}_{C_i}$ and the cost is $\text{Price}_{C_i}$.

• Add an edge $(C_i,t)$ for ever city $C_i$ in which you can sell the commodity. The capacity of this edge is $\text{Vol}_{C_i}$ and the cost is $-\text{Price}_{C_i}$.

If we were to look for a min-cost max-flow from $s$ to $t$ in the above graph, we would find the solution that maximizes the profit among the ones that trade the maximum amount of the commodity. This is clearly not what we want, as it could force us to trade the commodity at a loss.
We can avoid this problem with a technicality:

• Let $F$ be an upper bound on the amount of flow from $s$ to $t$ (for example the sum of all $\text{Vol}_{C_i}$). Add an edge $(t, t')$ with capacity $F$ and cost $0$, and an edge $(s,t)$ with capacity $F$ and cost $0$.

Now you can always attain a min-cost max-flow from $s$ to $t'$ by "padding"
the most profitable (but not necessarily maximum) flow from $s$ to $t$ in the previous graph. Indeed, if the amount of such flow is $\phi$, you can route $F-\phi$ additional "free" units of flow along the newly added edge $(s,t)$. The overall flow of $\phi + (F-\phi) = F$ reaching $t$ can then go from $t$ to $t'$ via the edge $(t, t')$.

StackExchange Computer Science Q#162297, answer score: 6