如何在OR-Tools中定义目标函数以最小化指派问题的成本极值差？

现有3名工人、4项任务，成本矩阵如下：

costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
    ]

要求为每名工人分配一项任务，无需最小化总成本，而是最小化成本的极值差（即让工人的任务成本尽可能接近）。例如工人0→任务0、工人1→任务1、工人2→任务2时，极值差为5，是最优结果。

尝试的代码与错误 #

使用OR-Tools的MIP求解器实现时，运行以下代码报错：

from ortools.linear_solver import pywraplp

def main():
    # Data
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # Solver
    solver = pywraplp.Solver.CreateSolver("SCIP")

    if not solver:
        return

    # Variables
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, "")

    # Constraints
    for i in range(num_workers):
        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) == 1)

    for j in range(num_tasks):
        solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) <= 1)

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

    objective_cost = max(objective_terms)-min(objective_terms)
    solver.Minimize(objective_cost)

    # Solve
    print(f"Solving with {solver.SolverVersion()}")
    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):
                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()

报错信息：

Operators "<" and ">" not supported with the linear solver

错误核心：objective_terms中的元素是OR-Tools的变量对象，无法直接用Python内置的max()/min()函数处理，线性求解器不支持这种非线性表达式。

解决方案：OR-Tools两种实现方式 #

这类问题完全可以用OR-Tools解决，以下是两种可行方案：

方案一：MIP求解器线性化目标函数 #

通过引入辅助变量max_cost和min_cost，将极值差的非线性目标转化为线性约束：

from ortools.linear_solver import pywraplp

def main():
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    solver = pywraplp.Solver.CreateSolver("SCIP")
    if not solver:
        return

    # 0-1分配变量
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, f"x_{i}_{j}")

    # 每个工人分配恰好一项任务
    for i in range(num_workers):
        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) == 1)

    # 每项任务最多分配给一个工人
    for j in range(num_tasks):
        solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) <= 1)

    # 定义每个工人的实际成本表达式
    worker_cost = []
    for i in range(num_workers):
        cost_expr = solver.Sum([costs[i][j] * x[i, j] for j in range(num_tasks)])
        worker_cost.append(cost_expr)

    # 引入最大、最小成本变量
    max_cost = solver.NumVar(0, solver.infinity(), "max_cost")
    min_cost = solver.NumVar(0, solver.infinity(), "min_cost")

    # 约束：max_cost >= 所有工人的成本
    for cost in worker_cost:
        solver.Add(max_cost >= cost)

    # 约束：min_cost <= 所有工人的成本
    for cost in worker_cost:
        solver.Add(min_cost <= cost)

    # 目标：最小化极值差
    solver.Minimize(max_cost - min_cost)

    # 求解
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f"最小极值差 = {solver.Objective().Value()}\n")
        for i in range(num_workers):
            for j in range(num_tasks):
                if x[i, j].solution_value() > 0.5:
                    print(f"工人 {i} 分配任务 {j}，成本：{costs[i][j]}")
    else:
        print("未找到可行解。")

if __name__ == "__main__":
    main()

方案二：使用CP-SAT求解器 #

CP-SAT原生支持极值运算，实现更直观：

from ortools.sat.python import cp_model

def main():
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    model = cp_model.CpModel()

    # 0-1分配变量
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = model.NewBoolVar(f"x_{i}_{j}")

    # 每个工人分配恰好一项任务
    for i in range(num_workers):
        model.AddExactlyOne(x[i, j] for j in range(num_tasks))

    # 每项任务最多分配给一个工人
    for j in range(num_tasks):
        model.AddAtMostOne(x[i, j] for i in range(num_workers))

    # 定义每个工人的成本
    worker_cost = []
    for i in range(num_workers):
        cost_vars = []
        for j in range(num_tasks):
            cost_vars.append(cp_model.LinearExpr.Term(x[i, j], costs[i][j]))
        total_cost = cp_model.LinearExpr.Sum(cost_vars)
        worker_cost.append(total_cost)

    # 计算最大和最小成本
    max_cost = model.NewIntVar(0, max(max(row) for row in costs), "max_cost")
    min_cost = model.NewIntVar(0, max(max(row) for row in costs), "min_cost")

    model.AddMaxEquality(max_cost, worker_cost)
    model.AddMinEquality(min_cost, worker_cost)

    # 目标：最小化极值差
    model.Minimize(max_cost - min_cost)

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

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"最小极值差 = {solver.ObjectiveValue()}\n")
        for i in range(num_workers):
            for j in range(num_tasks):
                if solver.Value(x[i, j]):
                    print(f"工人 {i} 分配任务 {j}，成本：{costs[i][j]}")
    else:
        print("未找到可行解。")

if __name__ == "__main__":
    main()

内容的提问来源于stack exchange，提问作者user24923465