优化 - 选择集合的子集以最小化成本
Optimization - choosing subset of sets which minimises the cost
解决此类问题的有效方法是什么：
我们有许多可能的实体（例如：产品、医学测试）。这些实体以套餐形式提供，购买套餐中的项目 A、B、C 比单独购买它们的成本更低（项目可能会也可能不会单独出售，如果它们有一定的价格）。我们只对几个项目感兴趣，我们想找到什么是单一产品的最佳组合 and/or 产品包以最低的成本购买我们需要的所有项目（我们真的不在乎我们是否购买任何产品是否不在我们的列表中，它们对我们的价值为零）。套餐的内容可以重叠（例如，项目 A 可以在多个不同的套餐中提供，也可以单独提供）。
最自然的方法是计算幂集（所有可能的子集），但这不允许解决方案很好地扩展。
什么是有效的精确或 approximate/heuristic 解决方案？
您可以在优化模型中执行此操作。
假设我们有输入数据：
---- 14 SET c items+combos
c1, c2, c3, A , B , C
---- 14 SET i single items
A, B, C
---- 14 PARAMETER p prices
c1 30, c2 18, c3 18, A 10, B 12, C 15
---- 14 PARAMETER cc combo content
A B C
c1 1 1 1
c2 1 1
c3 2
A 1
B 1
C 1
---- 14 PARAMETER demand items needed
A 7, B 4, C 3
现在我们求解简单的混合整数规划 (MIP) 模型：
结果如下：
---- 36 VARIABLE buy.L items+combos to buy
c1 3, c2 1, c3 1, A 1
---- 36 VARIABLE cost.L = 136.000
在某些情况下，我们会购买比需要更多的东西（如果折扣足够高）。如果您购买的物品的价值超过需求，那么模型就会变得有点复杂。
高性能商业 MIP 求解器和开源 MIP 求解器都很容易获得。他们将非常有效地解决这种类型的模型以达到全局最优（即使对于具有许多项目和许多组合的更大数据集也是如此）。与您的 "powerset" 算法相比，对我来说，这种方法看起来更有吸引力。 MIP 求解器不是近似值，但它们通常只需要探索所有可能的可行整数解的一小部分。
解决此类问题的有效方法是什么：
我们有许多可能的实体（例如：产品、医学测试）。这些实体以套餐形式提供，购买套餐中的项目 A、B、C 比单独购买它们的成本更低（项目可能会也可能不会单独出售，如果它们有一定的价格）。我们只对几个项目感兴趣，我们想找到什么是单一产品的最佳组合 and/or 产品包以最低的成本购买我们需要的所有项目（我们真的不在乎我们是否购买任何产品是否不在我们的列表中，它们对我们的价值为零）。套餐的内容可以重叠（例如，项目 A 可以在多个不同的套餐中提供，也可以单独提供）。
最自然的方法是计算幂集（所有可能的子集），但这不允许解决方案很好地扩展。
什么是有效的精确或 approximate/heuristic 解决方案？
您可以在优化模型中执行此操作。
假设我们有输入数据：
---- 14 SET c items+combos
c1, c2, c3, A , B , C
---- 14 SET i single items
A, B, C
---- 14 PARAMETER p prices
c1 30, c2 18, c3 18, A 10, B 12, C 15
---- 14 PARAMETER cc combo content
A B C
c1 1 1 1
c2 1 1
c3 2
A 1
B 1
C 1
---- 14 PARAMETER demand items needed
A 7, B 4, C 3
现在我们求解简单的混合整数规划 (MIP) 模型：
结果如下：
---- 36 VARIABLE buy.L items+combos to buy
c1 3, c2 1, c3 1, A 1
---- 36 VARIABLE cost.L = 136.000
在某些情况下，我们会购买比需要更多的东西（如果折扣足够高）。如果您购买的物品的价值超过需求，那么模型就会变得有点复杂。
高性能商业 MIP 求解器和开源 MIP 求解器都很容易获得。他们将非常有效地解决这种类型的模型以达到全局最优（即使对于具有许多项目和许多组合的更大数据集也是如此）。与您的 "powerset" 算法相比，对我来说，这种方法看起来更有吸引力。 MIP 求解器不是近似值，但它们通常只需要探索所有可能的可行整数解的一小部分。