CODEWITHSUNDEEP
constraint-programmingminizinc
Learning Developer
Learning Developer

Reputation: 77

Constraint to select certain items in MiniZinc

I am trying to create a model to work with a problem derived from the Set Packing problem.

In this case, I have a parameter called nRecipes that represents the number of recipes and another called nIngred that represents the number of ingredients. Each recipe has a specific nutritional value that is represented by the value parameter.

I want to choose a menu with at most numDishes recipes, so that the nutritional value of the menu is maximized. Another restriction is that each chosen dish does not contain any ingredients in the other chosen dishes.

I have tried the following:

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;

Test example:

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;

Expected Output:

Value:20
Recipe:{1,10}

Upvotes: 1

Views: 221

Answers (1)

Magnus &#197;hlander
Magnus &#197;hlander

Reputation: 1446

Here is one way, where the group variable has been flipped around to hold the ingredients per recipe (also renamed it ingredients). Now you can use all_disjoint to formulate the constraint that the selected dishes may not use the same ingredients.

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"];

running with the data:

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}];

gives:

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

Edit: A new version that allows choosing less dishes than num_dishes dishes if that gives a better objective value. This is done through the variable dishes that represents the number of actually chosen dishes. Non-used menus will have a value of 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])];

Edit: Another version using a set to represent 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)];

Upvotes: 2

Related Questions