Summary
Constraint programming is a declarative paradigm used to solve discrete optimization problems. This contrasts with the imperative paradigm that we are generally used to. The main components of a model are variables and constraints. A solution is an assignment of values to the variables such that the constraints are satisfied.
The piece of software that interprets this model is called a solver. The solution returned by the solver is now: 18. Previously there was a $9 difference between the largest and smallest contributions. The inner workings of a solvers are outside the scope of this article.
A practical example with Python and CP-SAT. Let's use this new CP knowledge to solve a more complex real-world example. The store is open from 8AM to 8PM every day, and each day is divided into three shifts of 4 hours. There are two roles in the store: cashier and restocker.
The function model creates and then returns a variable, which we store in schedule. This variable is equal to 1 if Emma does work as a restocker on the Monday evening shift, or to 0 if she doesn't. By following the problem description and constraining these variables, we should be able to get a schedule that satisfies the requirements of the store owner.
An employee can work either the morning or the evening shift, or neither of these shifts. If they do work 2 shifts in a day, we must ensure that there is no idle time between these shifts, as they would be idle for 4 hours during the afternoon shift. A single constraint can take care of both of these requirements.
An employee cannot work morning and afternoon shifts during the week, in order to attend his classes. He also cannot work the morning and morning shifts during week, to attend classes. The employee would like to distribute these equally between all employees, so we would like them to work equally on the weekend.
The solver takes as input a model, and returns a status and a solution. The solution (x, y) is called optimal. A solution is optimal when there does not exist another solution that is strictly better than it. If no solution has been found, the status returned is unknown. This means that while the solver has not found a solution, it does not know whether one exists (feasible) or if the problem has no solution (infeasable)
An objective allows us to minimize the value of an expression. We could, for example, minimize the shift difference between the employee who is assigned the fewest shifts and the one who is assign the most. We would like to distribute the shifts as fairly as possible between Emma, David, and Rebecca.
Thanks to this model, we could easily see that it would not be possible for Emma to take five days off as she initially wanted. In the end, we created a schedule that satisfied both the requiremends of the store owner, as well as the needs of the employees.
