关于算法:运筹优化工具ortools解读与实践MIP求解器与CPSAT求解器对比

1. 前言

前文咱们提到，CP-SAT 不仅能够解决束缚布局问题，还能够解决整数布局、混合整数布局等指标优化问题，并在前文中用车间调度案例做了阐明。

本文次要比照两种不同的求解器的差别，咱们从一个案例说起。

2. 调配问题的两种解法

问题

假如一家出租车公司有四个客户在等车，四个出租车司机 (工人) 能够接他们，工作是给每个客户调配一名司机去接他们。工作的老本是司机接一个特定客户所破费的工夫。问题是，如何将司机调配给客户，以最小化总等待时间。

如下图所示，右边的节点示意 worker(司机)。左边的节点示意工作(客户)，这些边示意将工作人员调配给工作的所有可能办法。

用表格模式示意如下：

MIP 问题求解

底层采纳 SCIP 求解器

from ortools.linear_solver import pywraplp

def main():
    # 数据，存储不同 work-task 匹配时的 cost
    costs = [[90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # SCIP 求解器.
    solver = pywraplp.Solver.CreateSolver('SCIP')


    # 决策变量
    # x[i, j] 存储 0 - 1 值, 如果将 worker i 和 task j 进行匹配，则设置为 1.
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, '')

    # 束缚 1：一个 worker 最多安顿一个 task.
    for i in range(num_workers):
        #solver 本身提供 sum 等针对 var 的数值操作
        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

    # 束缚 2：一个 task 只安顿给 1 个 worker.
    for j in range(num_tasks):
        solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

    # 指标函数
    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * x[i, j])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    status = solver.Solve()

    # Print solution.
    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f'Total cost = {solver.Objective().Value()}\n')
        for i in range(num_workers):
            for j in range(num_tasks):
                # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
                if x[i, j].solution_value() > 0.5:
                    print(f'Worker {i} assigned to task {j}.' +
                          f'Cost: {costs[i][j]}')
    else:
        print('No solution found.')


if __name__ == '__main__':
    main()

CP-SAT 求解

from ortools.sat.python import cp_model


def main():
    # 数据，存储不同 work-task 匹配时的 cost
    costs = [[90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # CP-SAT
    model = cp_model.CpModel()

    # 变量
    x = []
    for i in range(num_workers):
        t = []
        for j in range(num_tasks):
            t.append(model.NewBoolVar(f'x[{i},{j}]'))
        x.append(t)

    # Constraints
    # Each worker is assigned to at most one task.
    for i in range(num_workers):
        model.AddAtMostOne(x[i][j] for j in range(num_tasks))

    # Each task is assigned to exactly one worker.
    for j in range(num_tasks):
        model.AddExactlyOne(x[i][j] for i in range(num_workers))

    # Objective
    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * x[i][j])
    model.Minimize(sum(objective_terms))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'Total cost = {solver.ObjectiveValue()}')
        print()
        for i in range(num_workers):
            for j in range(num_tasks):
                if solver.BooleanValue(x[i][j]):
                    print(f'Worker {i} assigned to task {j} Cost = {costs[i][j]}')
    else:
        print('No solution found.')


if __name__ == '__main__':
    main()

3. 比照

适用性

实践上，

• MIP 办法更适宜线性规划问题的变种，例如仅仅是减少了整数束缚；
• CP-SAT 更适宜少数变量为布尔型时的状况

代码构造

从代码中能够看到，
CP-SAT 提供两个类

• CpModel 类，大量 CP-SAT 的和信操作，例如变量、束缚都在该类中

Methods for building a CP model.
Methods beginning with:

• New create integer, boolean, or interval variables.

• Add create new constraints and add them to the model.
• CpSolver 类，求解器主类，搜寻 solution、生成求解过程的统计数据等

The purpose of this class is to search for a solution to the model provided
to the Solve() method.
Once Solve() is called, this class allows inspecting the solution found
with the Value() and BooleanValue() methods, as well as general statistics
about the solve procedure.

linear_solver 只提供一个 Solver 类，所有外围因素都在该类内。