如何在MIP求解器中表达二元变量不等约束？OR-Tools球箱分配问题

一、二元变量不等的线性约束表达 #

对于两个布尔变量x和y，x != y无法直接在MIP求解器中使用，可通过以下两种等价的线性约束实现：

• 方式1：直接用等式约束 x + y = 1（仅适用于x和y必须有一个为1的场景）
• 方式2：用两个不等式约束 x ≤ 1 - y 和 y ≤ 1 - x（更通用，支持x和y同时为0的情况）

二、球箱同质分配的约束建模 #

针对你的问题，核心要求是同一容器内不能同时存在不同尺寸的球，以下提供两种可行的建模方式：

方式1：基于球对的约束（直观易实现） #

遍历所有尺寸不同的球对，对每个容器添加约束：这两个球不能同时放入该容器。即对于任意尺寸不同的球i₁、i₂，以及任意容器j，添加约束：
dv[(i₁,j)] + dv[(i₂,j)] ≤ 1

同时需要添加基础约束：每个球必须恰好放入一个容器：
sum(dv[(i,j)] for j in bins) = 1 对所有球i

方式2：基于容器尺寸标记的约束（更高效，适合大规模问题） #

为每个容器定义3个布尔变量，标记该容器是否存放对应尺寸的球：

• bin_s[j]：容器j是否放小球
• bin_m[j]：容器j是否放中球
• bin_l[j]：容器j是否放大球

然后添加以下约束：

1. 每个容器最多只能对应一种尺寸（可根据需求改为恰好一种）：
   bin_s[j] + bin_m[j] + bin_l[j] ≤ 1 对所有容器j
2. 每个球只能放入对应尺寸标记为1的容器：
   • 若球i是小号（s）：dv[(i,j)] ≤ bin_s[j] 对所有容器j
   • 若球i是中号（m）：dv[(i,j)] ≤ bin_m[j] 对所有容器j
   • 若球i是大号（l）：dv[(i,j)] ≤ bin_l[j] 对所有容器j
3. 每个球必须恰好放入一个容器（同方式1的基础约束）

三、完整代码示例（以方式1为例） #

from ortools.linear_solver import pywraplp
import itertools

s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

balls_size = ["s", "m", "s", "m", "l", "s", "m"]
balls_id_size = {i: j for i, j in zip(range(len(balls_size)), balls_size)}

bins = ["a", "b", "c"]

# 定义决策变量：dv[(i,j)] = 1表示球i放入容器j
dv = {(i, j): s.BoolVar(f"ball_{i}_to_bin_{j}") for i, j in itertools.product(balls_id_size, bins)}

# 1. 基础约束：每个球必须恰好放入一个容器
for ball_id in balls_id_size:
    s.Add(sum(dv[(ball_id, bin_id)] for bin_id in bins) == 1)

# 2. 核心约束：同一容器内不能有不同尺寸的球
# 遍历所有球对，筛选出尺寸不同的组合
for (ball1, size1), (ball2, size2) in itertools.combinations(balls_id_size.items(), 2):
    if size1 != size2:
        # 对每个容器，这两个球不能同时放入
        for bin_id in bins:
            s.Add(dv[(ball1, bin_id)] + dv[(ball2, bin_id)] <= 1)

# 可选：添加目标函数，最小化使用的容器数量
bin_used = {j: s.BoolVar(f"bin_{j}_used") for j in bins}
for j in bins:
    s.Add(bin_used[j] >= sum(dv[(i,j)] for i in balls_id_size) / len(balls_id_size))
s.Minimize(sum(bin_used[j] for j in bins))

# 求解并输出结果
status = s.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print("最优分配方案：")
    for bin_id in bins:
        assigned_balls = [i for i in balls_id_size if dv[(i, bin_id)].solution_value() == 1]
        if assigned_balls:
            sizes = {balls_id_size[i] for i in assigned_balls}
            print(f"容器{bin_id}：球{assigned_balls}，尺寸{next(iter(sizes))}")
else:
    print("无可行解")

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