1

我正在解决一个非常大的 LP——一个没有 0 作为基本可行解决方案 (BFS) 的 LP。我想知道是否通过向求解器传递一个基本可行的解决方案，我可以加快这个过程。寻找类似的东西：solver.setBasicFeasibleSolution()。我将在下面制定一个玩具实例（约束更少）并向您展示我的意思。

from ortools.linear_solver import pywraplp


def main():  
    # Instantiate solver
    solver = pywraplp.Solver('Toy',
                       pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    # Variables
    x = solver.NumVar(-1, solver.infinity(), 'x')
    y = solver.NumVar(-1, solver.infinity(), 'y')
    z = solver.NumVar(-1, solver.infinity(), 'z')

    # Constraint 1: x + y >= 10.
    constraint1 = solver.Constraint(10, solver.infinity())
    constraint1.SetCoefficient(x, 1)
    constraint1.SetCoefficient(y, 1)

    # Constraint 2: x + z >= 5.
    constraint2 = solver.Constraint(5, solver.infinity())
    constraint2.SetCoefficient(x, 1)
    constraint2.SetCoefficient(z, 1)

    # Constraint 3: y + z >= 15.
    constraint2 = solver.Constraint(15, solver.infinity())
    constraint2.SetCoefficient(y, 1)
    constraint2.SetCoefficient(z, 1)

    # Objective function: min 2x + 3y + 4z.
    objective = solver.Objective()
    objective.SetCoefficient(x, 2)
    objective.SetCoefficient(y, 3)
    objective.SetCoefficient(z, 4)
    objective.SetMinimization()

    # What I want:
    """
    solver.setBasicFeasibleSolution({x: 10, y: 5, z: 15})
    """

    solver.Solve()

    [print val.solution_value() for val in [x, y, z]]

希望这样的事情会加快速度（以防求解器必须使用两相单纯形法来找到初始 BFS 或大 M 方法）。

此外，如果有人可以向我指出 python API 文档——不是谷歌提供的示例——那将非常有帮助。希望了解 ortools 的求解器中有哪些对象可用，它们的方法是什么，以及它们的返回值和模式是什么。有点像 C++ 文档。

当然，也欢迎其他资源。

4

1 回答 1

3

抓取文档，这似乎是基于 C++ 的求解器和基于 swig 的 python 绑定的 API 文档。

在其中，你会发现MPSolver有这个：

SetStartingLpBasis

返回类型：无效

参数：const std::vector& variable_statuses, const std::vector& constraint_statuses

高级用法：增量。此函数为在下一次 LP Solve() 调用中使用的起始基础。当前解决方案的状态可以通过 MPVariable 或 MPConstraint 的 basic_status() 函数检索。警告：使用 Glop，您应该在使用此功能时禁用 presolve，因为此信息不会与 presolve 同步修改，并且可能对预先解决的问题没有太大意义。

这个警告有点让我想知道这是否对你有用（在节省时间方面）。

如果您没有充分的理由坚持使用 GLOP（看起来很有趣！），请使用CoinORs Clp（令人沮丧的文档状态；但恕我直言，最好的开源 LP 求解器，包括一些有趣的崩溃程序）！我认为它甚至可以在 ortools 中进行交互。（Mittelmann Benchmarks，它甚至击败了 CPLEX。但就科学评估而言，它只表明它非常具有竞争力！）

或者，如果它非常大并且您不需要类似 Simplex 的解决方案，请使用内点方法（Clp 有一个；没有关于质量的信息）。

于 2018-02-20T00:56:34.537 回答