我正在使用 ojAlgo 来解决我正在做的一个课堂安排问题作为练习。可以在 GitHub 上的kotlin_solution文件夹中找到源代码：
https://github.com/thomasnield/optimized-scheduling-demo
一切都很顺利，直到我开始实现我在 Math Exchange 上描述过的连续块逻辑。基本上，如果一节课需要 4 个块，那么这 4 个块需要放在一起。
由于某种原因，当我在这部分代码中实现连续逻辑时，此建模逻辑突然停止。它在无限地搅动。
这是完整的 Kotlin 代码：
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() }
}
** 更新 **
我创建了一个独立的示例，简化了我在上面尝试做的事情。似乎连续逻辑确实是问题所在，问题的“槽”越多，执行速度就越慢。在 48000 个变量中，连续的逻辑似乎永远在搅动。
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 }