组合优化&背包问题的变种

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和cost U的产品P，找到具有cost U'和value V'的产品Q，具有最小的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来求解这个非lienar程序)。

程序：

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.3d =0.1)，因为excel不允许在求解器中出现条带不等。)

我猜有了像Ampl这样的真正的求解器，它会完美地工作。

希望能有所帮助，