Fun with MiniZinc: Christmas gifts distribution
Update 2019-04-13: After following two MiniZinc courses on Coursera (Basic Modeling for Discrete Optimization and Advanced Modeling for Discrete Optimization), I revisited and improved the MiniZinc model presented in this post.I recommend these courses if you want to learn more about MiniZinc and the topic of discrete optimization.
MiniZinc is a free and open source constraint modeling language that can be used to model optimization problems in a solver independent way. We've been evaluating MiniZinc for the last few weeks in order to determine if we could use at it work to model our scheduling and routing problems.
Since it's Christmas time, and in order to present MiniZinc to the team in an entertaining manner, we created a fictitious Christmas employee gift distribution problem. I've simplified the problem a bit by reducing the number of gifts and employees in order to reproduce it on this blog.
The gift distribution problem #
First, let's state the problem in plain English:
The company would like to offer gifts to their 6 employees (James, Mary, Robert, Linda, David and Sarah). They set a budget between $1000 and $2000 and would like to spend at least $120 per employee.
They put together a list of potential gifts (Tech gifts, gift cards, etc) and gathered information about people preferences. For instance, an iPhone owner might like to get AirPods, unless they already own a pair. A gamer might like to get an Xbox or a gift card to buy games, and so on...
Employees might receive one or two gifts, depending on the value the gifts. All the gifts must be unique.
Overall, the company wants their employees to be satisfied with the gift(s) they receive, so they want to find the optimal gift distribution in order to make everyone happy.
The code #
So now let's write the MiniZinc program to solve this problem. I added as much comments as possible in order to describe what's going on:
/*
DECLARATIONS
*/
% An enumeration of Employees
enum EMPLOYEES = {
James,
Mary,
Robert,
Linda,
David,
Sarah
};
% An enumeration of Products
% The first item labelled "Nothing" represents the abscence of a product
enum PRODUCTS = {
/* 0 */ Nothing,
/* 1 */ AirPods,
/* 2 */ XBoxOneS,
/* 3 */ GoogleHomeSpeaker,
/* 4 */ HueStarterKit,
/* 5 */ RestaurantFor2,
/* 6 */ ThreeDPrinter,
/* 7 */ SportsExpertsGiftCard,
/* 8 */ BestBuyGiftCard,
/* 9 */ AppleTV4K,
/* 10 */ AmazonGiftCard,
/* 11 */ SonosOne,
/* 12 */ BotaBotaGiftCard,
/* 13 */ GoPro7,
/* 14 */ OculusGo,
/* 15 */ BoseQuietConfort,
/* 16 */ PlexPass,
/* 17 */ PSN12Months,
/* 18 */ Chromecast
};
% The index set of the PRODUCT enum is 1-based, but we want a 0-based index set (Nothing = 0)
set of int: PRODUCTS0 = 0..card(PRODUCTS)-1;
% The price for each product in the enumeration.
% The values are bounded between 0 and 500
% The value of "Nothing" is 0.
array[PRODUCTS0] of 0..500: prices = array1d(PRODUCTS0,
[0, 220, 230, 180, 160, 200, 280, 100, 100, 230, 100, 250, 150, 269, 280, 330, 160, 70, 45]);
% 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
% HAPPINESS is a set of integers representing the range of possible values for happiness
set of int: HAPPINESS = -10..10;
% This table represents the level of happiness (-10 to +10) of each employee receiving the corresponding product
array[EMPLOYEES,PRODUCTS0] of HAPPINESS: happiness = array2d(EMPLOYEES, PRODUCTS0,
/* James */ [ 0, 10, 10, 0, 5, 6, 0, -2, 2, 6, 4, 3, 1, 1, 9, 4, -5, -10, 0,
/* Mary */ 0, 10, -10, -5, -2, 2, 2, -3, 0, 7, 3, -4, 4, 6, 7, 3, 9, 6, -7,
/* Robert */ 0, -10, 7, 5, 4, 6, 3, 5, 3, 5, 6, 6, 3, 6, -6, 2, -10, -5, 5,
/* Linda */ 0, -5, 3, 5, -2, 5, 4, 5, 2, -5, 4, 3, -9, 2, 9, 4, -10, 4, 6,
/* David */ 0, 5, 9, 6, -2, -2, -10, 4, 7, -3, 6, 1, 2, 5, 7, -10, -10, -7, 7,
/* Sarah */ 0, 3, -4, 2, -3, -2, -3, 5, 2, -3, 3, -3, 3, 4, 6, 8, 5, 5, 3 ]);
% 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
% MINVALUE is a constant representing the minimum spending per employee
int: MINVALUE = 120;
% This array will contain the result of the gifts distribution.
% Each employee can receive 1 or 2 gifts, so it's a 2-dimensional array.
array[EMPLOYEES, 1..2] of var PRODUCTS0: gifts;
/*
CONSTRAINTS
*/
% This predicate checks that all values in an array are different, except for 0 that can repeat.
% Constraint: All gifts are different, except Nothing that can be used multiple times
include "alldifferent_except_0.mzn";
constraint alldifferent_except_0(array1d(gifts));
% Constraint: Everyone must receive a 1st gift (!= Nothing) */
constraint forall(i in EMPLOYEES)
(gifts[i, 1] != 0);
% Constraint: If one receives a 1st gift which value is greater that MINVALUE, they don't receive a 2nd gift
constraint forall (i in EMPLOYEES)
(prices[gifts[i, 1]] > MINVALUE -> gifts[i, 2] == 0);
% Constraint: The value of the 2nd gift must be lower or equal to the value of the 1st gift
constraint forall (i in EMPLOYEES)
(prices[gifts[i, 1]] >= prices[gifts[i, 2]]);
% Constraint: The combined value of the 1st and 2nd gift must be greater than MINVALUE
constraint forall (i in EMPLOYEES)
(sum (j in 1..2)
(prices[gifts[i, j]]) > MINVALUE);
% Constraint: Everyone must have at least 7 happiness score
constraint forall (i in EMPLOYEES)
(sum(j in 1..2)
(happiness[i, gifts[i, j]]) > 6);
% Contraint: We have a budget and want to spend between $1000 and $2000
var int: cost = sum (i in EMPLOYEES, j in 1..2)
(prices[gifts[i, j]]);
constraint cost > 1000 /\ cost < 2000;
/*
OBJECTIVE
*/
/* The objective is to maximize happiness */
var -100..100: objective;
constraint objective = sum (i in EMPLOYEES, j in 1..2)
(happiness[i, gifts[i, j]]);
% This starts the solver
solve maximize objective;
/*
OUTPUT
*/
output
[ "Cost ($): \(cost)\n" ] ++
[ "Happiness : \(objective)\n" ] ++
[ "\(e)\t: \(PRODUCTS[gifts[e, 1] + 1]) and \(PRODUCTS[gifts[e, 2] + 1]) ($\(sum (i in 1..2) (prices[gifts[e, i]])), 😊 \(sum(i in 1..2) (happiness[e, gifts[e, i]])));\n" | e in EMPLOYEES ]
After running it, here's the output of the problem:
Cost ($): 1405
Happiness : 62
James : XBoxOneS and Nothing ($230, 😊 10);
Mary : AirPods and Nothing ($220, 😊 10);
Robert : AmazonGiftCard and SportsExpertsGiftCard ($200, 😊 11);
Linda : OculusGo and Nothing ($280, 😊 9);
David : BestBuyGiftCard and Chromecast ($145, 😊 14);
Sarah : BoseQuietConfort and Nothing ($330, 😊 8);
The solver found the optimal distribution of gifts in order to maximize happiness while respecting the various constraints, like our budget. Of course we can get different results by changing the budget of tinkering with the "happiness" values.
Conclusion #
The aspect of MiniZinc I like the most is the clean syntax that let you write highly readable models. The same problem written in C# (using or-tools or IBM CP Optimizer for instance) would be less readable and hard to follow.
Another interesting aspect is the ability to model optimization problems in a solver independent way. We were able to model problems and solve them with multiple solvers including or-tools and IBM CP Optimizer.
However, while MiniZinc usually gives good results for reasonably simple problems, our models written directly for CP Optimizer in C# outperforms the MiniZinc models significantly when the problem contains a lot of variables (think of the problem described in this post, but with hundreds of employees), even though the same solver is used under the hood. We were not able to determine why.
Nonetheless, I had a lot of fun learning MiniZinc and I think it is a great tool to grasp constraint-based modeling.