Wednesday, March 5, 2014

Appointment scheduling in Clojure with Loco

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.

29 comments:

  1. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download Now

      >>>>> Download Full

      Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download LINK

      >>>>> Download Now

      Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download Full

      >>>>> Download LINK WF

      Delete
  2. Hi Mark,

    many thanks for this non-trivial, but not too complicated, Loco introduction! What a mighty tool ...
    Kudos to aengelberg for writing this nice library!

    Best,
    Andreas

    ReplyDelete
  3. Thanks for one marvelous posting! I enjoyed reading it; you are a great author. I will make sure to bookmark your blog and may come back someday. I want to encourage that you continue your great posts.
    apple service center in chennai
    apple mobile service centre in chennai
    apple service center near me

    ReplyDelete
  4. I learned World's Trending Technology from certified experts for free of cost. I got a job in decent Top MNC Company with handsome 14 LPA salary, I have learned the World's Trending Technology from python training in btm layout experts who know advanced concepts which can help to solve any type of Real-time issues in the field of Python. Really worth trying Freelance SEO expert in Bangalore

    ReplyDelete
  5. It’s great to come across a blog every once in a while that isn’t the same out of date rehashed material. Fantastic read.
    Datascience Course in Chennai | Datascience Training in Chennai

    ReplyDelete
  6. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful . digital marketing training in bangalore

    ReplyDelete
  7. Thanks for sharing this blog. This very important and informative blog.MSBI Training in Bangalore




    Thanks for sharing this blog. This very important and informative blog.MSBI Training in Bangalore




    Thanks for sharing this blog. This very important and informative blog.MSBI Training in Bangalore




    Thanks for sharing this blog. This very important and informative blog.MSBI Training in Bangalore

    Thanks for sharing this blog. This very important and informative blog.MSBI Training in Bangalore







    ReplyDelete
  8. such a great word which you use in your article and article is amazing knowledge. thank you for sharing it.

    Upgrade your career Learn Oracle Training from industry experts gets complete hands on Training, Interview preparation, and Job Assistance at My Training Bangalore.

    ReplyDelete
  9. Such a great information for blogger iam a professional blogger thanks…

    Learn DevOps Training from the Industry Experts we bridge the gap between the need of the industry. Softgen Infotech provide the Best DevOps Training in Bangalore with 100% Placement Assistance. Book a Free Demo Today.

    ReplyDelete
  10. I am glad to read that you come up with outstanding information that definitely allows me to share with others. Thank you for sharing this with us.

    digital marketing course in hubli

    ReplyDelete
  11. I’m really happy with this informative blog, thank you so much for sharing this. Ogen Infosystem infosystem is a leading Web Designing and SEO Service provider in Delhi, India.
    SEO Service in Delhi

    ReplyDelete
  12. Usually I never comment on blogs but your article is so convincing that I never stop myself to say something about it. Just have a look at this Air Hostess course

    ReplyDelete
  13. Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download Now

    >>>>> Download Full

    Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download LINK

    >>>>> Download Now

    Thoughts On Programming: Appointment Scheduling In Clojure With Loco >>>>> Download Full

    >>>>> Download LINK VQ

    ReplyDelete
  14. i'm dazzled. I don't assume Ive met each body who knows as an incredible arrangement simply extra or considerably less this present circumstance as you reach. you are in goal of truth handily proficient and colossally sparkling. You thought of something that individuals ought to get and made the trouble energizing for us all. absolutely, satisfying website you have came.. Razer Surround Pro Keygen

    ReplyDelete
  15. Python has a remarkable amount of capability and a relatively simple syntax. It may be extended in C or C++ and offers interfaces for many system calls, libraries, and window systems. To learn more about python, join Python Training in Chennai at FITA Academy.
    Python Training in Chennai
    Python Online Course
    Python Training in Bangalore

    ReplyDelete