基于Google OR-Tools的二元变量多目标函数求解问题

核心思路：分层优化（字典序优化） #

OR-Tools的CP-SAT求解器不支持同时优化两个目标，因此采用分阶段的分层策略：先确保最大化分配的用户总数，再在这个前提下最小化使用的服务器数量。

具体实现步骤 #

1. 第一步：求解最大可分配用户数 #

先构建基础模型，定义变量、约束，以最大化分配用户数为目标求解，得到该目标的最优值max_users。

from ortools.sat.python import cp_model

# 初始化模型
model = cp_model.CpModel()

# 替换为实际业务数据
U = 10  # 用户数量
S = 5   # 服务器数量
w = [2, 3, 1, 4, 2, 3, 1, 2, 3, 1]  # 每个用户的需求
C = 10  # 单服务器容量
# coverage[i][j] = True 表示服务器i覆盖用户j
coverage = [
    [True, True, False, True, False, True, False, True, False, True],
    [False, True, True, False, True, False, True, False, True, False],
    [True, False, True, True, False, False, True, True, False, False],
    [False, False, False, True, True, True, False, False, True, True],
    [True, True, True, False, False, False, True, True, True, False]
]

# 定义布尔变量x[i,j]：用户j是否分配到服务器i
x = {}
for i in range(S):
    for j in range(U):
        x[i,j] = model.NewBoolVar(f'x_{i}_{j}')
        # 邻近约束：不在覆盖范围内的用户不能分配到该服务器
        if not coverage[i][j]:
            model.Add(x[i,j] == 0)

# 定义布尔变量y[i]：服务器i是否被使用
y = {}
for i in range(S):
    y[i] = model.NewBoolVar(f'y_{i}')

# 1. 容量约束：服务器i的总用户需求不超过容量C
for i in range(S):
    model.Add(sum(w[j] * x[i,j] for j in range(U)) <= C)

# 2. 用户分配约束：每个用户最多分配到一个服务器
for j in range(U):
    model.Add(sum(x[i,j] for i in range(S)) <= 1)

# 3. 服务器使用状态关联约束：服务器被使用当且仅当有用户分配给它
for i in range(S):
    # 如果y[i]为True，至少有一个用户分配到该服务器
    model.Add(sum(x[i,j] for j in range(U)) >= 1).OnlyEnforceIf(y[i])
    # 如果y[i]为False，没有用户分配到该服务器
    model.Add(sum(x[i,j] for j in range(U)) == 0).OnlyEnforceIf(y[i].Not())

# 定义总分配用户数变量，作为第一步优化目标
total_users = model.NewIntVar(0, U, 'total_users')
model.Add(total_users == sum(x[i,j] for i in range(S) for j in range(U)))
model.Maximize(total_users)

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

# 获取最大可分配用户数
if status == cp_model.OPTIMAL:
    max_users = solver.Value(total_users)
else:
    print("第一步求解失败，无可行解")
    exit()

2. 第二步：在最大用户数约束下最小化服务器使用数 #

重置模型目标，添加“总分配用户数等于max_users”的强制约束，再以最小化服务器使用数为目标求解。

# 清除原目标，添加最大用户数约束
model.ClearObjective()
model.Add(total_users == max_users)

# 定义总使用服务器数变量，作为第二步优化目标
total_servers = model.NewIntVar(0, S, 'total_servers')
model.Add(total_servers == sum(y[i] for i in range(S)))
model.Minimize(total_servers)

# 求解第二步
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f"最优结果：分配{max_users}个用户，使用{solver.Value(total_servers)}台服务器")
    # 输出具体分配方案
    for i in range(S):
        if solver.Value(y[i]):
            print(f"\n服务器{i}分配的用户：")
            for j in range(U):
                if coverage[i][j] and solver.Value(x[i,j]):
                    print(f"  用户{j}（需求：{w[j]}）")
else:
    print("第二步求解失败，无可行解")

关键注意事项 #

• 变量关联约束：必须确保y[i]和x[i,j]的关联逻辑正确，否则会导致服务器使用数统计错误。
• 覆盖范围处理：对不在服务器覆盖范围内的用户，直接添加x[i,j] == 0的约束，避免无效计算。
• 模型重置：复用原模型时，需调用model.ClearObjective()清除旧目标，再添加新约束和目标。

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