.. title: Emptying Cashless Keys with Minizinc
.. slug: emptying-cashless-keys-with-minizinc
.. date: 2019-01-26 16:25:32 UTC+01:00
.. tags: minizinc
.. category: walk-through
.. link:
.. description: Let's use Minizinc to buy as many coffees as possible and spending all our money!
.. type: text
.. image:: /images/20190126_105723_HDR-min.jpg
Since I bought my first `cashless key`_ to buy coffee at the company's
vending machine, I never managed to spend every cent in the key - always
fell short of 3 or 5 cents.
I always wondered: which/how many drinks should I buy to reach zero?
We will use Minizinc to answer this question.
What is Minizinc?
-----------------
Minizinc_ is a free and open source constraint modeling language. It can be used
to formally describe (*model*) constraint satisfaction and optimization problems
in a high-level, solver-independent way. It is available for all major platforms
as a command line tool, or bundled with an IDE, and several solvers.
In our case, we're going to solve an optimization problem!
An optimization problem is the problem of finding the *best* solution from
all solutions that respect the problem's constraints (*feasible solutions*).
How do we define the *best* solution, though? We use an *objective function*: a function
that, given a feasible solution, returns its value in the system we're studying.
Don't worry if you don't understand every single word right now, I'm going to explain them in a bit!
Let's write the model!
----------------------
So, let's start by defining the parameters of our problem.
We have a given amount in our key, and a list of beverages and their cost.
.. code::
% the initial amount in our cashless key
int: START_AMOUNT;
% the list of beverages (coffee, tea, chocolate, ...)
enum BEVERAGES;
% how much does a beverage cost?
array[BEVERAGES] of int: COST;
Let's then define how we should spend our money!
Our solution is defined as an array of integers - for each beverage *b*,
*quantity[b]* is the number of times I have to drink *b*.
.. code::
/* how many times do I have to drink a beverage B? */
array[BEVERAGES] of var int: quantity;
After defining the structure of the solution, we need to limit
the values we can assign to the solution. Assignments to *quantity*
must follow some rules - in this case, we must drink all beverages
at least zero times, and we must spend every single cent we have.
Every assignment that follows those rules is a *feasible solution* for the problem.
.. code::
/* constraint: cannot drink a negative amount of drinks! */
constraint forall(b in BEVERAGES)(quantity[b] >= 0);
/* constraint: we must spend exactly START_AMOUNT */
var int: spent = sum(b in BEVERAGES)(quantity[b] * COST[b]);
constraint START_AMOUNT - spent = 0;
At the end, we want to check **how** we are going to spend our money.
Our objective function is how many drinks we are going to buy.
We want to find an assignment of *quantity* that **maximizes**
the number of coffees we have to drink - hard earned money must not be wasted!
.. code::
/* the objective function! */
var int: how_many_drinks;
constraint how_many_drinks = sum(b in BEVERAGES)(quantity[b]);
% use `maximize` to drink as many coffees as possible
% use `minimize` to cut down on coffees and get to zero euro as fast as possible
solve maximize how_many_drinks;
Results
-------
Let's feed our model with a simplified instance of the problem: it will tell us that
we can buy 8 coffees and 2 chocolates, for a total of 10 drinks.
If we want to cut down on coffees, we can order 3 tea cups and 4 ginseng coffees.
.. code::
shell % cat data.dzn
START_AMOUNT = 260; % 2.60 euro
BEVERAGES = { coffee, tea, ginseng, chocolate };
COST = [ 25, 40, 35, 30 ];
shell % minizinc model.mzn --data data.dzn
quantity = array1d(BEVERAGES, [8, 0, 0, 2]);
how_many_drinks = 10;
----------
==========
shell % # update the model to solve the minimization problem
shell % minizinc model.mzn --data data.dzn --all
quantity = array1d(BEVERAGES, [8, 0, 0, 2]);
how_many_drinks = 10;
----------
quantity = array1d(BEVERAGES, [2, 0, 0, 7]);
how_many_drinks = 9;
----------
quantity = array1d(BEVERAGES, [0, 0, 4, 4]);
how_many_drinks = 8;
----------
quantity = array1d(BEVERAGES, [0, 3, 4, 0]);
how_many_drinks = 7;
----------
==========
Nothing stops us from adding more constraints, such as "I need to drink at
least one chocolate", or "I don't want to buy more than one cup of tea",
or that the number of drinks must be even because I offer coffees to a colleague.
Try to experiment, add your own constraints, add more beverages and modify the prices!
References
----------
* Example gist: https://gist.github.com/alfateam123/3241bf8070d490677a08b13059d4c833
* Basic Modeling on Coursera: https://www.coursera.org/learn/basic-modeling
* Wikipedia "Optimization Problem": https://en.wikipedia.org/wiki/Optimization_problem
-----------------------------------------------
If you liked this article, `Tag me`_ in a photo of your favorite morning beverage,
or consider offering me a Ko-fi_ !
.. _cashless key: https://duckduckgo.com/?q=cashless+vending+key&atb=v120-4&iar=images&iax=images&ia=images
.. _Minizinc: https://www.minizinc.org/
.. _`Tag me`: https://twitter.com/alfateam123
.. _Ko-fi: https://www.ko-fi.com/alessandrobalzano