我可以在 Google 的 ortools 包中提供一个带有 BFS 的求解器来启动吗？

Question

我正在求解一个非常大的线性规划 — 一个没有 0 作为基本可行解 (BFS) 的线性规划。我想知道通过求解器传递一个基本的可行解是否可以加快这个过程。寻找类似以下内容的内容：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 文档——而不是 Google 提供的示例——那将非常有帮助。希望了解 ortools 的求解器中有哪些对象可用、它们的方法是什么以及它们的 return 值和模式是什么。有点像 C++ 文档。

当然也欢迎其他资源

Answer 1

正在抓取文档，this seems to be the API-docs 提到了基于 C++ 的求解器和 swig-based python-binding。

在这里面，你会发现 MPSolver 有这个：

SetStartingLpBasis

Return type: void

Arguments: const std::vector& variable_statuses, const std::vector& constraint_statuses

Advanced usage: Incrementality. This function takes a starting basis to be used in the next LP Solve() call. The statuses of a current solution can be retrieved via the basis_status() function of a MPVariable or a MPConstraint. WARNING: With Glop, you should disable presolve when using this because this information will not be modified in sync with the presolve and will likely not mean much on the presolved problem.

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

如果您没有充分的理由坚持使用 GLOP（看起来很有趣！），请使用 CoinORs Clp (depressing state of docs; but imho the best open-source LP-solver including some interesting crashing-procedures)! I think it's even interfaced within ortools. (Mittelmann Benchmarks，它甚至击败了 CPLEX。但是对于一个scientific-eval来说，只能说明它非常有竞争力！）

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

我可以在 Google 的 ortools 包中提供一个带有 BFS 的求解器来启动吗？

Can I provide a solver in Google's ortools package with a BFS to start?

python

mathematical-optimization

linear-programming

or-tools