How to separate multi-day task into days chunks in constraint stream?

[holgerbrandl]

Hi,

we want to build a training course scheduler (e.g. to schedule developer trainings) with timefold. Each course will last several days and requires several notebooks (that is the number of registered participants) from a pool. For the scoring function, we would like to compute (and penalize) the following metrics

1. count the number of teachers being active every day in the calendar
2. count the number of notebooks in use for each day (and use a hard constraint later to penalize if more notebooks are needed than available).

How can we use the constraints API from https://timefold.ai/docs/timefold-solver/latest/constraints-and-score/score-calculation#constraintStreamsGroupingAndCollectors to increase the cardinality accordingly to compute these metrics? So something along

courses.groupBy(TrainingCourse::getDay, sum(TrainingCourse::getNumRequiredNotebooks))

Unfortunately, this approach won't work, as we can not separate the planning entity (course) into different chunks for each day. So groupBy does not seem to allow increasing the cardinality of the stream.

Do you know how/ if to use the timefold constraints API to model such a use-case?

Kind regards,
Holger

[triceo]

Hello @holgerbrandl. Can you perhaps sketch how you think the API should work to be able to do what you want? It would help me to understand your problem.

Constraint Streams' groupBy does support cardinality changes in all directions. Your snippet has 2 arguments, so the resulting cardinality will be 2 (bi). From that, I'm assuming that your cardinality and my cardinality are actually different things and I need to understand that difference.

[holgerbrandl]

Thanks @triceo . Indeed my question was not well phrased. I've tried to draw it to simplify our discussion:

The model sources (incomplete here) are

import ai.timefold.solver.core.api.domain.entity.PlanningEntity
import ai.timefold.solver.core.api.domain.lookup.PlanningId
import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty
import ai.timefold.solver.core.api.domain.solution.PlanningScore
import ai.timefold.solver.core.api.domain.solution.PlanningSolution
import ai.timefold.solver.core.api.domain.solution.ProblemFactCollectionProperty
import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider
import ai.timefold.solver.core.api.domain.variable.*
import ai.timefold.solver.core.api.score.buildin.hardmediumsoft.HardMediumSoftScore
import ai.timefold.solver.core.api.score.stream.Constraint
import ai.timefold.solver.core.api.score.stream.ConstraintCollectors.sum
import ai.timefold.solver.core.api.score.stream.ConstraintFactory
import ai.timefold.solver.core.api.score.stream.ConstraintProvider
import kotlinx.datetime.Instant
import kotlinx.datetime.LocalDate



open class ScheduleItem{

    @get:PlanningId
    var id: Long? = null

    @InverseRelationShadowVariable(sourceVariableName = "previousTaskOrRoom")
    var nextTask: Course? = null
}

class Room  : ScheduleItem()

data class LaptopRequirements(val date: LocalDate, val numLaptops: Int)

@PlanningEntity
class Course {

    var numParticipants : Int? = 0

    @AnchorShadowVariable(sourceVariableName = "previousTaskOrRoom")
    var room: Room? = null

    @PlanningVariable(
        valueRangeProviderRefs = ["rooms", "courses"],
        graphType = PlanningVariableGraphType.CHAINED
    )
    var previousTaskOrRoom: ScheduleItem? = null

    @ShadowVariable(
        variableListenerClass = CourseVariablesListener::class,
        sourceVariableName = "room"
    )
    @ShadowVariable(
        variableListenerClass = CourseVariablesListener::class,
        sourceVariableName = "previousTaskOrRoom"
    )
    var start: Instant? = null

    @PiggybackShadowVariable(shadowVariableName = "start")
    var end: Instant? = null

    fun getLaptopRequirementTimeline(): List<LaptopRequirements> {
//        return  end - start --> chunk per day --> listOf(date, LaptopRequirements(numParticipants))
        return listOf()
    }
}

@PlanningSolution
class CourseSchedule {
    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "rooms")
    lateinit var rooms: List<Room>

    @PlanningEntityCollectionProperty
    @ValueRangeProvider(id = "courses")
    lateinit var courses: List<Course>

    @PlanningScore
    var score: HardMediumSoftScore? = null

    constructor() // needed by solver engine
}


abstract class CourseVariablesListener : VariableListener<CourseSchedule, Course>{
    // not relevant here
}

open class CourseConstraints : ConstraintProvider {

    override fun defineConstraints(constraintFactory: ConstraintFactory): Array<Constraint> = buildList {
        add(laptopAvailability(constraintFactory))
    }.toTypedArray()

    fun laptopAvailability(constraintFactory: ConstraintFactory) = constraintFactory
        .forEach(Course::class.java)
        .filter { it.start != null }
        // TODO this does not compile and is what my question is about:
        .groupBy(Course::getLaptopRequirementTimeline, sum(LaptopRequirements::numLaptops))
        .filter(HardMediumSoftScore.ONE_SOFT) { day, laptopTotal ->
            laptopTotal > 7
        }        
        .penalize(HardMediumSoftScore.ONE_SOFT)
        .asConstraint("laptop-availability")
}

So my problem (marked with TODO) is that group-key-mapper function reference arguement does not seem to support list values (as provided by getLaptopRequirementTimeline ).

[triceo]

The drawing illustrates the problem well. In the past, I solved a similar issue by essentially doing a time grain pattern. For every day in the problem, check all courses happening on that day, sum up their requirements, subtract availabilities.

This requires you to somehow have Day as fact in the problem, and have one instance of it for every day of your planning window. Alternatively, at the expense of much more complex (and relatively slow) constraints, you can probably have the list of days deduced from first day of first course and last day of last course, and that list can then be flattened.

Hopefully the planning window is just a few weeks, as this design pattern really doesn't scale. I wouldn't go into hundreds of days, but YMMV.

[holgerbrandl]

Thanks @triceo for your kind guidance. I have followed your suggestions and also documented the solution path in a public example deposited under https://github.com/holgerbrandl/kalasim/blob/master/modules/optimization/src/main/kotlin/org/kalasim/examples/coursescheduler/CourseScheduling.kt#L245

From my perspective, we can close this discussion.