mathematical-optimization - N个产品与M个特征的最优组合
问题描述
我有 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。
我现在必须从这个列表中选择项目,以便获得最大价值。另一个约束是,在最终的组合中,所有方面都应该平衡。例如,宽度、长度、高度和重量的最终总和应平均分配。如果不相等,至少在一个平衡的范围内。即因为有4个方面,每个方面应该是总值的大约25% +/-5%。
我尝试用背包问题的方式解决它,但我这里有更多维度。
解决方案
一种方法是通过 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]