algorithm - 组合优化-背包的变化

这是一个实际的组合优化问题。

我们为特定产品提供了一系列值(value)主张。值(value)主张是不同的类型，但每种类型都是独立的，并为整个产品增加了同等的利益。在构建产品时，我们可以包含每种类型的任何非负整数的“单位”。但是，在添加了某种类型的第一个单元后，该类型的其他单元的边际 yield 会不断降低。实际上，新单位的边际 yield 是添加新单位后该类型单位数量的倒数。我们的产品必须至少具有某种类型的单元，并且由于此要求，我们必须对总值进行小幅校正。

令T[]为一个数组，代表产品在特定生产过程中每种类型的数量。然后，总值V由(伪代码)给出:

V = 1
For Each t in T
    V = V * (t + 1)
Next t
V = V - 1 // correction

在成本方面，相同类型的单位具有相同的成本。但是，不同类型的单位各自具有独特的非理性成本。类型的数量很大，但是我们得到了一组类型成本C[]，从最小到最大排序。我们进一步假设类型数量数组T[]也按成本从最小到最大排序。然后，总成本U就是每个单位成本的总和:

U = 0
For i = 0, i < NumOfValueTypes
    U = U + T[i] * C[i]
Next i

到现在为止还挺好。所以这是问题所在:给定产品P的值为V和cost U，找到具有成本Q和值U'的产品V'，其U'最小，如U' > U和V'/U' > V/U。

最佳答案

您描述的问题是非线性整数编程问题，因为它包含整数变量t的乘积。由于存在严格的不等式，因此无法关闭其可行性集，可以通过使用非严格的不等式并在右侧添加一个小的正数(ε)来解决此问题。然后可以在AMPL中将问题表述为:

set Types;
param Costs{Types};      # C
param GivenProductValue; # V
param GivenProductCost;  # U
param Epsilon;

var units{Types} integer >= 0; # T
var productCost = sum {t in Types} units[t] * Costs[t];

minimize cost: productCost;
s.t. greaterCost: productCost >= GivenProductCost + Epsilon;
s.t. greaterValuePerCost:
  prod {t in Types} (units[t] + 1) - 1 >=
    productCost * GivenProductValue / GivenProductCost + Epsilon;

可以使用诸如Couenne之类的非线性整数编程求解器来解决此问题。

关于algorithm - 组合优化-背包的变化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6334004/