algorithm - 投资组合优化问题 : improving the O(n! ) 解决方案

Question

有一组订阅产品，每个产品都有以下属性:

• 日返回率
• 最低可分配金额
• 最大可分配金额

我正在尝试分配给定的金额以获得尽可能高的每日总返回。

我目前的解决方案是一个复杂度为 O(n!) 的蛮力递归贪婪算法。我正在寻找至少一个多项式解决方案，因为针对生产数据运行它需要很长时间。我尝试应用动态规划技术，但每一步都有一个非整数值发生变化(数量是真实的，在每次分配后它变得更低)。

Python 中的 O(n!) 解决方案(参见 _allocator 函数):

from pprint import pprint
from decimal import Decimal as D
from dataclasses import dataclass

_RATE = D(1) / 365

@dataclass
class Product:
    name: str
    min: D
    max: D
    annual_rate: D # Rate of return (annualized)
    daily_returns: D = None

    def __post_init__(self):
        self.daily_returns = (1 + self.annual_rate) ** _RATE - 1

@dataclass
class Allocation:
    product: Product
    amount: D
    daily_gain: D = None

    def __post_init__(self):
        self.daily_gain = self.product.daily_returns * self.amount

PRODUCTS = [
    Product('Bad', 1, 100, D('0.01')),
    Product('Flexible', 1, 100, D('0.02')),
    Product('Locked60', 20, 30, D('0.04')),
    Product('Locked90', 20, 35, D('0.05')),
    Product('Staking7', 1, 10, D('0.07')),
]

# Try all possible allocations recursively and pick the best one
# Complexity: O(n!)
def _allocator(amount, products, path):
    bgain, balloc = D(0), path

    for i, p in enumerate(products):
        if p.min <= amount:
            val = min(p.max, amount)
            sgain, salloc = _allocator(amount - val,
                                       products[:i] + products[i+1:],
                                       [*path, (p, val)])

            sgain += val * p.daily_returns
            if sgain > bgain:
                bgain = sgain
                balloc = salloc

    return bgain, balloc

def balance_brute(amount, products):
    _, alloc = _allocator(amount, products, [])
    return [Allocation(p, a) for p, a in alloc]

allocs = balance_brute(D(100), PRODUCTS)
pprint(allocs)
print('Total gain:', sum(a.daily_gain for a in allocs))

Answer 1

我会先尝试混合整数规划公式。

高级求解器具有所谓的半连续变量，它允许变量取值 0 或介于 [L,U] 之间。这将给出如下模型:

max sum(i, x[i]*rate[i])
sum(i, x[i]) <= budget
x[i] ∈ {0} ∪ [L[i],U[i]]

如果您的求解器没有半连续变量，则使用二元变量:

max sum(i, x[i]*rate[i])
sum(i, x[i]) <= budget
δ[i]*L[i] <= x[i] <= δ[i]*U[i];
δ[i] ∈ {0,1}

根本不是多项式。但非常快:10 万个项目(使用随机数据)需要 2.2 秒。这是一个很好的例子，其中复杂性分析可能会产生误导:指数级的最坏情况行为并不意味着在特定问题上速度慢。这个显而易见的陈述似乎几乎从未被教授过。

(我之前说过 0.05 秒；那是不正确的——那是针对 n=1,000 次运行)。正确的时间是:

Root node processing (before b&c):
  Real time             =    2.20 sec. (2328.41 ticks)
Parallel b&c, 16 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    2.20 sec. (2328.41 ticks)