ojAlgo – 连续块逻辑的优化问题？
我正在使用ojAlgo来解决作为练习的课堂安排问题。 源代码可以在kotlin_solution文件夹的GitHub上find：
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.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) { 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) { 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) 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个variables，连续的逻辑似乎永远流失。
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) { 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 List.rollingBatches(batchSize: Int) = (0..size).asSequence().map { i -> subList(i, (i + batchSize).let { if (it > size) size else it }) }.filter { it.size == batchSize }
我想到了。 稍后我会用完整的数学建模解释来更新这个答案。 本质上，对于每个15分钟的块，我查询包含该块的槽组，并声明所有块的总和不能超过一个。 最终在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>( 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) { 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) { 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 List .rollingBatches(batchSize: Int) = (0..size).asSequence().map { i -> subList(i, (i + batchSize).let { if (it > size) size else it }) }.filter { it.size == batchSize } fun List .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 }