如何在or-tools中定义其他目标函数来解决分配问题？

Question

我要解决的问题和这个文字

一样

例如，我有3个作品和4个任务。成本矩阵如下所示。

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

我需要为每个工人分配一项任务。但我不需要最小化总成本。相反，我想最小化他们的极端范围（意味着我想让他们的工作时间尽可能接近）。

例如，如果work0->task0 work1->task1 work2->task2，那么它们的range是最小的5。这就是我想要得到的。

我尝试过使用MIP求解器和CP-SAT求解器。但总会有错误。 下面的代码展示了 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
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")

    if not solver:
        return

    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, "")

    # Constraints
    # Each worker is assigned to exactly one 1 task.
    for i in range(num_workers):
        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) == 1)

    # Each task is assigned to at most one worker.
    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):
                # 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()

运行此程序，会抛出以下内容：

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

关键代码是这样的：

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

我知道为什么错了。列表objective_terms中元素的数据类型不是int。但我不知道要修改它。阿洛斯，我想不出任何其他方法来处理这个问题。

这是我可以使用或工具解决的问题类型吗？

非常感谢您的善意和热情的帮助。

Answer 1

由于 MIP 求解器使用具有一定容差的浮点计算，因此严格相等的概念定义不明确。

因此操作员< and >被禁止。您需要使用具有正确偏移量的 <= and >=。

此外，不支持 min() 和 max()。这些是在调用求解器之前解释的 Python 结构。结果是不可预测的。

我建议使用 CP-SAT，因为它本身定义了最小和最大相等性。

从这个作业示例开始。

然后添加公平部分：

查看平衡组示例中的 epsilon 最小化方法

或

使用 2 个临时变量（

min_worked

和

max_worked

）和两个约束（

add_min_equality

和

add_max_equality

）然后

minimize max_worked - min_worked