限制为 select MiniZinc 中的某些项目

Question

我正在尝试创建一个模型来处理源自 集装箱问题的问题。

在这种情况下，我有一个名为 nRecipes 的参数代表菜谱的数量，另一个名为 nIngred 的参数代表菜谱的数量配料。每个食谱都有特定的营养价值，由 value 参数表示。

我想选择最多numDishes道菜谱的菜单，让菜单的营养价值最大化。另一个限制是每个选择的菜肴不包含其他选择的菜肴中的任何成分。

我试过以下方法：

int: nRecipes;                                  
set of int: RECIPES = 1..nRecipes;              

array[RECIPES] of int: value;                   

int: nIngred;                             
set of int: INGREDIENTS = 1..nIngred;    
int: numDishes;                                 
  
array[INGREDIENTS] of set of RECIPES: group;

var set of RECIPES: menu; 


array[1..numDishes] of var RECIPES: selected_menu;

constraint menu <= selected_menu; % Error
constraint alldifferent(selected_menu);

solve maximize value;

测试示例：

nRecipes = 10;
value = [10,8,4,2,6,9,5,3,8,10];
group = [{1,4,6},{1,2,6,7},{1,3,6,8}, 
        {1,2,3},{2,9,10},{5,6,8,10},
        {7,8,10},{1,3,5}];
numDishes = 3;
nIngred = 8;

预期输出：

Value:20
Recipe:{1,10}

Answer 1

这是一种方法，其中 group 变量已翻转以保存每个食谱的成分（也将其重命名为 ingredients）。现在你可以使用all_disjoint来制定所选菜肴不能使用相同成分的约束。

include "globals.mzn";

int: nRecipes;                                  
set of int: RECIPES = 1..nRecipes;              

array[RECIPES] of int: value;                   

int: nIngred;                             
set of int: INGREDIENTS = 1..nIngred;    
int: numDishes;                                 
    
array[RECIPES] of set of INGREDIENTS: ingredients;

array[1..numDishes] of var RECIPES: selected_menu;

constraint all_disjoint([ingredients[selected_menu[i]] | i in 1..numDishes]);

var int: obj = sum([value[selected_menu[i]] | i in 1..numDishes]);
solve maximize obj;

output ["total value=\(obj)\n"] ++ 
["selected_menu=\(selected_menu)\n"] ++
["ingredients=\([ingredients[selected_menu[i]] | i in 1..numDishes])\n"];

运行数据：

numDishes = 2;
nIngred = 8;
nRecipes = 10;
value = [10,8,4,2,6,9,5,3,8,10];

ingredients = [{1,2,3,4},{2,4,5},{3,4,8}, 
        {1},{6,8},{1,2,3,6},
        {2,7},{3,6,7},{5},{5,6,7}];

给出：

total value=20
selected_menu=[10, 1]
ingredients=[5..7, 1..4]

编辑： 一个新版本，允许选择比 num_dishes 更少的菜肴，如果它提供更好的 objective 价值。这是通过代表实际选择的菜肴数量的变量 dishes 完成的。未使用的菜单的值为 0。

int: nRecipes;                                  
set of int: RECIPES = 1..nRecipes;              
set of int: RECIPES0 = 0..nRecipes;

array[RECIPES] of int: value;                   

int: nIngred;                             
set of int: INGREDIENTS = 1..nIngred;    
int: numDishes;                                 
    
var 1..numDishes: maxDishes;
    
array[INGREDIENTS] of set of RECIPES: group;

array[1..numDishes] of var RECIPES0: selected_menu;

constraint forall(i in INGREDIENTS)
    (sum(m in selected_menu)(m in group[i]) <= 1);

var int: obj = sum([value[selected_menu[i]] | i in 1..maxDishes]);
solve maximize obj;

output["Value: ", show(obj), "\nRecipe: ", show([selected_menu[d] | d in 1..maxDishes])];

编辑： 另一个版本使用集合来表示 selected_menu.

int: nRecipes;                                  
set of int: RECIPES = 1..nRecipes;              

array[RECIPES] of int: value;                   

int: nIngred;                             
set of int: INGREDIENTS = 1..nIngred;    
int: numDishes;
                            
array[INGREDIENTS] of set of RECIPES: group;

var 1..numDishes: dishes;
var set of RECIPES: selected_menu;

% each ingredients may appear in at most one recipe
constraint forall(i in INGREDIENTS)
    (card(selected_menu intersect group[i]) <= 1);
    
constraint card(selected_menu) <= dishes;    

var int: obj = sum([value[m] | m in selected_menu]);
solve maximize obj;

output["Value: ", show(obj), "\nRecipe: ", show(selected_menu)];

限制为 select MiniZinc 中的某些项目

Constraint to select certain items in MiniZinc

constraint-programming

minizinc