Find max total revenue in a directed graph

Question

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

Answer 1

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

Answer 2

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.