Ограничение выбора определенных элементов в MiniZinc

Я пытаюсь создать модель для работы с проблемой, связанной с проблемой Set Packing.

В этом случае у меня есть параметр nRecipes, который представляет количество рецептов, и другой параметр, называемый nIngred, который представляет количество ингредиентов. Каждый рецепт имеет определенную пищевую ценность, которая представлена ​​параметром значение.

Я хочу выбрать меню, содержащее не более 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}

constraint-programming minizinc
person Learning Developer    schedule 02.12.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вот один из способов, когда переменная 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 блюд, если это дает лучшую объективную ценность. Это делается с помощью переменной 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)];
person Magnus Åhlander    schedule 03.12.2020
comment
Добавил версию с использованием исходных параметров. - person Magnus Åhlander; 04.12.2020
comment
Функция card() указывает количество элементов набора. Функция array2set() преобразует массив selected_menu в набор (чтобы мы могли использовать intersect). - person Magnus Åhlander; 04.12.2020
comment
Вы можете использовать sort(selected_menu) в операторе вывода или добавить ограничение нарушения симметрии, например constraint increasing(selected_menu); - person Magnus Åhlander; 04.12.2020
comment
Если вы конвертируете в набор (array2set()), вы получите желаемый результат. - person Magnus Åhlander; 05.12.2020
comment
output["Recipe: ", show(array2set(selected_menu))]; даст желаемый результат. - person Magnus Åhlander; 05.12.2020
comment
Я отредактировал вопрос, потому что модель не соответствует некоторым примерам. Прикрепляю один из них. - person Learning Developer; 06.12.2020
comment
Я добавил модифицированную модель, обрабатывающую случай, когда лучше выбирать меньшее, чем максимальное количество разрешенных меню. - person Magnus Åhlander; 07.12.2020
comment
Я отредактировал ответ, чтобы не использовать глобальные ограничения. Зачем тебе var set of RECIPES: menu;? - person Magnus Åhlander; 09.12.2020
comment
Добавлена ​​еще одна модель, в которой набор используется для представления selected_menu - person Magnus Åhlander; 10.12.2020