如何在or-solver中添加非线性目标函数实现装箱剩余容量均匀分配

目标逻辑纠正 #

首先明确一个基础逻辑：所有箱子的总剩余容量 = 所有箱子初始总容量 - 所有包裹总体积，是固定常数。要让剩余容量尽可能均匀，等价于最小化各剩余容量的平方和（和固定的前提下，平方和越小代表各数值的差异越小，分布越均匀），你当前写的Maximize(score)会得到剩余容量尽可能不均匀的结果，注意根据你的需求调整目标方向。

OR-Tools 实现方案 #

分两种常用求解器场景给出实现方式：

1. 使用支持二次规划的MIP求解器（如SCIP、Gurobi、CPLEX） #

可以直接调用二次项接口添加目标：

from ortools.linear_solver import pywraplp

# 初始化求解器，选择支持MIQP的后端
solver = pywraplp.Solver.CreateSolver('SCIP')

# 入参示例
box_num = 3 # 箱子总数
parcel_num = 4 # 包裹总数
box_capacity = [10, 8, 5] # 各箱子初始容量
parcel_size = [2, 3, 1, 2] # 各包裹体积

# 定义0-1决策变量x[i][j]：1代表第j个包裹分配给第i个箱子
x = []
for i in range(box_num):
    x_i = []
    for j in range(parcel_num):
        x_i.append(solver.IntVar(0, 1, f'x_{i}_{j}'))
    x.append(x_i)

# 约束1：每个包裹必须分配给恰好一个箱子
for j in range(parcel_num):
    solver.Add(sum(x[i][j] for i in range(box_num)) == 1)

# 约束2：每个箱子装的包裹总体积不能超过自身容量
for i in range(box_num):
    solver.Add(sum(parcel_size[j] * x[i][j] for j in range(parcel_num)) <= box_capacity[i])

# 定义目标函数
objective = solver.Objective()
for i in range(box_num):
    # 计算第i个箱子的剩余容量
    cap_left = box_capacity[i] - sum(parcel_size[j] * x[i][j] for j in range(parcel_num))
    # 添加平方项，系数为1
    objective.AddQuadraticTerm(cap_left, cap_left, 1)
# 要均匀就设最小化，要不均匀就设最大化
objective.SetMinimization()

# 执行求解
status = solver.Solve()

# 输出结果（和你给出的result矩阵格式一致）
result = []
for i in range(box_num):
    row = []
    for j in range(parcel_num):
        row.append(int(solver.Value(x[i][j])))
    result.append(row)
print(result)

2. 使用CP-SAT求解器 #

CP-SAT不支持直接写入二次目标，需要先定义辅助变量绑定平方值，再添加目标：

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# 入参和上面一致
box_num = 3
parcel_num = 4
box_capacity = [10, 8, 5]
parcel_size = [2, 3, 1, 2]

# 定义0-1决策变量x[i][j]
x = [[model.NewIntVar(0, 1, f'x_{i}_{j}') for j in range(parcel_num)] for i in range(box_num)]
# 定义各箱子剩余容量变量，上下界设为0到对应箱子初始容量即可
cap_left = [model.NewIntVar(0, box_capacity[i], f'cap_left_{i}') for i in range(box_num)]

# 约束1：每个包裹恰好分配一个箱子
for j in range(parcel_num):
    model.Add(sum(x[i][j] for i in range(box_num)) == 1)

# 约束2：箱子容量不超限，同时绑定cap_left变量
for i in range(box_num):
    model.Add(cap_left[i] == box_capacity[i] - sum(parcel_size[j] * x[i][j] for j in range(parcel_num)))

# 定义平方值辅助变量
cap_left_sq = [model.NewIntVar(0, box_capacity[i] ** 2, f'cap_left_sq_{i}') for i in range(box_num)]
# 用乘法约束绑定平方关系
for i in range(box_num):
    model.AddMultiplicationEquality(cap_left_sq[i], cap_left[i], cap_left[i])

# 目标：最小化平方和实现均匀分配
model.Minimize(sum(cap_left_sq))

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

# 输出结果
result = []
for i in range(box_num):
    row = []
    for j in range(parcel_num):
        row.append(int(solver.Value(x[i][j])))
    result.append(row)
print(result)

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