Loco makes it easy to declaratively build constraint satisfaction models. In this blog post, we’ll look at a common use for constraint programming – appointment scheduling – and in so doing, we’ll see some of the ways that Loco goes beyond the features found in other Clojure constraint libraries.
(use 'loco.core 'loco.constraints)
Scheduling appointments with no conflicts
Imagine you have four people coming in for an interview, and you’ve set aside four timeslots in your day to conduct these interviews. You ask each person to list the timeslots when he/she can potentially come in.
Let’s use 0-based indexing to refer to the people, and 1-based indexing to refer to the timeslots.
Person 0 says she can come in at any of the four timeslots: 1, 2, 3, or 4.
Person 1 says he can come in at timeslot 2 or 3.
Person 2 says she can come in at timeslot 1 or 4.
Person 3 says he can come in at timeslot 1 or 4.
So the availability data looks like this:
(def availability
[[1 2 3 4]
[2 3]
[1 4]
[1 4]])
Let the variable [:person 0] denote the timeslot when person 0 is scheduled to come in, [:person 1] when person 1 comes in, etc.
(def person-vars
(for [i (range (count availability))] [:person i]))
We want to constrain each [:person i] variable to the available timeslots.
(def availability-constraints
(for [i (range (count availability))]
($in [:person i] (availability i))))
We want to ensure we don’t schedule two people in the same timeslot.
(def all-different-constraint
(apply $all-different? person-vars))
For convenience, let’s assemble the constraints into one big list (the order doesn’t matter in Loco):
(def all-constraints
(conj availability-constraints all-different-constraint))
Now we’re ready to solve. Let’s dump the solution into a sorted-map for easy readability.
=> (into (sorted-map) (solution all-constraints))
{[:person 0] 3, [:person 1] 2, [:person 2] 4, [:person 3] 1}
So there you have it. Once we’ve played around with this example interactively in the REPL, and are confident in the model, we can easily abstract this into a function that takes availability data, and returns the schedule:
(defn schedule [availability]
(->>
(solution
(conj
(for [i (range (count availability))]
($in [:person i] (availability i)))
($distinct
(for [i (range (count availability))] [:person i]))))
(into (sorted-map))))
=> (schedule
[[1 3 5]
[2 4 5]
[1 3 4]
[2 3 4]
[3 4 5]])
{[:person 0] 5, [:person 1] 4, [:person 2] 1, [:person 3] 2, [:person 4] 3}
I think the declarative Loco way of modeling constraints is concise and elegant, but this example could just as easily be done in, say, core.logic. So let’s push beyond, into an area that (as far as I know) can’t be done with core.logic.
Scheduling appointments minimizing conflicts
The above scheduler is somewhat naive.
=> (schedule
[[1 2 3 4]
[1 4]
[1 4]
[1 4]])
{}
This doesn’t work because there’s no way to satisfy the constraint that no two people can be scheduled in the same timeslot.
But let’s say, hypothetically, that if absolutely necessary, we can potentially squeeze two candidates into the same timeslot. We’d rather not, but we can do it if we have to. Can we build a model for this?
Again, let’s start exploring the problem interactively with global defs and playing around with it at the REPL. Here’s the problematic availability example:
(def availability
[[1 2 3 4]
[1 4]
[1 4]
[1 4]])
As before, we’ll want to constraint each person’s timeslot to his/her availability schedule:
(def availability-constraints
(for [i (range (count availability))]
($in [:person i] (availability i))))
Let’s define a few names for convenience. Let timeslots be a list of all the timeslot numbers.
(def timeslots (distinct (apply concat availability)))
Let person-vars be the list of all [:person i] variables.
(def person-vars
(for [i (range (count availability))] [:person i]))
Now for the interesting part. We want to allow up to 2 people in a given timeslot. So we’ll let the variable [:num-people-in-timeslot 1] be the number of people signed up for timeslot 1, and so on. Let people-in-timeslot-vars be the list of all such variables.
(def people-in-timeslot-vars
(for [i timeslots] [:num-people-in-timeslot i]))
Now, we create a list of constraints that state that each of these [:num-people-in-timeslot i] variables ranges between 0 and 2.
(def conflict-constraints
(for [i timeslots]
($in [:num-people-in-timeslot i] 0 2)))
To give these :num-people-in-timeslot variables the appropriate meaning, we need to bind each [:num-people-in-timeslot i] variable to the number of times i occurs among the variables [:person 1], [:person 2], etc. Loco’s $cardinality constraint allows us to do exactly that. For example,
($cardinality [:x :y :z] {1 :number-of-ones})
will bind :number-of-ones to the number of times 1 occurs among :x, :y, and :z. So, the following constraint will bind all the [:num-people-in-timeslot i] variables to their appropriate values.
(def number-in-timeslots
($cardinality person-vars
(zipmap timeslots people-in-timeslot-vars)))
To minimize the number of conflicts, we need to count the number of conflicts.
Let the variable :number-of-conflicts stand for the number of timeslot conflicts we have. We need two constraints on :number-of-conflicts. The first constraint just sets up the finite domain that the variable could range over (i.e., 0 to the total number of timeslots). We need to do this because in Loco, every variable must be declared somewhere in the model. The second constraint binds :number-of-conflicts to the number of times 2 appears in the variables [:num-people-in-timeslot 1], [:num-people-in-timeslot 2], etc.
(def number-of-conflicts
[($in :number-of-conflicts 0 (count timeslots))
($cardinality people-in-timeslot-vars {2 :number-of-conflicts})])
We built the constraints in parts; now building the model is simply a matter of concatting all the constraints together. (Note that number-in-timeslots is a single constraint, so we concatenate [number-in-timeslots] in with the other lists of constraints).
(def all-constraints (concat availability-constraints
conflict-constraints
[number-in-timeslots]
number-of-conflicts))
Now, we’re all set up to solve the model.
=> (solution all-constraints
:minimize :number-of-conflicts)
{[:person 0] 2,
[:person 1] 4,
[:person 2] 4,
[:person 3] 1,
:number-of-conflicts 1,
[:num-people-in-timeslot 1] 1,
[:num-people-in-timeslot 2] 1,
[:num-people-in-timeslot 3] 0,
[:num-people-in-timeslot 4] 2}
In the final version, we really only want to see the [:person i] variables; Loco allows us to hide the other variables from the output by prepending an underscore character in front of the variable names.
So let’s abstract this into a more robust schedule-with-conflicts function.
(defn schedule-with-conflicts [availability]
(let [timeslots (distinct (apply concat availability)),
availability-constraints
(for [i (range (count availability))]
($in [:person i] (availability i))),
person-vars
(for [i (range (count availability))] [:person i]),
people-in-timeslot-vars
(for [i timeslots] [:_num-people-in-timeslot i]),
conflict-constraints
(for [i timeslots]
($in [:_num-people-in-timeslot i] 0 2)),
number-in-timeslots
($cardinality person-vars
(zipmap timeslots people-in-timeslot-vars)),
number-of-conflicts
[($in :_number-of-conflicts 0 (count timeslots))
($cardinality people-in-timeslot-vars {2 :_number-of-conflicts})]
all-constraints (concat availability-constraints
conflict-constraints
[number-in-timeslots]
number-of-conflicts)]
(into (sorted-map)
(solution all-constraints :minimize :_number-of-conflicts))))
Let’s give it a spin:
=> (schedule-with-conflicts
[[1 2 3 4]
[1 4]
[1 4]
[1 4]])
{[:person 0] 2, [:person 1] 4, [:person 2] 4, [:person 3] 1}
Written with StackEdit.
Permalink
