CVXPY多背包分配优化的容器约束实现及相关问题问询

问题背景 #

我正在使用CVXPY实现多背包分配优化问题，核心需求是将多个源容器中的物品分配至多个背包：

• 每个物品具备自身价值
• 存在从源容器到背包的分配成本（如运输成本）
• 每个物品仅能分配至一个背包

问题与解答 #

1. 是否可添加约束，使得分配给背包的物品数量为88的倍数，且每88件物品必须来自同一源容器？

完全可以实现，需要通过定义辅助变量和约束来达成：

• 变量定义：
  • 二元变量 x[i,j,k]：取值为1表示将源容器i中的物品j分配到背包k，0则表示不分配
  • 非负整数变量 y[i,k]：表示从源容器i分配到背包k的「88件物品组」的数量（例如y[i,k]=3代表从i向k分配264件物品）
• 核心约束：
  • 同容器到同背包的分配量必须是88的倍数：sum_j x[i,j,k] = 88 * y[i,k]（对所有i,k）
  • 每个物品只能被分配一次：sum_k x[i,j,k] ≤ 1（若所有物品必须分配，可改为等于号）
  • 背包容量适配（因容量是88的倍数）：sum_i sum_j x[i,j,k] ≤ 88 * C[k]，其中C[k]为背包k可容纳的「88件物品组」的最大数量
  • 变量类型约束：y[i,k]需声明为CVXPY的Integer()类型，且y[i,k] ≥ 0

通过这些约束，就能保证背包接收的物品均以88件为一组，每组来自同一源容器，同时符合背包容量限制。

2. 若上述约束无法实现，能否在目标函数中通过权重设置最小化使用的容器数量？

可以通过引入辅助变量并在目标函数中加入惩罚项实现，具体步骤：

• 变量定义：
  新增二元变量 z[i,k]：取值为1表示源容器i有物品分配至背包k，0则表示无
• 关联约束：
  对所有i,j,k，添加约束 x[i,j,k] ≤ z[i,k]——只要源容器i有任何一件物品分配到背包k，z[i,k]就必须为1，以此标记该容器被背包k使用
• 目标函数调整：
  计算所有背包涉及的总容器使用次数：sum_k sum_i z[i,k]，给这个值设置一个惩罚权重w（权重需根据业务场景设定，建议远大于单位分配成本，确保优先减少容器使用），将其纳入原目标函数：
  若原目标为最大化总价值减总成本，调整后为：

  objective = cp.Maximize(
      cp.sum((value[i,j] - cost[i,k]) * x[i,j,k] for i,j,k) 
      - w * cp.sum(z[i,k] for i,k)
  )
  

  若原目标为最小化总成本，则调整为：

  objective = cp.Minimize(
      cp.sum(cost[i,k] * x[i,j,k] for i,j,k) 
      + w * cp.sum(z[i,k] for i,k)
  )
  

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