Optimization with Loco

I had the pleasure of beta-testing Loco, which was announced today. Loco is a Clojure constraint solver library built on top of the Java library Choco. There are several constraint libraries available for Clojure, including core.logic, propaganda, and clocop, each with a slightly different focus.

The features that make Loco shine are the performance of the constraint engine, the fully declarative API, the ease with which one can build models, support for several interesting global constraints, and the ability to find an optimal solution for models with multiple solutions.

This is the first article of what I hope to be a series, detailing some of the interesting problems you can solve with Loco.

Scheduling Buses with Loco

(use 'loco.core loco.constraints)

Loco is a powerful and expressive constraint solver, but it can also be used to solve certain kinds of integer linear programs.

One classic example is bus scheduling. Imagine that we are city transportation planners and we want to minimize the number of buses we need to operate in order to meet demand. We know the number of buses demanded for four-hour blocks of time.

(def demands
  {:12am-4am  8
   :4am-8am  10
   :8am-12pm  7
   :12pm-4pm 12
   :4pm-8pm   4
   :8pm-12am  4})

So for example, this map tells us that there is sufficient demand for 8 buses operating between 12am and 4am.

The interesting twist is that buses operate for 8 hours at a time. So, if we set a bus into operation at 12am, it operates an 8-hour shift from 12am-8am. So the question is, how many buses do we need to run from 12am-8am, and from 4am-12pm, etc. in order to meet the above demands.

We can represent this by a series of variables, each of which must be an integer from 0 through 12 (since 12 is the maximum overall demand).

So with loco, we can get the solution quite simply:

(solution
  [($in :bus-12am-8am 0 12)
   ($in :bus-4am-12pm 0 12)
   ($in :bus-8am-4pm 0 12)
   ($in :bus-12pm-8pm 0 12)
   ($in :bus-4pm-12am 0 12)
   ($in :bus-8pm-4am 0 12)
   ($>= ($+ :bus-8pm-4am :bus-12am-8am) (demands :12am-4am))
   ($>= ($+ :bus-12am-8am :bus-4am-12pm) (demands :4am-8am))
   ($>= ($+ :bus-4am-12pm :bus-8am-4pm) (demands :8am-12pm))
   ($>= ($+ :bus-8am-4pm :bus-12pm-8pm) (demands :12pm-4pm))
   ($>= ($+ :bus-12pm-8pm :bus-4pm-12am) (demands :4pm-8pm))
   ($>= ($+ :bus-4pm-12am :bus-8pm-4am) (demands :8pm-12am))]
  :minimize
  ($+ :bus-12am-8am :bus-4am-12pm :bus-8am-4pm 
      :bus-12pm-8pm :bus-4pm-12am :bus-8pm-4am))

which yields

{:bus-8pm-4am 0, :bus-4pm-12am 4, :bus-12pm-8pm 7, 
 :bus-8am-4pm 5, :bus-4am-12pm 2, :bus-12am-8am 8}

Let’s see if we can generalize this to handle an arbitrary number of evenly-spaced time periods. Clearly, to do this we’ll need to get away from demands and variables that directly name the timespan. Instead, for our example in which we sliced the day into six 4-hour time periods, we can imagine indexing these blocks of time (0-based) as “Time period 0” through “Time period 5”. So we can just use a vector for our demands, for example:

[8 10 7 12 4 4]

means that 8 buses are demanded for time period “0” (corresponding to 12am-4am), 10 buses are demanded for time period “1” (corresponding to 4am-8am),… up to a demand of 5 buses for time period “5”.

We’ll make use of Loco’s ability to treat vectors as subscripted variables. So [:buses 0] denotes , which is our variable for how many buses we schedule starting at the beginning of time period 0 (i.e., 12am). [:buses 1] (i.e., ) is the variable for the number of buses starting at the beginning of time period 1, etc.

We will also need an input, span which indicates how many consecutive time periods are spanned by the bus’s shift. In our example, span would be 2 (because a bus works for 2 of our 4-hour time periods).

(defn minimize-buses
  "Takes a vector of the demands for any number of equally-spaced time slots.
   span is the number of time slots that a bus's operating time spans"
  [demands span]
  (let [time-slots (count demands),
        max-demand (apply max demands),

        declarations
        (for [i (range time-slots)]
          ($in [:buses i] 0 max-demand))

        constraints
        (for [i (range time-slots)]
          ($>=
            (apply $+ (for [j (range (inc (- i span)) (inc i))]
                        [:buses (mod j time-slots)]))
            (demands i)))]

    (solution
      (concat declarations constraints)
      :minimize (apply $+ (for [i (range time-slots)] [:buses i])))))

Let’s test it out on our original sample demand:

=> (minimize-buses [8 10 7 12 4 4] 2)
{[:buses 5] 0, [:buses 4] 4, [:buses 3] 7, [:buses 2] 5, [:buses 1] 2, [:buses 0] 8}

Hmmm, it’s a little hard to read. We can fix that:

=> (into (sorted-map) (minimize-buses [8 10 7 12 4 4] 2))
{[:buses 0] 8, [:buses 1] 2, [:buses 2] 5, [:buses 3] 7, [:buses 4] 4, [:buses 5] 0}

Good, same answer as before. But now we can easily adjust to alternative demand schedules. For example, here’s a solution for a demand schedule based on 2-hour time periods, while buses still work 8-hour shifts:

=> (into (sorted-map)
      (minimize-buses [1 5 7 9 11 12 18 17 15 13 4 2] 4))

{[:buses 0] 0, [:buses 1] 1, [:buses 2] 2, [:buses 3] 6, [:buses 4] 2,
 [:buses 5] 2, [:buses 6] 8, [:buses 7] 5, [:buses 8] 0, [:buses 9] 0,
 [:buses 10] 0, [:buses 11] 4}

Now, let’s try a demand schedule with 1-hour time periods, with buses working 8-hour shifts:

=> (into (sorted-map)
      (minimize-buses
        [1 3 5 7 9 11 12 13 14 15 16 19
         18 17 15 13 15 16 10 8 6 5 4 2]
        8))

Uh oh, this seems to run forever. We can fix this with the timeout feature. In the definition of minimize-buses, we change the call to solution as follows:

(solution
      (concat declarations constraints [constraint])
      :minimize (apply $+ (for [i (range time-slots)] [:bus i]))
      :timeout 1000)

The :timeout keyword specifies a number of milliseconds, after which the solver should return the best solution it has found so far:

=> (into (sorted-map)
      (minimize-buses
        [1 3 5 7 9 11 12 13 14 15 16 19
         18 17 15 13 15 16 10 8 6 5 4 2]
        8))

{[:bus 0] 1, [:bus 1] 2, [:bus 2] 2, [:bus 3] 2, [:bus 4] 2, [:bus 5] 2,
 [:bus 6] 1, [:bus 7] 1, [:bus 8] 2, [:bus 9] 3, [:bus 10] 3, [:bus 11] 5,
 [:bus 12] 1, [:bus 13] 1, [:bus 14] 2, [:bus 15] 2, [:bus 16] 2, [:bus 17] 0,
 [:bus 18] 0, [:bus 19] 0, [:bus 20] 0, [:bus 21] 0, [:bus 22] 0, [:bus 23] 0}

Written with StackEdit.