algorithm - 0-1 带分区约束的背包

Question

我有一个问题，表面上看起来像 0-1 背包。我有一组可以选择(或不选择)的可能“候选人”，每个候选人都有一个“权重”(成本)和一个潜在的“值(value)”。如果这是整个问题，我会使用 DP 方法并解决它。但这里有一个曲线球:对可能出现在最终解决方案中的候选对象存在“分区约束”。

我的意思是候选空间被拆分成离散的等价类。对于我的特定问题，大约有 300 个候选对象和 12 个可能的等价类。有“商业规则”说我最多只能说 C1 类的 3 名候选人和 C2 类的 6 名候选人，等等。

此约束建议使用分支定界技术或某种其他形式的修剪的图形搜索类型方法，但是我对如何开始有些困惑，因为我只熟悉 0-1 Knapsack 的 DP 解决方案.什么技术/方法可能适合这个问题？我也想过也许使用约束编程库，但不确定它是否能够找到解决方案？

Answer 1

您可以尝试使用整数线性规划求解器，其中有一个用于选择每个候选项的二进制变量。约束很容易表示为线性不等式。有了 300 个变量，求解器应该不会遇到太多问题。

最简单的方法可能是以文本格式写下您的问题，例如 CPLEX LP format ，然后使用 Coin CBC 或 GLPK 等求解器。