迷你锌。离散背包问题。 Аn难以理解的解决方案

Question

求解（来自https://www.minizinc.org/doc-2.5.5/en/modelling2.html#set-constraints）：

enum ITEM = { I1, I2, I3, I4, I5 };
int: capacity = 5;

array[ITEM] of int: profits = [1,2,3,4,5];
array[ITEM] of int: weights = [1,2,3,4,5];

int: maxProfit = sum (profits);

var set of ITEM: knapsack;

var int: weight = sum ([weights[i] | i in knapsack]);
var int: profit = sum ([profits[i] | i in knapsack]);

constraint weight <= capacity;

solve maximize profit;

output ["knapsack = \(knapsack)\n",
        "weight = \(weight)/\(capacity)\n",
        "profit = \(profit)"]

输出：

knapsack = {I1, I2}
weight = 3/5
profit = 3
----------
knapsack = {I1, I3}
weight = 4/5
profit = 4
----------
knapsack = {I1, I4}
weight = 5/5
profit = 5
----------
==========

请告诉我为什么输出是这样的？我期待以下形式的回答：

% profit 5 for all
{ I1, I4 }
{ I2, I3 }
{ I5 }

解算器：Gecode 6.3.0

Answer 1

如果我正确理解你的问题，你期望输出应该显示所有最优解。对吗？

但是，这是一个优化问题，只显示一个最优解。前两个“解决方案”是具有增加值 profit（3 和 4）的中间解决方案。最后一个解（profit = 5）就是最优解：{I1, I4}.

如果您想要所有最优解（profit = 5），您必须将其添加为约束并将 solve maximize profit 更改为 solve satisfy:

constraint profit = 5;
        
% solve maximize profit;
solve satisfy;

那么输出将是：

knapsack = {I1, I4}
weight = 5/5
profit = 5
----------
knapsack = {I2, I3}
weight = 5/5
profit = 5
----------
knapsack = {I5}
weight = 5/5
profit = 5
----------
==========

我不知道 MiniZinc（或 FlatZinc 解算器）的任何标志会直接打印所有最优解（即没有上述手动处理）。但是，这可以使用 Python 接口 MiniZinc Python (https://minizinc-python.readthedocs.io/en/latest/ )

更新

这里有一个 Python 模型（使用 MiniZinc-Python），用于显示所有最优解。除了没有 solve 行外，MiniZinc 模型与所述相同。这是由 Python 程序添加的，是获得所有最优解的关键。

from minizinc import Instance, Model, Solver

gecode = Solver.lookup("gecode")

model = Model("./discrete_knapsack.mzn")
instance = Instance(gecode, model)

with instance.branch() as opt:
    opt.add_string("solve maximize profit;\n")
    res = opt.solve()
    obj = res["objective"]

instance.add_string(f"constraint sum ([profits[i] | i in knapsack]) = {obj};\n")

result = instance.solve(all_solutions=True)
for sol in result.solution:
    print(sol)
    print()

输出为：

knapsack = {I1, I4}
weight = 5/5
profit = 5

knapsack = {I2, I3}
weight = 5/5
profit = 5

knapsack = {I5}
weight = 5/5
profit = 5

（该程序的灵感来自 MiniZinc-Python 示例 https://minizinc-python.readthedocs.io/en/latest/basic_usage.html#finding-all-optimal-solutions ）

迷你锌。离散背包问题。 Аn难以理解的解决方案

MiniZinc. Discrete knapsack problem. Аn incomprehensible solution

knapsack-problem

minizinc