Maximum profit from buy and sell offers

Question

Given a list of sell offers and a list of buy offers for an item I want to determine how many units to trade for maximum profit.

Each offer consists of a price and a maximum amount of units being traded. Offers can be partially fulfilled (i.e. if a buyer/seller wants to trade 100 units, it's ok to trade only 10). However, buy orders can have a minimum amount, which means that the buyer will buy at least this amount of units or none at all.

# sell offers
sell = [Order(price=7.0, amount=120, min_amount=np.nan),
        Order(price=20.0, amount=80, min_amount=np.nan)]

# buy offers
buy = [Order(price=30.0, amount=100, min_amount=100),
       Order(price=15.0, amount=200, min_amount=50),
       Order(price=10.0, amount=20, min_amount=1)]

In this example 120 units are being sold at a price of 7.0 and 80 units at a price of 20.0. Buyers are willing to buy exactly 100 units for 30.0, between 50 and 200 units for 15.0, and up to 20 units for 10.0.

My code determines how many units to trade for maximum profit. It loops over the amount of units traded and computes the optimal buy and sell prices in each iteration. The idea is to get the item as cheaply as possible from sell orders and to sell them as expensively as possible to buy orders.

The optimal sell order price is relatively trivial to obtain. Get as many units as possible from the cheapest offer, and if that is exhausted advance to the next cheapest.

The minimum amount on buy orders makes computation of the optimal buy price more complicated. For example, when trading less than 100 units they cannot be sold as expensively than when trading more than 100 units.

This works reasonably well in the example, but is horribly inefficient when dealing with larger amounts (thousands-millions of units). I could certainly get better performance by using Cython or implementing in C, but I hope for a algorithmic optimization first.

Is there a better (faster) way to find the optimal profit?

import numpy as np
import matplotlib.pyplot as plt
from collections import namedtuple

Order = namedtuple('Order', ['price', 'amount', 'min_amount'])

if __name__ == '__main__':
    # sell offers
    sell = [Order(price=7.0, amount=120, min_amount=np.nan),
            Order(price=20.0, amount=80, min_amount=np.nan)]

    # buy offers
    buy = [Order(price=30.0, amount=100, min_amount=100),
           Order(price=15.0, amount=200, min_amount=50),
           Order(price=10.0, amount=20, min_amount=1)]

    max_n = 201

    sell = np.asarray(sell)
    buy = np.asarray(buy)

    # vectorized computation of sell prices
    amounts = np.zeros(1 + sell.shape[0])
    prices = np.zeros(1 + sell.shape[0])
    amounts[1:] = np.cumsum(sell[:, 1])
    prices[1:] = np.cumsum(sell[:, 1] * sell[:, 0])
    sellprices = np.interp(np.arange(max_n), amounts, prices)

    # performance hog: computation of buy prices
    buyprices = []
    for n in range(max_n):
        price = 0
        remaining = n
        for unit_price, amount, min_amount in buy:
            if remaining < min_amount:
                continue
            if remaining > amount:
                remaining -= amount
                price += amount * unit_price
            else:
                price += remaining * unit_price
                break
        buyprices.append(price)

    sellprices = np.array(sellprices)
    buyprices = np.array(buyprices)
    profits = buyprices - sellprices

    k = np.argmax(profits)

    plt.plot(sellprices, 'r', label='sell offers')
    plt.plot(buyprices, 'b', label='buy offers')
    plt.plot(profits, 'k', label='profit')
    plt.plot(k, profits[k], 'ko', label='optimum')
    plt.legend(loc='best')
    plt.xlabel('amount traded')
    plt.ylabel('price')
    plt.show()

Answer 1

1. Review

1. The code in the post does not always compute the highest profit. For example, suppose that I have these orders:

   sell = [Order(price=1, amount=1, min_amount=np.nan)]
   buy = [Order(price=1, amount=1, min_amount=1),
          Order(price=2, amount=1, min_amount=1)]
   max_n = 2
   

   Then the code computes:

   buyprices = [0, 1]
   profits = [0, 0]
   

   In other words, the code sells to the first buyer, ignoring the second buyer who is prepared to pay more.

2. You clarified in comments that it's a requirement that the buyers be sorted by price. It would be more reliable if the code did any necessary sorting:

   buy = buy[np.argsort(buy[:,0])]
   

   Then you wouldn't have to worry about the order of the input.

3. Even if the input is sorted by price, the algorithm in the post still does not always compute the highest profit. For example, suppose that I have the following orders:

   sell = [Order(price=1, amount=4, min_amount=np.nan)]
   buy = [Order(price=6, amount=3, min_amount=3),
          Order(price=5, amount=2, min_amount=2),
          Order(price=5, amount=2, min_amount=2)]
   max_n = 5
   

   In this case, the code computes:

   buyprices = [0, 0, 10, 18, 18]
   profits = [0, -1, 8, 15, 14]
   

   The highest profit it can find is 15, by selling three units to the first buyer. But if I sell two units to each of the second and third buyers, then I get a profit of 16.

4. Even with the orders given in the post, the code computes the wrong prices for some amounts. For example, you can see from the graph that the code thinks that it can sell 40 units for a price of 200. But there is no way to sell 40 units — you can sell 20 units to the third buyer, but no more than that, and the second buyer has a minimum order of 50.

   Similarly, the code determines that it can sell 140 units for a price of 3200. But there is no way to make such a sale: if you sell 100 to the first buyer, then that leaves 40, and there is no way to sell 40 units (as discussed above). So you have to sell to the second buyer, in which case the best price you can get is 2100.

   I believe that the correct graph looks like this, with a gap between 20 and 50, and lower profits betwen 120 and 150:

   

2. Correct algorithm

Before trying to speed up the code, it's important to implement a correct algorithm (even if it is slow), otherwise it will be hard to check that the faster algorithm is correct.

In the general case, the problem of finding the highest profit is NP-hard, by an easy reduction from SUBSET SUM. But this isn't a disaster, because problems like subset sum often have pseudo-polynomial algorithms using the tabular method (aka "dynamic programming").

So let's try the tabular method by building up a table of prices, using \$−∞\$ for impossible amounts:

def buy_prices(buy_orders, limit):
    """Return array containing the best price for each amount below limit,
    given an array of buy orders. The result is -inf for any amount
    that cannot be sold to any combination of buy orders.

    """
    prices = np.full((limit,), -np.inf)
    prices[0] = 0
    for price, amount, min_amount in buy_orders:
        p = prices.copy()
        for a in range(int(min_amount), int(amount) + 1):
            for i in range(a, limit):
                prices[i] = max(prices[i], p[i-a] + a * price)
    return prices

This has runtime \$Θ(mn^2)\$, where \$m\$ is the number of buy orders and \$n\$ is the maximum amount that can be traded.

We can speed this up by vectorizing the inner loop:

def buy_prices(buy_orders, limit):
    """Return array containing the best price for each amount below limit,
    given an array of buy orders. The result is -inf for any amount
    that cannot be sold to any combination of buy orders.

    """
    prices = np.full((limit,), -np.inf)
    prices[0] = 0
    for price, amount, min_amount in buy_orders:
        p = prices.copy()
        for a in range(int(min_amount), min(limit, int(amount) + 1)):
            q = p[:limit-a] + a * price
            prices[a:limit] = np.maximum(prices[a:limit], q)
    return prices

However, the runtime is still \$Θ(mn^2)\$ and so it will be unacceptable when \$n\$ is large.