代码之家  ›  专栏  ›  技术社区  ›  EDZ

我可以在Google的ortools包中提供一个带有BFS的解算器吗?

  •  1
  • EDZ  · 技术社区  · 6 年前

    我正在解一个非常大的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++文档。

    当然,也欢迎其他资源。

    1 回复  |  直到 6 年前
        1
  •  3
  •   sascha    6 年前

    抓取文档, this seems to be the API-docs 对于基于C++的解算器和基于swig的python绑定,会提到。

    在此范围内,您将发现 MPSolver 有了这个:

    设置开始LPBASIS

    返回类型:void

    参数:const std::vector&variable\u status,const std::vector&constraint\u状态

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

    这个警告有点让我想知道这是否会对你起作用(在节省时间方面)。

    如果你没有很好的理由坚持使用GLOP(看起来很有趣!),使用 CoinORs Clp (令人沮丧的文档状态;但我是最好的开源LP解算器,包括一些有趣的崩溃过程)!我认为它甚至在ortools中也有接口。( Mittelmann Benchmarks 甚至击败了CPLEX。但就科学评估而言,这只表明它很有竞争力!)

    或者,如果它非常大,并且您不需要类似单纯形的解决方案,那么可以使用内点法(Clp有一个;没有关于质量的信息)。