具有M个特征的N个产品的最优组合

Question

我有 X 件成本固定的零件。每个部分都有N个方面不同的价值。

例如：

Part 1: cost = 3,
Width = 10,
Length = 12,
Height = 13,
Weight = 12,
Value = sum of four aspects = 47

Part 2: cost 4,
Width = 20,
Length = 15,
Height = 12,
Weight = 10,
Value = sum of above four aspects = 57

Part 3: cost 2,
Width = 9,
Length = 12,
Height = 9,
Weight = 8,
Value = sum of above four aspects = 38

然后我有很多这样的不同项目，例如20 项。我一次可以选择的最大项目数有上限，例如8 项。我有一个成本上限，即所选项目的成本总和应该有一个规定的限制，例如30.

我现在必须从此列表中选择项目，这样我才能获得最大价值。另一个约束是，在最终组合中，所有方面都应该是平衡的。例如Width、Length、Height 和 Weight 的最终总和应平均分配。如果不相等，至少在一个平衡的范围内。即因为有4个方面，每个方面应该是总价值的25%+/-5%左右。

我尝试用背包问题的方式解决它，但我这里有更多维度。

Answer 1

一种方法是通过 MILP 模型。这是一个用 MiniZinc 实现的简单模型。 x 是二进制变量，表示是否选择了某个项目。

int: items = 5;
int: selectedItems = 3;
int: maxCost = 10;

set of int: ITEM = 1..items;

array[ITEM] of int: cost = [3, 4, 2, 1, 1];
array[ITEM] of int: width = [10, 20, 9, 15, 12];
array[ITEM] of int: length = [12, 15, 12, 15, 12];
array[ITEM] of int: height = [13, 12, 9, 15, 12];
array[ITEM] of int: weight = [12, 10, 8, 15, 12];
array[ITEM] of int: value = [width[i] + length[i] + height[i] + weight[i] | i in ITEM];
    
array[ITEM] of var 0..1: x;

% selected items constraint
constraint sum(x) <= selectedItems;

% cost constraint
constraint sum(i in ITEM)(cost[i]*x[i]) <= maxCost;

predicate balanced(array[ITEM] of var int: values) =
    let {var int: value = sum(i in ITEM)(values[i]*x[i])} in
    value >= 0.2*totalValue /\ value <= 0.3*totalValue;

% balance constraints
constraint balanced(width) /\ balanced(length) /\ balanced(height) /\ balanced(weight);

var 1..sum(value): totalValue = sum(i in ITEM)(value[i]*x[i]);

solve maximize totalValue;

output ["totalValue=\(totalValue)\n"] ++
["cost=\(sum(i in ITEM)(cost[i]*x[i]))\n"] ++ 
["x="] ++ [show(x)] ++
["\nratio="] ++ [show_float(5, 2,sum(i in ITEM)(width[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(length[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(height[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(weight[i]*x[i]) / totalValue)] ++
["\nvalue="] ++ [show(value)];

运行（使用默认的 Gecode 求解器）给出：

totalValue=165
cost=6
x=[0, 1, 0, 1, 1]
ratio= 0.28 0.25 0.24 0.22
value=[47, 57, 38, 60, 48]

具有M个特征的N个产品的最优组合

Optimal combination of N products with M features

mathematical-optimization