我正在解一个非常大的LP,它没有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的解算器中有哪些对象可用,它们的方法是什么,以及它们的返回值和模式是什么。有点像C++文档。
当然,也欢迎其他资源。