kotlin - ojAlgo-连续 block 逻辑的优化问题？

Question

我正在使用ojAlgo解决我正在做的练习中的类安排问题。可以在GitHub上的kotlin_solution文件夹中找到源代码:

https://github.com/thomasnield/optimized-scheduling-demo

一切顺利，直到我开始实现连续的块逻辑which I've described over on Math Exchange为止。基本上，如果一个类 session 需要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() }
}

**更新**

我创建了一个独立的示例，简化了上面我想做的事情。似乎连续的逻辑确实是问题所在，并且问题越多，“插槽”的执行速度就越慢。在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 }

Answer 1

我想到了。稍后，我将使用完整的数学建模说明来更新此答案。基本上，对于每个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<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 }