如何在Python Pyomo SCIP中重写MAX函数解决装箱约束优化问题？

问题分析 #

你在使用Pyomo+SCIP求解双目标装箱问题时，原目标函数中的max()操作无法被SCIP识别——线性规划求解器仅支持线性表达式，而max()属于非线性操作，因此抛出布尔转换错误。

解决方案：将MAX操作线性化 #

我们可以通过新增变量和约束，把“每个箱子的最大物品价值”这个非线性需求转化为线性约束，具体步骤如下：

1. 新增变量 #

添加一个连续变量bin_max_value，用于记录每个箱子中物品的最大价值：

max_item_value = max(item_values)
model.bin_max_value = pyo.Var(range(max_num_bins), within=pyo.NonNegativeReals, bounds=(0, max_item_value))

2. 添加线性约束 #

• 约束1：确保bin_max_value[j]不小于箱子j中所有已放入物品的价值
  对每个箱子j和物品i，若物品i被放入箱子j（bins_loc[i,j]=1），则bin_max_value[j]必须≥该物品的价值；若未放入，约束自动失效：

  model.bin_max_value_constraint = pyo.ConstraintList()
  for j in range(max_num_bins):
      for i in range(num_items):
          model.bin_max_value_constraint.add(
              model.bin_max_value[j] >= model.bins_loc[i,j] * item_values[i]
          )
  

• 约束2：未启用的箱子其bin_max_value必须为0
  避免未使用的箱子对目标函数产生无效贡献：

  model.bin_max_value_zero_constraint = pyo.ConstraintList()
  for j in range(max_num_bins):
      model.bin_max_value_zero_constraint.add(
          model.bin_max_value[j] <= model.bins_on[j] * max_item_value
      )
  

3. 修改目标函数 #

将原来使用max()的obj2替换为新增变量的求和：

obj1 = sum(model.bins_on[j] for j in range(max_num_bins))
obj2 = sum(model.bin_max_value[j] for j in range(max_num_bins))
model.obj = pyo.Objective(expr=obj1 + obj2, sense=pyo.minimize)

完整修改后代码 #

import pyomo.environ as pyo
from pyomo.opt import SolverFactory

bin_capacity = 8
item_weights = [2, 4, 2, 5, 1, 1, 3, 4, 2, 3]
item_values = [10, 15, 20, 34, 22, 1, 23, 3, 25, 90]
num_items = len(item_weights)
max_num_bins = len(item_weights)
max_item_value = max(item_values)  # 新增：物品最大价值

model = pyo.ConcreteModel()

# 变量定义
model.bins_loc = pyo.Var(range(num_items), range(max_num_bins), within=pyo.Binary)
model.bins_on = pyo.Var(range(max_num_bins), within=pyo.Binary)
model.bin_max_value = pyo.Var(range(max_num_bins), within=pyo.NonNegativeReals, bounds=(0, max_item_value))  # 新增变量

# 约束定义
model.bins_on_constraint = pyo.ConstraintList()
for j in range(max_num_bins):
    model.bins_on_constraint.add(expr=(1 - model.bins_on[j]) * (sum(model.bins_loc[i, j] for i in range(num_items))) <= 0)

model.capacity_exceed_constraint = pyo.ConstraintList()
for j in range(max_num_bins):
    model.capacity_exceed_constraint.add(expr=sum((model.bins_loc[i, j] * item_weights[i]) for i in range(num_items)) <= bin_capacity)

if max_num_bins > 1:
    model.onebin_per_item_constraint = pyo.ConstraintList()
    for i in range(num_items):
        model.onebin_per_item_constraint.add(expr=sum(model.bins_loc[i, j] for j in range(max_num_bins)) == 1)

# 新增：bin_max_value相关约束
model.bin_max_value_constraint = pyo.ConstraintList()
for j in range(max_num_bins):
    for i in range(num_items):
        model.bin_max_value_constraint.add(model.bin_max_value[j] >= model.bins_loc[i,j] * item_values[i])

model.bin_max_value_zero_constraint = pyo.ConstraintList()
for j in range(max_num_bins):
    model.bin_max_value_zero_constraint.add(model.bin_max_value[j] <= model.bins_on[j] * max_item_value)

# 目标函数
obj1 = sum(model.bins_on[j] for j in range(max_num_bins))
obj2 = sum(model.bin_max_value[j] for j in range(max_num_bins))
model.obj = pyo.Objective(expr=obj1 + obj2, sense=pyo.minimize)

# 求解
opt = SolverFactory('scipampl', executable=r'scipampl.exe')
result = opt.solve(model)

# 可选：打印结果
print("使用的箱子数量：", sum(pyo.value(model.bins_on[j]) for j in range(max_num_bins)))
for j in range(max_num_bins):
    if pyo.value(model.bins_on[j]) > 0.5:
        items_in_bin = [i for i in range(num_items) if pyo.value(model.bins_loc[i,j]) > 0.5]
        print(f"箱子{j}包含物品：{items_in_bin}，最大价值：{pyo.value(model.bin_max_value[j])}")

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