1

我有简单的二进制线性编程函数，我想得到不止一个，例如来自 Optimisation.Result = model.minimise() 的 10 个最佳解决方案。这对 OjAlgo 可行吗？

我知道函数的目的是找到一个最佳解决方案，但是有没有机会生成更多解决方案或从求解器迭代中获得解决方案？

fun linearProgrammingSolver(meal: Meal): MutableList<String> {

        val mealList = meal.results
        val resultList = mutableListOf<String>()
        val listOfVariables= makeVariables(meal) as ImmutableList<Variable>

        val model = ExpressionsBasedModel()
        listOfVariables.forEach{
            model.addVariable(it)
        }


        val calories = model.addExpression("calories")
            .lower(1500)
            .upper(3000)
        listOfVariables.forEach {
           val index = listOfVariables.indexOf(it)
            calories.set(listOfVariables[index], mealList[index].nutrition.nutrients[0].amount)
        }

        val protein = model.addExpression("protein")
            .lower(60)
        listOfVariables.forEach {
            val index = listOfVariables.indexOf(it)
            protein.set(listOfVariables[index], mealList[index].nutrition.nutrients[1].amount)
        }


        val meals = model.addExpression("meals")
            .level(3)
        listOfVariables.forEach {
            val index = listOfVariables.indexOf(it)
            meals.set(listOfVariables[index], 1)
        }


        val result: Optimisation.Result = model.minimise()

        println("state ${result.state}")


        model.variables.forEach{
            if(it.value.toInt() == 1){
                println("model.var ${it}")
                resultList.add(it.name)
            }
        }

        println(model)
        println(result)
        println("list $resultList")

        return resultList
    }

4

2 回答 2

2

有两种方法可以解释这个问题。

  1. 获得最佳解决方案和 9 个次佳解决方案。这可以通过查看最佳解决方案x*(i)并设置和引入禁止再次找到a(i):=x*(i)的模型的额外约束来实现，然后解决。x*重复这个。您需要在每个循环中添加的剪切可能如下所示：

    sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1

  2. 收集算法找到的解决方案并报告其中最好的 10 个。这应该不会太难添加到算法中（只需跟踪最好的 10 个）。这将需要更改算法的源代码。

另一种方法是使用更高级（但可能更昂贵）的求解器，它具有所谓的解决方案池。

于 2020-11-18T17:21:39.593 回答
1

ojAlgo 返回 1 个解决方案与描述该解决方案“质量”的状态配对 - 最优/可行/近似/不可行/无界...

您可以按照 Erwin Kalvelagen 在他的回答中的建议进行操作。ojAlgo 的 IntegerSolver 确实注册/记录找到的每个整数解决方案，但目前仅存储并返回找到的最佳解决方案。

于 2020-11-18T19:29:27.027 回答