ojAlgo - 连续块逻辑的优化问题？
ojAlgo - Optimization issue with contiguous block logic?
我正在使用 ojAlgo 解决一个 class 房间安排问题，我正在做一个练习。可以在 kotlin_solution 文件夹中的 GitHub 上找到源代码：
https://github.com/thomasnield/optimized-scheduling-demo
一切都很顺利，直到我开始实施连续块逻辑 which I've described over on Math Exchange。基本上，如果 class 会话需要 4 个块，那么这 4 个块需要放在一起。
出于某种原因，当我实现连续逻辑 in this part of the code 时，此建模逻辑突然停止。它在无限地搅动着。
这是完整的 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() }
}
** 更新**
我创建了一个独立的示例来简化我在上面尝试做的事情。看起来连续逻辑确实是问题所在，问题越多"slots"，执行速度就越慢。在 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 }
我明白了。我稍后会用完整的数学建模解释更新这个答案。基本上，对于每个 15 分钟的块，我查询包含该块的时隙组，并声明它们的总和不能超过 1。由于它在 30-60 秒内运行，因此最终效率可以接受。
代码在 GitHub 以及下面：
https://github.com/thomasnield/optimized-scheduling-demo
import org.ojalgo.optimisation.integer.IntegerSolver
import java.time.LocalDate
import java.time.LocalTime
import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import java.time.DayOfWeek
import java.time.LocalDateTime
import java.util.concurrent.atomic.AtomicInteger
// 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()
model.countVariables().run { println("$this variables") }
model.options.apply {
//debug(IntegerSolver::class.java)
iterations_suffice = 0
}
println(model.minimise())
ScheduledClass.all.forEach {
println("${it.name}- ${it.daysOfWeek.joinToString("/")} ${it.start.toLocalTime()}-${it.end.toLocalTime()}")
}
println("Job ended at ${LocalTime.now()}")
}
// 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) }
data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {
val timeRange = dateTimeRange.let { it.start.toLocalTime()..it.endInclusive.toLocalTime() }
val available get() = (breaks.all { timeRange.start !in it } && timeRange.start in operatingDay)
//val cumulativeState = variable().apply { if (available) lower(0).upper(1) else level(0) }
val slots by lazy {
Slot.all.filter { it.block == this }
}
fun addConstraints() {
if (available) {
addExpression().lower(0).upper(1).apply {
ScheduledClass.all.asSequence().flatMap { it.anchorOverlapFor(this@Block) }
.filter { it.block.available }
.forEach {
set(it.occupied, 1)
}
}
} else {
ScheduledClass.all.asSequence().flatMap { it.anchorOverlapFor(this@Block) }
.forEach {
it.occupied.level(0)
}
}
}
companion object {
// Operating blocks
val all by lazy {
generateSequence(operatingDates.start.atStartOfDay()) {
it.plusMinutes(15).takeIf { it.plusMinutes(15) <= operatingDates.endInclusive.atTime(23,59) }
}.map { Block(it..it.plusMinutes(15)) }
.toList()
}
fun applyConstraints() {
all.forEach { it.addConstraints() }
}
}
}
data class ScheduledClass(val id: Int,
val name: String,
val hoursLength: Double,
val repetitions: Int,
val repetitionGapDays: Int = 2) {
val repetitionGapSlots = repetitionGapDays * 24 * 4
val slotsNeeded = (hoursLength * 4).toInt()
val slots by lazy {
Slot.all.asSequence().filter { it.session == this }.toList()
}
val batches by lazy {
slots.rollingRecurrences(slotsNeeded = slotsNeeded, gapSize = repetitionGapSlots, recurrencesNeeded = repetitions)
}
fun anchorOverlapFor(block: Block) = batches.asSequence()
.filter { it.flatMap { it }.any { it.block == block } }
.map { it.first().first() }
val start get() = slots.asSequence().filter { it.occupied.value.toInt() == 1 }.map { it.block.dateTimeRange.start }.min()!!
val end get() = start.plusMinutes((hoursLength * 60.0).toLong())
val daysOfWeek get() = (0..(repetitions-1)).asSequence().map { start.dayOfWeek.plus(it.toLong() * repetitionGapDays) }.sorted()
fun addConstraints() {
//sum of all boolean states for this session must be 1
addExpression().level(1).apply {
slots.forEach {
set(it.occupied, 1)
}
}
//guide Mon/Wed/Fri for three repetitions
if (repetitions == 3) {
addExpression().level(1).apply {
slots.filter { it.block.dateTimeRange.start.dayOfWeek == DayOfWeek.MONDAY }
.forEach {
set(it.occupied, 1)
}
}
}
//guide two repetitions to start on Mon, Tues, or Wed
if (repetitions == 2) {
addExpression().level(1).apply {
slots.filter { it.block.dateTimeRange.start.dayOfWeek in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY }.forEach {
set(it.occupied, 1)
}
}
}
}
companion object {
val all by lazy { scheduledClasses }
}
}
data class Slot(val block: Block, val session: ScheduledClass) {
val occupied = variable().apply { if (block.available) binary() else level(0) }
companion object {
val all by lazy {
Block.all.asSequence().flatMap { b ->
ScheduledClass.all.asSequence().map { Slot(b,it) }
}.toList()
}
}
}
fun applyConstraints() {
Block.applyConstraints()
ScheduledClass.all.forEach { it.addConstraints() }
}
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 }
fun <T> List<T>.rollingRecurrences(slotsNeeded: Int, gapSize: Int, recurrencesNeeded: Int) =
(0..size).asSequence().map { i ->
(1..recurrencesNeeded).asSequence().map { (it - 1) * gapSize }
.filter { it + i < size}
.map { r ->
subList(i + r, (i + r + slotsNeeded).let { if (it > size) size else it })
}.filter { it.size == slotsNeeded }
.toList()
}.filter { it.size == recurrencesNeeded }
我正在使用 ojAlgo 解决一个 class 房间安排问题，我正在做一个练习。可以在 kotlin_solution 文件夹中的 GitHub 上找到源代码：
https://github.com/thomasnield/optimized-scheduling-demo
一切都很顺利，直到我开始实施连续块逻辑 which I've described over on Math Exchange。基本上，如果 class 会话需要 4 个块，那么这 4 个块需要放在一起。
出于某种原因，当我实现连续逻辑 in this part of the code 时，此建模逻辑突然停止。它在无限地搅动着。
这是完整的 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() }
}
** 更新**
我创建了一个独立的示例来简化我在上面尝试做的事情。看起来连续逻辑确实是问题所在，问题越多"slots"，执行速度就越慢。在 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 }
我明白了。我稍后会用完整的数学建模解释更新这个答案。基本上，对于每个 15 分钟的块，我查询包含该块的时隙组，并声明它们的总和不能超过 1。由于它在 30-60 秒内运行，因此最终效率可以接受。
代码在 GitHub 以及下面： https://github.com/thomasnield/optimized-scheduling-demo
import org.ojalgo.optimisation.integer.IntegerSolver
import java.time.LocalDate
import java.time.LocalTime
import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
import java.time.DayOfWeek
import java.time.LocalDateTime
import java.util.concurrent.atomic.AtomicInteger
// 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()
model.countVariables().run { println("$this variables") }
model.options.apply {
//debug(IntegerSolver::class.java)
iterations_suffice = 0
}
println(model.minimise())
ScheduledClass.all.forEach {
println("${it.name}- ${it.daysOfWeek.joinToString("/")} ${it.start.toLocalTime()}-${it.end.toLocalTime()}")
}
println("Job ended at ${LocalTime.now()}")
}
// 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) }
data class Block(val dateTimeRange: ClosedRange<LocalDateTime>) {
val timeRange = dateTimeRange.let { it.start.toLocalTime()..it.endInclusive.toLocalTime() }
val available get() = (breaks.all { timeRange.start !in it } && timeRange.start in operatingDay)
//val cumulativeState = variable().apply { if (available) lower(0).upper(1) else level(0) }
val slots by lazy {
Slot.all.filter { it.block == this }
}
fun addConstraints() {
if (available) {
addExpression().lower(0).upper(1).apply {
ScheduledClass.all.asSequence().flatMap { it.anchorOverlapFor(this@Block) }
.filter { it.block.available }
.forEach {
set(it.occupied, 1)
}
}
} else {
ScheduledClass.all.asSequence().flatMap { it.anchorOverlapFor(this@Block) }
.forEach {
it.occupied.level(0)
}
}
}
companion object {
// Operating blocks
val all by lazy {
generateSequence(operatingDates.start.atStartOfDay()) {
it.plusMinutes(15).takeIf { it.plusMinutes(15) <= operatingDates.endInclusive.atTime(23,59) }
}.map { Block(it..it.plusMinutes(15)) }
.toList()
}
fun applyConstraints() {
all.forEach { it.addConstraints() }
}
}
}
data class ScheduledClass(val id: Int,
val name: String,
val hoursLength: Double,
val repetitions: Int,
val repetitionGapDays: Int = 2) {
val repetitionGapSlots = repetitionGapDays * 24 * 4
val slotsNeeded = (hoursLength * 4).toInt()
val slots by lazy {
Slot.all.asSequence().filter { it.session == this }.toList()
}
val batches by lazy {
slots.rollingRecurrences(slotsNeeded = slotsNeeded, gapSize = repetitionGapSlots, recurrencesNeeded = repetitions)
}
fun anchorOverlapFor(block: Block) = batches.asSequence()
.filter { it.flatMap { it }.any { it.block == block } }
.map { it.first().first() }
val start get() = slots.asSequence().filter { it.occupied.value.toInt() == 1 }.map { it.block.dateTimeRange.start }.min()!!
val end get() = start.plusMinutes((hoursLength * 60.0).toLong())
val daysOfWeek get() = (0..(repetitions-1)).asSequence().map { start.dayOfWeek.plus(it.toLong() * repetitionGapDays) }.sorted()
fun addConstraints() {
//sum of all boolean states for this session must be 1
addExpression().level(1).apply {
slots.forEach {
set(it.occupied, 1)
}
}
//guide Mon/Wed/Fri for three repetitions
if (repetitions == 3) {
addExpression().level(1).apply {
slots.filter { it.block.dateTimeRange.start.dayOfWeek == DayOfWeek.MONDAY }
.forEach {
set(it.occupied, 1)
}
}
}
//guide two repetitions to start on Mon, Tues, or Wed
if (repetitions == 2) {
addExpression().level(1).apply {
slots.filter { it.block.dateTimeRange.start.dayOfWeek in DayOfWeek.MONDAY..DayOfWeek.WEDNESDAY }.forEach {
set(it.occupied, 1)
}
}
}
}
companion object {
val all by lazy { scheduledClasses }
}
}
data class Slot(val block: Block, val session: ScheduledClass) {
val occupied = variable().apply { if (block.available) binary() else level(0) }
companion object {
val all by lazy {
Block.all.asSequence().flatMap { b ->
ScheduledClass.all.asSequence().map { Slot(b,it) }
}.toList()
}
}
}
fun applyConstraints() {
Block.applyConstraints()
ScheduledClass.all.forEach { it.addConstraints() }
}
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 }
fun <T> List<T>.rollingRecurrences(slotsNeeded: Int, gapSize: Int, recurrencesNeeded: Int) =
(0..size).asSequence().map { i ->
(1..recurrencesNeeded).asSequence().map { (it - 1) * gapSize }
.filter { it + i < size}
.map { r ->
subList(i + r, (i + r + slotsNeeded).let { if (it > size) size else it })
}.filter { it.size == slotsNeeded }
.toList()
}.filter { it.size == recurrencesNeeded }