组合优化 - 背包的变体

Question

这是一个现实世界的组合优化问题。

我们获得了某种产品的大量价值主张。价值主张有不同的类型，但每种类型都是独立的，并且为整体产品带来同等的好处。在构建产品时，我们可以包含每种类型的任何非负整数“单元”。然而，在添加某种类型的第一个单元之后，该类型的附加单元的边际效益不断减小。事实上，新单元的边际效益是添加新单元后该类型单元数量的倒数。我们的产品必须至少有一个某种类型的单位，并且由于这一要求，我们必须对整体价值进行一个小的修正。

令 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

到目前为止一切顺利。所以问题是：给定具有值 V 和成本 U 的产品 P，找到具有以下值的产品 Q：成本U'和值V'，具有最小U'使得U'> U，V'/U'> V/U。

Answer 1

您描述的问题是非线性整数规划问题，因为它包含整数变量t的乘积。由于严格的不等式，它的可行性集不是封闭的，可以通过使用非严格的不等式并向右侧添加一个小的正数（epsilon）来解决。然后问题可以在 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 。

Answer 2

老实说，我认为没有简单的方法可以解决这个问题。最好的办法是编写系统并用求解器求解（Excel 求解器可以解决问题，但您可以使用 Ampl 来解决这个非线性程序。）

该程序：

Define: U;
        V;
        C=[c1,...cn];

Variables: T=[t1,t2,...tn];

Objective Function: SUM(ti.ci)

Constraints:

For all i: ti integer
SUM(ti.ci) > U 
(PROD(ti+1)-1).U > V.SUM(ti.ci)

它与 Excel 配合良好：您只需替换 >U经过>=U+d 其中 d 是成本的有效数字（即如果 C=[1.1, 1.8, 3.0, 9.3] d =0.1< /code>) 因为 Excel 不允许求解器中存在严格的不等式。

我想使用像 Ampl 这样的真正的解算器，它会完美地工作。

希望有帮助，