For endel år siden skulle jeg lage en bordplanleggingsmodul for et eventbyrå som arrangerte konferanser for tusenvis av deltakere. Det viste seg å være kombinatorisk mye mer komplisert enn jeg først antok. Etter litt research oppdaget jeg at det fantes noe som het constraint solvers. På relativt kort tid klart jeg å lage en løsning som ga veldig gode resultater innenfor akseptable tidsrammer.

La oss først gå litt inn på hva det er og så bruker vi mesteparten av tiden på et konkret eksempel

Litt bakgrunn

Constraint Programming

“Constraint programming is a paradigm for solving combinatorial problems…”
  • “Declarative constraints for feasible solutions”
  • “Do not specify a step or sequence of steps to execute”
  • “Backtracking, constraint propagation, branching heuristics”

      • Wikipedia

Constraint programming har sine røtter helt tilbake til Prolog og 80-tallet. Måten å tenke på er annerledes enn for imperativ og forsåvidt også funksjonell programmering. Veldig forenklet så funker det omtrent slik;

  1. Man definerer deklarativt beskrankninger (constraints) som løsningen skal/bør tilfredstille
  2. Man forer programmet med et problem i form av data i en eller annen form for datastruktur
  3. Programmet benytter seg av søkealgoritmer scoret/validert mot beskrankningene for å effektivt søke frem de beste løsningskandidatene

Constraint Solvers

Man kan kanskje si at Constraint Solvers er manifestasjonen av constraint programming. Disse manifestasjonene kan ha forskjellige nivåer;

  • Språk - Det finnes egne skreddersydde språk
  • Biblioteker - Det finnes en mengde biblioteker man kan bruke for de mange språk
  • Verktøysett/Rammeverk - Eksempelvis for java(/kotlin/python) har vi Timefold
  • Hyllevare - Tjenester eller skreddersydd pakke som kankje er spesielt tilpasset et gitt domene

Typiske bruksområder

Man bruker gjerne Constraint Solvers for kompliserte/omfattende planleggingsproblemer. Eksempler på typisk kommersiell bruk;

  • Ruteplanlegging for kjøretøy
  • Skiftplanlegging
  • Pakking av containere
  • Timeplanlegging (f.eks skole)
  • Konferanseplanlegging

Det er også ofte slik at man ikke nødvendigvis bare kjører en planlegging og så er man ferdig. I den virkelige verden så forandrer ting seg hele tiden. Derfor har man ofte behov for at constraint solver verktøyet man benytter har mulighet til å kontinuerlig re-planlegge basert på endringer i dataene for det underliggende problemet.

Timefold

Verktøyet jeg brukte for bordplanlegging het i sin tid Optaplanner (JBoss). Dette er nå blitt til Timefold. Det er et godt dokumentert open source verktøy/rammeverk skrevet i Java.

Det er relativt enkelt å ta i bruk og er bare noen maven/gradle besvergelser unna.

dependencies {
    implementation(platform("ai.timefold.solver:timefold-solver-bom:${timefoldSolverVersion}"))
    implementation("ai.timefold.solver:timefold-solver-core")
    implementation("ch.qos.logback:logback-core:1.5.16")
    implementation("ch.qos.logback:logback-classic:1.5.16")
    implementation("org.slf4j:slf4j-api:2.1.0-alpha1")
}

For å komme i gang så er det stort sett bare å;

  1. Modellere problemet i form av en domenemodell manifistert via java/kotlin klasser
  2. Definere beskrankninger via en DSL
  3. Konfigurere en solver
  4. Mate solveren med et problem og snurre film

Løsningsfasen i Timefold består av 2 faser.

  1. Konstruksjonsfasen: Denne fasen er rask og og benytter seg av enkle algoritmer/heurestikker (first fit/best fit/weakest fit m.fl) for å finne et brukbart utgangspunkt
  2. Lokalt søk fase: Denne fasen konfigurerer man til å kjøre så lenge det er hensiktsmessig(tm). Den benytter seg av mer avanserte heuristikker (hill climbing, tabu search, simulated annealing m.fl) for å søke etter stadig mer optimale løsninger i løsningsrommet.

I neste avsnitt viser vi et konkret eksempel på hvordan du kan ta i bruk Timefold.

Eksempel: Vaktliste på JavaZone

På JavaZone pleier Kodemaker å ha stand. Da har vi det slik at de kodemakerene som ikke holder foredrag får æren av å stå på standvakt. Det er alltid litt styr med å lage vaktliste selvom man kanskje ikke kan kalle det et kombinatorisk superkomplisert problem. Vi trenger ikke en Constraint Solver for å få det til, men vi er jo utviklere og her kan det spares noen minutter/timer samtidig som vi har det litt skøy. Etter nitidig kartlegging og diverse workshops med administrasjonen lander vi på et sett med krav.

  1. Must: En vakt skal ha 2 (forskjellige) kodemakere
  2. Must: En kodemaker kan ikke ha vakt på en innmeldt blokkert tid
  3. Should: Kodemakere ønsker færrest mulig vakter pr dag
  4. Should: Ved flere vakter ønsker man ikke å komme på vakt med en man har vært på vakt med tidligere

Domenemodell

Vi begynner med å definere en domenemodell for problemet vårt. Vi kunne modellert dette noe enklere om vi hadde bundet modellen til å bare støtte 2 stykker på vakt, men vi legger inn litt fleksibilitet vha mange-til-mange klassen ShiftAssignment.

Med en modell på plass kan vi begynne å implementere den i Kotlin. Dette gjør vi ganske enkelt ved å definere data klasser i Kotlin. De første klassene er relativt rett frem.

data class Timeslot(
    val dayOfWeek: DayOfWeek,
    val startTime: LocalTime,
    val endTime: LocalTime = startTime.plusMinutes(50)
)

data class Employee(
    val id: String,
    val name: String,
    val blockedSlots: List<Timeslot> = listOf(),
)

data class Shift(
    val id: String,
    val timeslot: Timeslot
)

For de to siste klassene må vi gi Timefold litt mer informasjon vha annotasjoner og svelge noen immutability-kameler.

@PlanningEntity
data class ShiftAssignment(
    @PlanningId
    val id: String,

    val shift: Shift,
    val shiftIdx: Int,

    @PlanningVariable
    var employee: Employee? = null,
) {
    // NOTE: Timefold requires a no-arg constructor (:
    @Suppress("unused")
    constructor() : this(
        "dummy[0]",
        Shift(id="dummy", timeslot = Timeslot(DayOfWeek.SUNDAY, LocalTime.of(0, 0))),
        0
    )
}


@PlanningSolution
data class Roster(
    // These are the entities we want timefold to plan for us
    @PlanningEntityCollectionProperty
    @ValueRangeProvider
    val shiftAssignments: List<ShiftAssignment> = emptyList(),

    // These are the facts available for the solution
    @ProblemFactCollectionProperty
    @ValueRangeProvider
    val employees: List<Employee> = emptyList(),

    @PlanningScore
    var score: HardSoftScore? = null,
)

Vi forteller Timefold at klassen ShiftAssignment er en planleggingsentitet og feltet vi vil ha hjelp med å sette er employee.

Klassen Roster fungerer som både;

  • En problemdefinisjon, altså noe vi gir som input til Timefold sin solver (mer om det litt senere)
  • Og den representerer løsningen som Timefold kom frem til etter den har kjørt ferdig (gitt tiden vi ga den til rådighet).

Det finnes mange måter å gi score til løsninger, vi har valgt å bruke en HardSoftScore her. Det matcher bra med våre Must og Should definisjoner. En løsning med negativ score i Hard (must) delen anser vi som en ugyldig løsning. Jo nærmere 0 Soft (should) vi treffer jo mer optimal løsning har vi.

Feltet score vil bli satt av Timefold ved å evaluere beskrankningsdefinisjonene vi har definerer.

Beskrankninger

Det neste vi må gjøre er å definere beskrankningene basert på kravlisten vår. Dette kan vi gjøre i Timefold ved å benytte oss av en DSL. Denne DSL’en er basert på en java streaming API og er optimalisert for ytelse. Det er viktig at evaluering av beskrankningene går så raskt som mulig da disse kjøres for hver permutasjon Timefold prøver. For problemer som er kombinatorisk mye større enn dette eksemplet blir det fort veldig mange ganger 😅

private fun shiftMustHaveDifferentEmployees(constraintFactory: ConstraintFactory): Constraint =
        constraintFactory
            .forEachUniquePair(
                ShiftAssignment::class.java,
                Joiners.equal(ShiftAssignment::shift),
                Joiners.equal(ShiftAssignment::employee)
            )
            .penalize(HardSoftScore.ONE_HARD)
            .asConstraint("Must be different Employees in a shift")

private fun mustNotBeAssignedToBlockedOutSlot(constraintFactory: ConstraintFactory): Constraint =
        constraintFactory
            .forEach(ShiftAssignment::class.java)
            .filter {
                it.employee?.blockedSlots?.contains(it.shift.timeslot) ?: false
            }.penalize(HardSoftScore.ONE_HARD)
            .asConstraint("Employee must be available for timeslot in shift")

private fun shouldHaveAsFewShiftsAsPossiblePerDay(constraintFactory: ConstraintFactory): Constraint =
        constraintFactory.forEachUniquePair(
            ShiftAssignment::class.java,
            Joiners.equal(ShiftAssignment::employee),
            Joiners.equal { it.shift.timeslot.dayOfWeek },
        ).penalize(HardSoftScore.ONE_SOFT)
            .asConstraint("Penalize multiple timeslots per day")


private fun shouldHaveDifferentEmployeeCombos(constraintFactory: ConstraintFactory): Constraint =
        constraintFactory.forEachUniquePair(
            ShiftAssignment::class.java,
            Joiners.equal(ShiftAssignment::shift)
        ).map { a, b -> setOf(a.employee, b.employee) }
            .groupBy({ it }, ConstraintCollectors.count())
            .filter { _, count -> count > 1 }
            .penalize(HardSoftScore.ONE_SOFT, { _, count -> count })
            .asConstraint("Penalize having same combo of employees for a shift more than once")

Som for alle DSL’er, tar det litt tid å finne ut hvordan de virker. Her må man bare lese seg litt opp og finne ut hva som er den mest effektive måten. Typesignaturene byr på litt hjernetrim, men sluttresultatet blir jo ganske ryddig å lese tross alt.

Definere en solver og finne løsningskandidat

// 1. CONFIGURE SOLVER
val solverFactory: SolverFactory<Roster> = SolverFactory.create<Roster?>(
    SolverConfig()
        .withConstraintProviderClass(RosterConstraintProvider::class.java)
        .withSolutionClass(Roster::class.java)
        .withEntityClasses(ShiftAssignment::class.java)
        .withTerminationSpentLimit(Duration.ofSeconds(1))
)
val solver = solverFactory.buildSolver()

// 2. "LOAD" problem
val shifts = loadShifts() // from somewhere

val problem = Roster(
    shiftAssignments = shifts.flatMap {
        listOf(
            ShiftAssignment(id = "$it.id}[0]" , shift = it, shiftIdx = 1),
            ShiftAssignment(id = "$it.id}[1]", shift = it, shiftIdx = 2),
        )
    },
    employees = loadEmployees(), // from somewhere
)

// 3. SOLVE IT
val solution = solver.solve(problem)

// 4. ... use it/show it?

Først setter vi opp en Timefold solver med konfigurasjon for å fortelle den om modellen og beskrankningene våre. Vi benytter default konfigurasjon for alt annet unntatt hvor lenge vi lar den få lov til å holde på. For dette lille problemet holder det lenge med 1 sekund på min maskin.

ℹ️ Det er mulig å konfigurere hvilke algoritmer som skal brukes både i konstruksjonsfase (First fit, best fit osv) og søkefasen (Simulated Annealing, Tabu Search osv).

Det neste vi gjør er å definere problemet, dvs populere et Roster objekt med;

  • En liste med tilgjengelig kodemakere
  • Og en liste med vakttildelinger (2 per vakt) uten employee feltet satt

Til slutt kjører ber vi Timefold solveren om å finne en løsning.

Eksempel resultat i console ender opp med å bli noe slikt;

WEDNESDAY 09:00: Sindre Grønningen         - Marina Santos Haugen
WEDNESDAY 10:00: Anders Furseth            - Stein Tore Tøsse
WEDNESDAY 11:00: Frode Nerbråten           - Magnus Rundberget
WEDNESDAY 12:00: Finn Johnsen              - Nils Larsgård
WEDNESDAY 13:00: Kristian Frølich          - Eivind Waaler
WEDNESDAY 14:00: André Bonkowski           - Fredrik Aubert
WEDNESDAY 15:00: Alf Kristian Støyle       - Stig Melling
WEDNESDAY 16:00: Åshild Thorrud            - Kristoffer Moe
WEDNESDAY 17:00: Olga Voronkova            - Ronny Løvtangen
THURSDAY  09:00: Stig Melling              - Kristoffer Moe
THURSDAY  10:00: Stein Tore Tøsse          - Fredrik Aubert
THURSDAY  11:00: André Bonkowski           - Ronny Løvtangen
THURSDAY  12:00: Olga Voronkova            - Nils Larsgård
THURSDAY  13:00: Åshild Thorrud            - Frode Nerbråten
THURSDAY  14:00: Sindre Grønningen         - Kristian Frølich
THURSDAY  15:00: Marina Santos Haugen      - Finn Johnsen
THURSDAY  16:00: Magnus Rundberget         - Alf Kristian Støyle
THURSDAY  17:00: Eivind Waaler             - Anders Furseth

Skrur vi på logging ser vi noe alla;

11:11:38.569 INFO  - Solving started: time spent (23), best score (-36init/0hard/0soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).
11:11:38.572 INFO  - Problem scale: entity count (36), variable count (36), approximate value count (18), approximate problem scale (1.54814 × 10^45).
11:11:38.613 INFO  - Construction Heuristic phase (0) ended: time spent (67), best score (0hard/-1soft), move evaluation speed (16200/sec), step total (36).
11:11:39.546 INFO  - Local Search phase (1) ended: time spent (1000), best score (0hard/0soft), move evaluation speed (230007/sec), step total (53963).
11:11:39.547 INFO  - Solving ended: time spent (1000), best score (0hard/0soft), move evaluation speed (215015/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).

I løpet av bare noen timer har vi prototypet en løsning som funker brillefint og er rimelig enkel å vedlikeholde eller utvide 🎉

Oppsummering

Constraint Solvers er et nyttig verktøy å ha i verktøykassen når man møter på kombinatorisk komplekse problemer. Problemene det egner seg spesielt godt for har kanskje ikke én perfekt løsning og løsningsrommet er så stort at det ikke er praktisk mulig å bruke brute-force for å søke seg frem til en løsning. Ved å fokusere på å definere beskrankninger og en hensiktsmessig måte å score løsningsalternativer på kan du få gode (nok) resultater innenfor rimelige/brukbare tidsrammer. Du lar språket/biblioteket/rammeverket gjøre den tunge jobben med å effektivt evaluere alternativer. Koden du selv skriver blir deklarativ og ofte betydelig mindre enn dersom du skulle ramle ned i en imperativ implementasjon.

Koden for eksemplet finner du på https://github.com/rundis/vaktliste.