I am using ojAlgo to work through a classroom scheduling problem I'm doing as an exercise. The source code can be found here on GitHub in the kotlin_solution folder:
https://github.com/thomasnield/optimized-scheduling-demo
Everything was going fine until I started to implement contiguous block logic which I've described over on Math Exchange. Bascially, if a class session requires 4 blocks then those 4 blocks need to be together.
For some reason, this modeling logic screeches to a halt when I implement the contiguous logic in this part of the code. It is churning infinitely.
Here is the Kotlin code in it's entirety:
import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import java.time.DayOfWeek
import java.time.LocalDate
import java.time.LocalDateTime
import java.time.LocalTime
import java.util.concurrent.atomic.AtomicInteger
// declare model
val model = ExpressionsBasedModel()
val funcId = AtomicInteger(0)
val variableId = AtomicInteger(0)
fun variable() = Variable(variableId.incrementAndGet().toString().let { "Variable$it" }).apply(model::addVariable)
fun addExpression() = funcId.incrementAndGet().let { "Func$it"}.let { model.addExpression(it) }
// Any Monday through Friday date range will work
val operatingDates = LocalDate.of(2017,10,16)..LocalDate.of(2017,10,20)
val operatingDay = LocalTime.of(8,0)..LocalTime.of(17,0)
val breaks = listOf<ClosedRange<LocalTime>>(
//LocalTime.of(11,30)..LocalTime.of(13,0)
)
// classes
val scheduledClasses = listOf(
ScheduledClass(id=1, name="Psych 101", hoursLength=1.0, repetitions=2),
ScheduledClass(id=2, name="English 101", hoursLength=1.5, repetitions=3),
ScheduledClass(id=3, name="Math 300", hoursLength=1.5, repetitions=2),
ScheduledClass(id=4, name="Psych 300", hoursLength=3.0, repetitions=1),
ScheduledClass(id=5, name="Calculus I", hoursLength=2.0, repetitions=2),
ScheduledClass(id=6, name="Linear Algebra I", hoursLength=2.0, repetitions=3),
ScheduledClass(id=7, name="Sociology 101", hoursLength=1.0, repetitions=2),
ScheduledClass(id=8, name="Biology 101", hoursLength=1.0, repetitions=2)
)
fun main(args: Array<String>) {
println("Job started at ${LocalTime.now()}")
applyConstraints()
println(model.minimise())
Session.all.forEach {
println("${it.name}-${it.repetitionIndex}: ${it.start.dayOfWeek} ${it.start.toLocalTime()}-${it.end.toLocalTime()}")
}
println("Job ended at ${LocalTime.now()}")
}
data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {
val timeRange = dateTimeRange.let { it.start.toLocalTime()..it.endInclusive.toLocalTime() }
fun addConstraints() {
val f = addExpression().upper(1)
OccupationState.all.filter { it.block == this }.forEach {
f.set(it.occupied, 1)
}
}
companion object {
// Operating blocks
val all by lazy {
generateSequence(operatingDates.start.atTime(operatingDay.start)) {
it.plusMinutes(15).takeIf { it.plusMinutes(15) <= operatingDates.endInclusive.atTime(operatingDay.endInclusive) }
}.filter { it.toLocalTime() in operatingDay }
.map { Block(it..it.plusMinutes(15)) }
.toList()
}
}
}
data class ScheduledClass(val id: Int,
val name: String,
val hoursLength: Double,
val repetitions: Int) {
val sessions by lazy {
Session.all.filter { it.parentClass == this }
}
fun addConstraints() {
//guide 3 repetitions to be fixed on MONDAY, WEDNESDAY, FRIDAY
if (repetitions == 3) {
sessions.forEach { session ->
val f = addExpression().level(session.blocksNeeded)
session.occupationStates.asSequence()
.filter {
it.block.dateTimeRange.start.dayOfWeek ==
when(session.repetitionIndex) {
1 -> DayOfWeek.MONDAY
2 -> DayOfWeek.WEDNESDAY
3 -> DayOfWeek.FRIDAY
else -> throw Exception("Must be 1/2/3")
}
}
.forEach {
f.set(it.occupied,1)
}
}
}
//guide two repetitions to be 48 hours apart (in development)
if (repetitions == 2) {
val first = sessions.find { it.repetitionIndex == 1 }!!
val second = sessions.find { it.repetitionIndex == 2 }!!
}
}
companion object {
val all by lazy { scheduledClasses }
}
}
data class Session(val id: Int,
val name: String,
val hoursLength: Double,
val repetitionIndex: Int,
val parentClass: ScheduledClass) {
val blocksNeeded = (hoursLength * 4).toInt()
val occupationStates by lazy {
OccupationState.all.asSequence().filter { it.session == this }.toList()
}
val start get() = occupationStates.asSequence().filter { it.occupied.value.toInt() == 1 }
.map { it.block.dateTimeRange.start }
.min()!!
val end get() = occupationStates.asSequence().filter { it.occupied.value.toInt() == 1 }
.map { it.block.dateTimeRange.endInclusive }
.max()!!
fun addConstraints() {
val f1 = addExpression().level(0)
//block out exceptions
occupationStates.asSequence()
.filter { os -> breaks.any { os.block.timeRange.start in it } || os.block.timeRange.start !in operatingDay }
.forEach {
// b = 0, where b is occupation state
// this means it should never be occupied
f1.set(it.occupied, 1)
}
//sum of all boolean states for this session must equal the # blocks needed
val f2 = addExpression().level(blocksNeeded)
occupationStates.forEach {
f2.set(it.occupied, 1)
}
//ensure all occupied blocks are consecutive
// PROBLEM, not finding a solution and stalling
/*
b1, b2, b3 .. bn = binary from each group
all binaries must sum to 1, indicating fully consecutive group exists
b1 + b2 + b3 + .. bn = 1
*/
val consecutiveStateConstraint = addExpression().level(1)
(0..occupationStates.size).asSequence().map { i ->
occupationStates.subList(i, (i + blocksNeeded).let { if (it > occupationStates.size) occupationStates.size else it })
}.filter { it.size == blocksNeeded }
.forEach { grp ->
/*
b = 1,0 binary for group
n = blocks needed
x1, x2, x3 .. xn = occupation states in group
x1 + x2 + x3 .. + xn - bn >= 0
*/
val binaryForGroup = variable().binary()
consecutiveStateConstraint.set(binaryForGroup, 1)
addExpression().lower(0).apply {
grp.forEach {
set(it.occupied,1)
}
set(binaryForGroup, -1 * blocksNeeded)
}
}
}
companion object {
val all by lazy {
ScheduledClass.all.asSequence().flatMap { sc ->
(1..sc.repetitions).asSequence()
.map { Session(sc.id, sc.name, sc.hoursLength, it, sc) }
}.toList()
}
}
}
data class OccupationState(val block: Block, val session: Session) {
val occupied = variable().binary()
companion object {
val all by lazy {
Block.all.asSequence().flatMap { b ->
Session.all.asSequence().map { OccupationState(b,it) }
}.toList()
}
}
}
fun applyConstraints() {
Session.all.forEach { it.addConstraints() }
ScheduledClass.all.forEach { it.addConstraints() }
Block.all.forEach { it.addConstraints() }
}
** UPDATE **
I created a self-contained example that simplifies what I'm trying to do above. It seems the contiguous logic is indeed the problem, and the more "slots" the problem has the slower it performs. At 48000 variables, the contiguous logic seems to churn forever.
import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import org.ojalgo.optimisation.integer.IntegerSolver
import java.util.concurrent.ThreadLocalRandom
import java.util.concurrent.atomic.AtomicInteger
// declare ojAlgo Model
val model = ExpressionsBasedModel()
// custom DSL for expression inputs, eliminate naming and adding
val funcId = AtomicInteger(0)
val variableId = AtomicInteger(0)
fun variable() = Variable(variableId.incrementAndGet().toString().let { "Variable$it" }).apply(model::addVariable)
fun addExpression() = funcId.incrementAndGet().let { "Func$it"}.let { model.addExpression(it) }
val letterCount = 9
val numberCount = 480
val minContiguousBlocks = 4
val maxContiguousBlocks = 4
fun main(args: Array<String>) {
Letter.all.forEach { it.addConstraints() }
Number.all.forEach { it.addConstraints() }
model.countVariables().run { println("$this variables") }
model.options.debug(IntegerSolver::class.java)
model.minimise().run(::println)
Letter.all.joinToString(prefix = "\t", separator = "\t").run(::println)
Letter.all.map { it.slotsNeeded }.joinToString(prefix = "\t", separator = "\t").run(::println)
Number.all.forEach { n ->
Letter.all.asSequence().map { l -> l.slots.first { it.number == n }.occupied.value.toInt() }
.joinToString(prefix = "$n ", separator = "\t").run { println(this) }
}
}
class Letter(val value: String, val slotsNeeded: Int = 1) {
val slots by lazy {
Slot.all.filter { it.letter == this }.sortedBy { it.number.value }
}
fun addConstraints() {
// Letter must be assigned once
addExpression().level(1).apply {
slots.forEach { set(it.occupied, 1) }
}
//handle recurrences
if (slotsNeeded > 1) {
slots.rollingBatches(slotsNeeded).forEach { batch ->
val first = batch.first()
addExpression().upper(0).apply {
batch.asSequence().flatMap { it.number.slots.asSequence() }
.forEach {
set(it.occupied, 1)
}
set(first.number.cumulativeState, -1)
}
}
}
//prevent scheduling at end of window
// all slots must sum to 0 in region smaller than slots needed
addExpression().level(0).apply {
slots.takeLast(slotsNeeded - 1)
.forEach {
set(it.occupied, 1)
}
}
}
override fun toString() = value
companion object {
val all = ('A'..'Z').asSequence()
.take(letterCount)
.map { it.toString() }
.map { Letter(it, ThreadLocalRandom.current().nextInt(minContiguousBlocks, maxContiguousBlocks + 1)) }
.toList()
}
}
class Number(val value: Int) {
val slots by lazy {
Slot.all.filter { it.number == this }
}
// b_x
val cumulativeState = variable().lower(0).upper(1)
fun addConstraints() {
// Number can only be assigned once
addExpression().upper(1).apply {
slots.forEach { set(it.occupied, 1) }
}
}
companion object {
val all = (1..numberCount).asSequence()
.map { Number(it) }
.toList()
}
override fun toString() = value.toString().let { if (it.length == 1) "$it " else it }
}
data class Slot(val letter: Letter, val number: Number) {
val occupied = variable().binary()
companion object {
val all = Letter.all.asSequence().flatMap { letter ->
Number.all.asSequence().map { number -> Slot(letter, number) }
}.toList()
}
override fun toString() = "$letter$number: ${occupied?.value?.toInt()}"
}
fun <T> List<T>.rollingBatches(batchSize: Int) = (0..size).asSequence().map { i ->
subList(i, (i + batchSize).let { if (it > size) size else it })
}.filter { it.size == batchSize }
I figured it out. I'll update this answer later with the full mathematical modeling explanation. Essentially for each 15 minute block I queried for slot groups that include that block, and declared the sum of all of them must be no more than one. This ended up being acceptably efficient as it runs in 30-60 seconds.
The code is here on GitHub, as well as below: https://github.com/thomasnield/optimized-scheduling-demo