时间折叠求解器只能找到最差的解决方案

Question

我有一个基本问题，我想使用 timefold 1.13.0 和 kotlin 为成员分配班次。

只有一个软约束，其中每个成员都有一个“optimalShiftCount”，代表他们应该分配的理想轮班数。

我创建了一个约束，该约束通过 optimizationShiftCount 与分配给成员的轮班次数之间的绝对差进行惩罚。

我使用约束验证器对这个约束进行了单元测试，它工作正常。

但是，即使是一个非常简单的问题，例如将 4 个班次分配给 2 个成员 (

approximate problem scale (16)

)，求解器也无法找到比 0hard/-3soft 解决方案更好的解决方案（在这种情况下可能是最差的可行解决方案）。即使我让它运行几分钟。

最优解是0hard/0soft，但是连0hard/-2soft解都找不到，就卡在0hard/-3soft了。

我添加了一个测试，我自己提供 0hard/0soft 解决方案，并且解决方案管理器正确分析了分数。

我使用 FULL_ASSERT（无警告）进行测试，启用日志记录，我看到求解器在移动，但它从未执行有助于提高分数的操作。

欢迎任何帮助。模型和测试：

import ai.timefold.solver.core.api.domain.entity.PlanningEntity
import ai.timefold.solver.core.api.domain.lookup.PlanningId
import ai.timefold.solver.core.api.domain.solution.PlanningEntityCollectionProperty
import ai.timefold.solver.core.api.domain.solution.PlanningScore
import ai.timefold.solver.core.api.domain.solution.PlanningSolution
import ai.timefold.solver.core.api.domain.solution.ProblemFactCollectionProperty
import ai.timefold.solver.core.api.domain.valuerange.ValueRangeProvider
import ai.timefold.solver.core.api.domain.variable.PlanningVariable
import ai.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore
import ai.timefold.solver.core.api.score.stream.*
import ai.timefold.solver.core.api.solver.SolutionManager
import ai.timefold.solver.core.api.solver.SolverConfigOverride
import ai.timefold.solver.core.api.solver.SolverFactory
import ai.timefold.solver.core.config.solver.EnvironmentMode
import ai.timefold.solver.core.config.solver.SolverConfig
import ai.timefold.solver.core.config.solver.termination.TerminationConfig
import ai.timefold.solver.test.api.score.stream.ConstraintVerifier
import org.assertj.core.api.Assertions.assertThat
import org.junit.jupiter.api.Test
import java.util.function.Function
import kotlin.math.absoluteValue


@PlanningSolution
private data class Planning(
    @PlanningEntityCollectionProperty
    val shifts: List<Shift> = emptyList(),
    @ValueRangeProvider
    @ProblemFactCollectionProperty
    val members: List<Member> = emptyList(),
    @PlanningScore
    var score: HardSoftScore? = null
)

@PlanningEntity
private data class Shift(
    @PlanningId
    val id: Int = -1,
    @PlanningVariable
    val member: Member? = null
)

private data class Member(
    @PlanningId
    val id: Int,
    val optimalShiftCount: Int
)

internal class ProblemConstraintProvider : ConstraintProvider {

    override fun defineConstraints(constraintFactory: ConstraintFactory) =
        arrayOf(penalizeNonOptimalShiftCount(constraintFactory))

    fun penalizeNonOptimalShiftCount(constraintFactory: ConstraintFactory): Constraint {
        return constraintFactory
            .forEach(Member::class.java)
            .join(Shift::class.java, Joiners.equal(Function.identity(), Shift::member))
            .groupBy({ member, shifts -> member }, ConstraintCollectors.countBi())
            .map(
                { member, shiftCount -> member },
                { member, shiftCount -> (member.optimalShiftCount - shiftCount).absoluteValue }
            )
            .filter { member, violation -> violation != 0 }
            .penalize(HardSoftScore.ONE_SOFT, { member, violation -> violation })
            .asConstraint("Non optimal shift count")
    }

}


internal class PlanningTest {

    private val optimalShiftCountVerifier =
        ConstraintVerifier.build(ProblemConstraintProvider(), Planning::class.java, Shift::class.java)
            .verifyThat(ProblemConstraintProvider::penalizeNonOptimalShiftCount)

    private val factory = SolverFactory.create<Planning>(
        SolverConfig()
            .withEnvironmentMode(EnvironmentMode.FULL_ASSERT)
            .withSolutionClass(Planning::class.java)
            .withEntityClasses(Shift::class.java)
            .withConstraintProviderClass(ProblemConstraintProvider::class.java)
    )

    // the solver is unable to find something better than 0hard/-3soft, the optimal solution is 0hard/0soft
    @Test
    fun `solver find optimal solution`() {
        val members = listOf(Member(1, 3), Member(2, 1))
        val problem = Planning(
            listOf(Shift(0), Shift(1), Shift(2), Shift(3)),
            members
        )

        factory.buildSolver(
            SolverConfigOverride<Planning?>()
                .withTerminationConfig(TerminationConfig().withBestScoreLimit("0hard/-2soft"))
        ).solve(problem)
    }

    @Test
    fun `solution manager correctly analyze the 0hard 0soft solution`() {
        val solutionManager = SolutionManager.create(factory)

        val members = listOf(Member(1, 3), Member(2, 1))
        val validSolution1 = Planning(
            listOf(Shift(0, members[0]), Shift(1, members[0]), Shift(2, members[0]), Shift(3, members[1])),
            members
        )
        assertThat(solutionManager.analyze(validSolution1).score())
            .isEqualTo(HardSoftScore.of(0, 0))
    }

    @Test
    fun `solution manager correctly analyze the 0hard -2soft solution`() {
        val solutionManager = SolutionManager.create(factory)

        val members = listOf(Member(1, 3), Member(2, 1))
        val validSolution1 = Planning(
            listOf(Shift(0, members[0]), Shift(1, members[0]), Shift(2, members[1]), Shift(3, members[1])),
            members
        )
        assertThat(solutionManager.analyze(validSolution1).score())
            .isEqualTo(HardSoftScore.of(0, -2))
    }

    @Test
    fun `penalize doing less than optimal shift count`() {
        val members = listOf(Member(0, 3))
        val planning = Planning(
            listOf(Shift(0, members[0]), Shift(1), Shift(2)),
            members
        )
        optimalShiftCountVerifier.givenSolution(planning).penalizesBy(2)
    }

    @Test
    fun `penalize doing more than optimal shift count`() {
        val members = listOf(Member(0, 1))
        val planning = Planning(
            listOf(Shift(0, members[0]), Shift(1, members[0]), Shift(2, members[0])),
            members
        )
        optimalShiftCountVerifier.givenSolution(planning).penalizesBy(2)
    }

    @Test
    fun `dont penalize doing optimal shift count`() {
        val members = listOf(Member(0, 2))
        val planning = Planning(
            listOf(Shift(0, members[0]), Shift(1, members[0]), Shift(2)),
            members
        )
        optimalShiftCountVerifier.givenSolution(planning).penalizes(0)
    }

}

Answer 1

我陷入了局部最优。

它可能发生在一个小数据集上，但就我而言，它来自一个更大的数据集。我只是进行了降采样以重现该问题。

我添加了支柱移动（默认情况下禁用）并解决了问题。

我认为约束的惩罚也过于线性。如果同一成员多次违规，则通过施加更多惩罚，可能会使某些举动更有价值，并有助于避免局部最优。