MiniZinc离散背包问题Gecode求解输出与预期不符原因问询

求解代码 #

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
----------
==========

预期输出（所有最大利润为5的解） #

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

使用的求解器为Gecode 6.3.0，请问为什么会出现实际输出与预期不符的情况？

解答 #

问题原因 #

输出和预期不符是两个默认配置导致的：

• 默认优化求解逻辑限制：solve maximize profit的默认配置下，求解器只会输出搜索过程中找到的逐步更优的解，一旦确认全局最优值（这里是利润5），就会直接终止搜索，不会主动枚举所有达到该最优值的不同解。你实际输出里最后一个解只是第一个被搜索到的最优解，其余两个同等最优的解还没被遍历到，搜索就结束了。
• 搜索顺序影响：Gecode的默认变量分支搜索顺序决定了第一个被找到的最优解是{I1, I4}，其余两个最优解{I2, I3}、{I5}的搜索优先级更低，不会被默认返回。

解决方法 #

如果要输出所有最优解，可以选择以下任意一种方案：

1. 修改模型代码：先跑一次得到最大利润为5后，添加约束constraint profit = 5;，将求解目标改为solve satisfy;，运行时加上-a参数要求输出所有满足约束的解，就能得到全部3组最优解。
2. 直接加运行参数：不用修改模型代码，运行MiniZinc时添加--all-optimal参数，求解器找到最优值后会继续枚举所有达到该最优值的解，命令示例：minizinc --solver gecode --all-optimal 你的模型文件名.mzn

内容的提问来源于stack exchange，提问作者Soul Colorful