Simple example of using JuMP to figure out snack calendar for children in Montessori Children's House classroom

snacks.jl

"""
@file      snacks.jl

@author    Scott Paul Jones
@copyright 2015
@license   MIT

@brief     Build snack calendar for children, using constraint engine

Changes
-------

- **2015-11-16** [Scott Jones] Initial implementation
"""
module snacks end
typealias DictAny Dict{Symbol, Any}

const debug = false

const vacation_days =
    (Date("2015-11-25"):Date("2015-11-27"),     # Thanksgiving
     Date("2015-12-21"):Date("2016-01-03"),     # Winter Break
     Date("2016-01-18"),                        # Martin Luther King
     Date("2016-02-15"):Date("2016-02-19"),     # School Vacation Week - Winter
     Date("2016-03-18"),                        # Parent-Teacher Conference Day
     Date("2016-04-18"):Date("2016-04-22"),     # School Vacation Week - Spring
     Date("2016-06-10"))                        # Parent-Teacher Conference Day

const zulima =
    DictAny(:classroom => "CH1",
            :teachers  => ("Zulima Martín García", "Celia"),
            :students  => ["Julian", "Nicolas", "Inés", "Selina", "Juan", "David",
                           "Carlos", "Lorenzo", "Christina", "Alonso", "Maria", "Pablo",
                           "Francisco", "Ricardo", "Elia", "Ana"],
            :nosnackdays => ("2016-01-04",),
            :history => [("2015-11-24", "Carlos"),
                         ("2015-11-30", "Selina"),
                         ("2015-12-01", "Christina"),
                         ("2015-12-02", "Alonso"),
                         ("2015-12-03", "Elia"),
                         ("2015-12-04", "Juan"),
                         ("2015-12-07", "Nicolas"),
                         ("2015-12-08", "Ana"),
                         ("2015-12-09", "Francisco"),
                         ("2015-12-10", "David"),
                         ("2015-12-11", "Lorenzo"),
                         ("2015-12-14", "Pablo"),
                         ("2015-12-15", "Ricardo"),
                         ("2015-12-16", "Maria"),
                         ("2015-12-17", "Julian"),
                         ("2015-12-18", "Inés")],
            :sameparents => (("Nicolas", "Juan"), ("Francisco", "Ricardo")),
            :away      => [("Julian", ["2015-12-04", "2016-01-04"]),
                           ("Lorenzo", ["2015-12-02"])],
            :schedules => [("MTW", ["Francisco", "Ricardo"]),
                           ("TWR", ["Elia"]),
                           ("MTWF", ["Ana"])])

#export makecalendar

using JuMP

function setupcalendar(no_school_days, date, enddate)
    cnt = 0
    const d1 = Dates.Day(1)
    dowvec = Vector{Int8}()
    dayvec = Vector{Date}()
    vacvec = Set{Date}()
    for dr in no_school_days
        if isa(dr, Date)
            push!(vacvec, dr)
        else
            for d in dr
                push!(vacvec, d)
            end
        end
    end
    while date <= enddate
        dow = Dates.dayofweek(date)
        if dow <= 5 && !(date in vacvec)
            push!(dowvec, dow)
            push!(dayvec, date)
        end
        date += d1
    end
    dowvec, dayvec
end

function makecalendar(nam, classroom, vacation_days, startdate, enddate)
    classkeys = keys(classroom)
    students = classroom[:students]
    numkids = length(students)
    kiddow = Vector{UInt8}(numkids)
    kidvec = Vector{Set{Date}}(numkids)
    push!(students, "No snack")
    nosnack = Set{Int}()
    cvthistory = Vector{NTuple{2,UInt16}}()
    dowvec, dayvec = setupcalendar(vacation_days, Date(startdate), Date(enddate))
    inv = Dict{ByteString, Int}()
    for i = 1:numkids
        kidvec[i] = Set{Date}() # default, no extra away days
        kiddow[i] = 0x1f # default, comes every day
        inv[students[i]] = i
    end
    if debug
        println(dowvec)
        println(dayvec)
        println("numkids = ",numkids)
        println("inv = ",inv)
    end
    if :schedules in classkeys
        for exp in classroom[:schedules]
            days = exp[1]
            kids = exp[2]
            dayflg = 0x00
            for i in days
                if i == 'M'
                    dayflg |= 0x01
                elseif i == 'T'
                    dayflg |= 0x02
                elseif i == 'W'
                    dayflg |= 0x04
                elseif i == 'R'
                    dayflg |= 0x08
                elseif i == 'F'
                    dayflg |= 0x10
                else
                    throw(ArgumentError("Bad day of week schedule input: $days"))
                end
            end
            for k in kids
                kiddow[inv[k]] = dayflg
            end
        end
    end
    if :away in classkeys
        for exp in classroom[:away]
            kv  = kidvec[inv[exp[1]]]
            for awayday in exp[2]
                push!(kv, Date(awayday))
            end
        end
    end
    if :nosnackdays in classkeys
        for nosnackday in classroom[:nosnackdays]
            day = findnext(dayvec, Date(nosnackday), 1)
            day != 0 && push!(nosnack, day)
        end
    end

    # Convert history information
    if :history in classkeys
        for pair in classroom[:history]
            day = findnext(dayvec, Date(pair[1]), 1)
            kid = findnext(students, pair[2], 1)
            kid == 0 && throw(ArgumentError("Invalid child name in history: $(pair[2])"))
            day != 0 && push!(cvthistory, (kid, day))
        end
    end

    if debug
        @show kiddow
        @show kidvec
        @show cvthistory
        @show nosnack
    end
    sol = SolveModel(numkids, dowvec, dayvec, kiddow, kidvec, cvthistory, nosnack)
    nameofday = ("Monday:   ", "Tuesday:  ", "Wednesday:", "Thursday: ", "Friday:   ")
    for day = 1:length(sol)
        println(dayvec[day]," ",nameofday[dowvec[day]]," ",students[sol[day]])
    end
    clsrm = classroom[:classroom]
    open(string(nam, ".ics"), "w") do io
        println(io, "BEGIN:VCALENDAR")
        println(io, "VERSION:2.0")
        for day = 1:length(sol)
            dv  = replace(string(dayvec[day]),"-","")
            println(io, "BEGIN:VEVENT")
            println(io, "DTSTART;VALUE=DATE:", dv)
            println(io, "DTEND;VALUE=DATE:",  dv)
            println(io, "SUMMARY: ", students[sol[day]])
            println(io, "LOCATION:", clsrm)
            println(io, "DESCRIPTION:Snack")
            println(io, "END:VEVENT")
        end
        println(io, "END:VCALENDAR")
    end
    for i=1:numkids
        open(string(nam,"_",i,".ics"), "w") do io
            println(io, "BEGIN:VCALENDAR")
            println(io, "VERSION:2.0")
            for day = 1:length(sol)
                if sol[day] == i
                    dv  = replace(string(dayvec[day]),"-","")
                    println(io, "BEGIN:VEVENT")
                    println(io, "DTSTART;VALUE=DATE:", dv)
                    println(io, "DTEND;VALUE=DATE:",  dv)
                    println(io, "SUMMARY: ", students[i])
                    println(io, "LOCATION:", clsrm)
                    println(io, "DESCRIPTION:Snack")
                    println(io, "END:VEVENT")
                end
            end
            println(io, "END:VCALENDAR")
        end
    end
    sol
end

# Solve model
function SolveModel(numkids, dowvec, dayvec, kiddow, kidvec, history, nosnack, prevday=true)
    snackmodel = Model()

    numdays = length(dayvec)

    @defVar(snackmodel, snackdays[1:numdays, 1:numkids+1], Bin)

    @addConstraints snackmodel begin
        # Constraint 1 - Only one child assigned for each day
        # Constraint 2 - Each child only assigned once per cycle
        # Constraint 3 - Don't have assignments too close from one cycle to the next
        # Constraint 4 - Take into account history
        # Constraint 5 - Make sure children with same parents are not assigned to close together
        # (not implemented yet)
        # Constraint 6 - (Optional) Make sure kids have class the the previous day
        #                (Note, a day when no snack is given is valid, as long as not
        #                a vacation day)
        row[day=1:numdays], sum(snackdays[day,:]) == 1
        nxt[day=numkids-3:numkids:numdays-numkids, kid=1:numkids],
            sum(snackdays[day:day+6,kid]) <= 1
    end

    day = 1
    while day < numdays
        lastday = min(day+numkids-1, numdays)
        nodays = length(intersect(day:lastday, nosnack))
        if nodays != 0
            while lastday != numdays
                lastday = min(lastday + nodays, numdays)
                nodays = length(intersect(day:lastday, nosnack))
                (lastday - day + 1) - nodays == numkids && break
            end
        end
        for kid=1:numkids
            if lastday - day + 1 < numkids
                @addConstraint(snackmodel, sum(snackdays[day:lastday, kid]) <= 1)
            else
                @addConstraint(snackmodel, sum(snackdays[day:lastday, kid]) == 1)
            end
        end
        day = lastday+1
    end
    for day=1:numdays, kid=1:numkids
        # Days of week
        if (kiddow[kid] & (1<<(dowvec[day]-1))) == 0
            @addConstraint(snackmodel, snackdays[day, kid] == 0)
        end
        # Specific kids' vacation days
        if dayvec[day] in kidvec[kid]
            @addConstraint(snackmodel, snackdays[day, kid] == 0)
        end
        # Check previous class day, to see if child will be present
        if day != 1 && prevday
            if (kiddow[kid] & (1<<(dowvec[day-1]-1))) == 0
                @addConstraint(snackmodel, snackdays[day, kid] == 0)
            end
            if dayvec[day-1] in kidvec[kid]
                @addConstraint(snackmodel, snackdays[day, kid] == 0)
            end
        end
    end

    # Add in history
    for (kid, day) in history
        @addConstraint(snackmodel, snackdays[day, kid] == 1)
    end
    
    # Add in no snack days
    for day=1:numdays
        if day in nosnack
            @addConstraint(snackmodel, snackdays[day, numkids+1] == 1)
        else
            @addConstraint(snackmodel, snackdays[day, numkids+1] == 0)
        end
    end
    
    # Solve it
    status = solve(snackmodel)

    # Check solution
    if status == :Infeasible
        error("No solution found!")
    else
        mipSol = getValue(snackdays)
        sol = zeros(Int, numdays)
        for day = 1:numdays, kid = 1:numkids+1
            if mipSol[day, kid] != 0
                sol[day] = kid
            end
        end
        return sol
    end

end

test(nam) = makecalendar(nam, zulima, vacation_days, "2015-11-24", "2016-06-17")