运筹优化工具ortools解读与实践-MIP求解器与CP-SAT求解器对比

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更适合多数变量为布尔型时的情况