# 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:

1. 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:

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

2. 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')$$.

• Steven, thank you very much for the answer! Am I right, that this algorithm takes O(n^3 * n) time (cubic vertices times edges)? Commented Oct 2, 2023 at 17:18
• It depends on which algorithm for min-cost max-flow you use. If all volumes are integral you can use this one to get a time complexity of $O(m(m+n \log n)) = O(n^2 \log n)$ once you clamp all volumes to at most 100 (since that's the maximum you can buy or sell anyway) and notice that $m=\Theta(n)$ since the number of vertices is $\Theta(n)$ and the number of edges $m$ is $2n+1 = O(n)$. Commented Oct 2, 2023 at 18:28

The following answer assumes that volumes are integers.

You can solve the problem in time $$O(n)$$ using dynamic programming. For $$i=0, \dots, n$$ and $$v=0, \dots, 100$$, let $$r[i,v]$$ be the maximum revenue that you can obtain when you only visit the first $$i$$ cities and you need to end your journey with a volume of exactly $$v$$ in your knapsack. If that's impossible, let $$r[i,v] = -\infty$$.

You have the following base cases for $$i=0$$: $$r[0,0]=0 \quad \text{and} \quad r[0,v] = -\infty \; \forall v \neq 0.$$

When $$i=1,\dots, n$$ and you can buy the commodity in city $$i$$ you have: $$r[i,v] = \max_{ x = 0,1,\dots, \min(v, \text{Vol}_{C_{i}})} \left( r[i-1, v-x] - x \cdot \text{Price}_{C_i} \right).$$

When $$i=1,\dots, n$$ and you can sell the commodity in city $$i$$ you have: $$r[i,v] = \max_{ x = 0,1,\dots, \min(100-v, \text{Vol}_{C_{i}})} \left( r[i-1, v+x] + x \cdot \text{Price}_{C_i} \right).$$

Notice that each of the above formulas for $$r[i,\cdot]$$ can be evaluated in constant time once the values of $$r[i, \cdot]$$ are known ($$x$$ can only take constantly many values), and that there are only $$O(n)$$ subproblems ($$v$$ can only take constantly many values).

The maximum revenue for the instance will be in $$r[n, 0]$$ (since it is never convenient to have leftover commodity). The actual amounts to buy/sell can be found by retracing the optimal choices backwards.

• Steven, thank you for the answer! I was also thinking about the DP. But in each city volumes are not only integer values... This could be the problem... Commented Oct 2, 2023 at 15:35
• Then the problem can be solved using min-cost max-flow. I'll sketch an answer- Commented Oct 2, 2023 at 15:52
• Steven, that would be more than helpful! Thank you! Commented Oct 2, 2023 at 16:11
• Steven, one more short question. I am now trying to implement the DP approach, but max capacity is not 100, but 1000000 in real. So the complexity starts to be n * 10000^2 (because we iterate over cities and over all values of volume and for each iteration we are searching for the max of array if length 10000). Don't you know if there is a way to increase the speed of the algorithm...? Commented Oct 2, 2023 at 20:29
• With some rewriting of the formulas maybe you can use monotone min-plus convolutions to reduce the time complexity to $\widetilde{O}(n \cdot M^{3/2})$, where $M$ is the maximum capacity, but I cannot comment on how practical the algorithm is. Commented Oct 2, 2023 at 22:16