组合优化 - 背包的变化

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

到现在为止还挺好.因此,这里的问题是:由于产品P具有价值V和成本U,找到产品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 ）来解决。