如何用OR-Tools/CPModel线性规划解决二进制物品筛选优化问题

问题转化思路 #

原目标是最大化剩余物品的期望值：exp_val = (Σw_i p_i x_i) / (Σw_i x_i)，其中x_i∈{0,1}（1表示保留物品i，0表示移除），且最多移除3个物品即Σ(1-x_i) ≤ 3。

由于分式目标无法直接用线性规划求解，我们通过变量替换转化为线性约束：引入连续变量t，将目标转化为最大化t，同时满足Σw_i p_i x_i ≥ t * Σw_i x_i。这样就把原问题转化为可求解的混合整数线性规划问题，能找到全局最优解，避免手动筛选的局部最优问题。

OR-Tools CPModel实现代码 #

from ortools.sat.python import cp_model

# 示例数据（替换为你的完整75个物品数据集）
data = {
    "weighting": {"0": 500, "1": 50, "2": 50, "3": 50, "4": 250, "5": 1000},
    "price": {"0": 4, "1": 78, "2": 75, "3": 170, "4": 5, "5": 4}
}

# 转换为列表格式，方便批量处理
item_ids = list(data["weighting"].keys())
weights = [int(data["weighting"][id]) for id in item_ids]
prices = [int(data["price"][id]) for id in item_ids]
n_items = len(item_ids)
max_remove = 3  # 最多移除物品数量

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

# 定义二进制变量：x[i] = 1 保留物品i，0 移除物品i
x = [model.NewBoolVar(f"x_{i}") for i in range(n_items)]

# 添加约束：移除的物品数量不超过3
model.Add(sum(1 - x[i] for i in range(n_items)) <= max_remove)

# 定义目标变量t（即要最大化的期望值）
t = model.NewFloatVar(0.0, max(prices), "expected_value")

# 添加分式目标转化后的线性约束
model.Add(
    sum(weights[i] * prices[i] * x[i] for i in range(n_items)) 
    >= t * sum(weights[i] * x[i] for i in range(n_items))
)

# 设置目标：最大化期望值t
model.Maximize(t)

# 创建求解器并执行求解
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 输出结果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"最优期望值: {solver.Value(t):.4f}")
    print("保留的物品列表:")
    for i in range(n_items):
        if solver.Value(x[i]) == 1:
            print(f"- 物品{item_ids[i]} | 权重: {weights[i]} | 价格: {prices[i]}")
    removed_count = sum(1 for i in range(n_items) if solver.Value(x[i]) == 0)
    print(f"实际移除物品数量: {removed_count}")
    
    # 手动验证计算结果
    total_weighted_price = sum(weights[i] * prices[i] for i in range(n_items) if solver.Value(x[i]) == 1)
    total_weight = sum(weights[i] for i in range(n_items) if solver.Value(x[i]) == 1)
    print(f"手动验证期望值: {total_weighted_price / total_weight:.4f}")
else:
    print("未找到可行解")

代码关键点说明 #

• 二进制变量x[i]精准标记每个物品的留舍状态
• 通过约束限制移除物品数量不超过3个
• 用连续变量t将分式目标转化为线性约束，规避分式优化的求解难点
• 依赖OR-Tools的CP-SAT求解器，能高效找到全局最优解，避免手动筛选的局部最优问题

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