如何加速ortools.linear_solver求解大规模人员任务分配问题

一、算法参数设置（如PRESOLVE_ON）加速求解 #

1. Python API设置方法 #

SCIP求解器的参数可通过solver.SetSolverSpecificParametersAsString()方法直接配置，比如开启预求解、调整启发式算法强度等：

# 创建SCIP求解器后添加参数配置
solver = pywraplp.Solver.CreateSolver("SCIP")
# 配置预求解及加速参数
solver.SetSolverSpecificParametersAsString("""
presolving/maxrounds=100
presolving/maxrestarts=5
heuristics/randrounding/freq=10
limits/time=300  # 可选：设置超时时间，单位秒
""")

常用有效参数说明：

• presolving/maxrounds：预求解最大轮次，增大值可增强预处理效果
• presolving/maxrestarts：预求解重启次数，帮助突破局部最优简化
• heuristics/*：调整启发式算法的频率和强度，快速生成可行解
• limits/time：设置全局超时，避免无限等待

2. 参数效果说明 #

预求解（PRESOLVE）会自动简化模型：移除冗余约束、固定变量取值、合并相似约束，能显著压缩问题规模。你的模型包含大量任务ID相关约束，预求解可提前收紧变量边界，大幅降低求解复杂度。

二、提供初始分配解加速最优解搜索 #

OR-Tools支持通过SetHint()方法为变量提供初始解，帮助求解器快速收敛到最优解。

1. 生成初始可行解 #

先通过贪心算法生成满足所有约束的初始分配：

def generate_initial_assignment(num_workers, num_tasks, workers_id, idsrt_2_id_dict):
    x_init = np.zeros((num_workers, num_tasks), dtype=int)
    task_assigned = [False]*num_tasks
    worker_assigned = [False]*num_workers

    # 处理任务1必须分配给A类工人的约束
    for i in range(num_workers):
        if workers_id[i] == idsrt_2_id_dict["A"] and not worker_assigned[i] and not task_assigned[1]:
            x_init[i][1] = 1
            worker_assigned[i] = True
            task_assigned[1] = True
            break

    # 处理任务2、4、6分配给同一ID工人的约束
    target_id = None
    for i in range(num_workers):
        if not worker_assigned[i]:
            target_id = workers_id[i]
            for j in [2,4,6]:
                if not task_assigned[j]:
                    for k in range(num_workers):
                        if workers_id[k] == target_id and not worker_assigned[k]:
                            x_init[k][j] = 1
                            worker_assigned[k] = True
                            task_assigned[j] = True
                            break
            break

    # 处理任务10、11、12分配给同一ID工人的约束
    target_id = None
    for i in range(num_workers):
        if not worker_assigned[i]:
            target_id = workers_id[i]
            for j in [10,11,12]:
                if not task_assigned[j]:
                    for k in range(num_workers):
                        if workers_id[k] == target_id and not worker_assigned[k]:
                            x_init[k][j] = 1
                            worker_assigned[k] = True
                            task_assigned[j] = True
                            break
            break

    # 剩余任务贪心分配（可根据ID总和约束调整逻辑）
    for i in range(num_workers):
        if not worker_assigned[i]:
            for j in range(num_tasks):
                if not task_assigned[j]:
                    x_init[i][j] = 1
                    worker_assigned[i] = True
                    task_assigned[j] = True
                    break
    return x_init

2. 为求解器设置初始解提示 #

生成初始解后，通过SetHint()传入求解器：

# 生成初始解
x_init = generate_initial_assignment(num_workers, num_tasks, workers_id, idsrt_2_id_dict)
# 为每个x[i,j]变量设置初始提示
for i in range(num_workers):
    for j in range(num_tasks):
        x[i,j].SetHint(int(x_init[i][j]))

初始解越接近最优解，求解器收敛速度越快。若贪心解质量不足，可尝试用遗传算法、局部搜索等启发式方法生成更优初始解。

三、额外优化建议 #

• 变量类型优化：将成本值离散化（如乘以100转为整数），使用整数变量求解，部分求解器对整数问题的优化更成熟。
• 约束简化：直接对任务j设置sum(workers_id[i]*x[i,j] == target_id)约束，避免创建冗余的Sum表达式，降低模型复杂度。
• 求解器切换：若SCIP速度不足，可尝试CBC或商业求解器Gurobi，只需修改CreateSolver参数，如solver = pywraplp.Solver.CreateSolver("CBC")。

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