具有多个约束的组合优化
Combinatorial optimization with multiple constraints
我有一个问题涉及游戏中的装备优化，但我会用这个例子来简化它：
- 假设我有 4 个包。
- 我有一套不同的物品，有 4 种类型。
- 每件商品都有其重量和价格。
- 每袋装一种物品，4 袋 - 4 种类型。
我想最大化我携带的所有包的价格，但我有以下限制：
- 每个袋子最多可容纳 6 件物品。也可以为空。
- 所有 4 件行李的总重量不得超过 700 公斤。
- 每个袋子都有最小重量值，即使是空袋子也按50kg计算（一个袋子里装1件25kg的东西还是算50kg，装1件51kg的东西还是算51kg）。
物品数量范围为200~300，最多可以选择6*4=24个物品，无法暴力破解
还有其他因素，但不属于组合问题，可以通过简单的编程来解决
这是什么问题？它是线性规划的子集吗？
你知道我可以研究什么样的算法来解决这个问题吗？
我开始阅读有关线性规划的内容，但我在理解某些符号时遇到了问题。我有编程经验，但不涉及数学。
更新
我调查了一下，现在我知道这是一个多维或多项选择的背包问题。解决了简单的背包问题，现在我只剩下 1 个约束条件，即 6 个项目限制。
有人知道解决这个问题的好方法吗？
更新 2
我现在正在使用 GLPK 对这个问题建模并解决它，我非常接近完成它，但是我被一个简单的约束所困。
# Size of knapsack
param s;
# Total of items
param t;
# Type of items
set Z;
# Min bag
param m;
# Items: index, size, profit, count, type
set I, dimen 5;
# Indices
set J := setof{(i,s,p,o,z) in I} i;
# Assignment
var a{J}, binary;
#maximize profit
maximize obj :
sum{(i,s,p,o,z) in I} p*a[i];
/*s.t. size :
sum{(i,s,p,o,z) in I} s*a[i] <= c;*/
#constraint of total weight, but with the min value for each bag
#the min function doesn't work, it says argument for min has invalid type
#something about it not being a linear function
s.t. size :
sum{zz in Z} (
min(m, sum{(i,s,p,o,z) in I: zz=z} (s*a[i]) )
) <= c;
#constraint of number of items in each bag, i put an extra count number
#in the set so i could sum it and make it a constraint
s.t. count{zz in Z}:
sum{(i,s,p,o,z) in I: zz=z} o*a[i] <= t;
solve;
printf "The bag contains:\n";
printf {(i,s,p,o,z) in I: a[i] == 1} " %i", i;
printf "\n";
data;
#set of type of items
set Z := 1 2 3 4;
# Total weight limit
param c := 100;
# Only 2 items per bag
param t := 2;
# Min bag value, if the bag weights less than it, then it counts as this value
param M := 10;
# Items: index, size, profit, count, type
set I :=
1 10 10 1 1
2 10 10 1 1
3 15 45 1 2
4 20 20 1 2
5 20 20 1 3
6 24 24 1 3
7 24 25 1 4
8 50 50 1 4;
end;
注意：我在这里使用了不同的值以使其较小。
这是我的模型，它在没有最小重量限制的情况下工作，我只需要它求和 50 公斤的最小值或行李总数，但 min 函数在那里不起作用。我试过这个公式
（无法 post 图片）
但是我也不会使用abs函数
有人能为我指出正确的方向吗？
如果您正在寻找一个精确的最优答案，那么该问题是 NP 完全问题，但是，我注意到您描述的问题集非常小。
如果您的问题很小，那么蛮力搜索是可行的：您可以生成所有可能的解决方案，计算解决方案成本，然后选择最佳解决方案。
如果您的示例仅打算概述问题描述，而您的现实生活中的问题集实际上是 "large"，则暴力破解将不起作用，因为执行时间会随着数量的增加呈指数增长项目。这是一个相当 old paper on this problem.
一个有趣的通知是，you can transform your constraints into numerical "penalties" 并使用不受约束的优化技术，稍微简化了您的问题。
保证最优解的算法仍然需要启发式修剪 bad/unfeasible 和 "dominated" 快速解决方案。
根据我读过的研究，即使使用启发式修剪，这种方法对于超过相对较小的集合来说实际上是不可行的 "paper about 2 phase" approach。
典型的元启发式优化技术适用于较大的集合，特别是 Simulated Annealing、禁忌搜索、群体。
您可以将您的问题表述为 0-1 整数规划，并使用 GLPK 或其他线性规划求解器（glpk 是免费的）求解。唯一的问题：你带的是空袋子吗？
让
i = {1,2,3,4} -- set of item types
j -- set of items
x_ij = {0,1} -- decision variable for jth item of ith type
w_ij and p_ij -- weights and profits
max sum_ij p_ij*x_ij
subject to:
sum_j x_ij <= 6 for all i // at most 6 items in a bag
// if you need empty bags:
sum_ij w_ij*x_ij + 4*50 <= 700 kg // total weight
x_ij = {0,1} for all i and j.
如果你不需要空袋那么配方就变得更复杂了
max sum_ij p_ij*x_ij
subject to:
sum_j x_ij <= 6 for all i // at most 6 items in a bag
sum_ij w_ij*x_ij + 50*(sum_i y_i) <= 700 kg // total weight
y_i <= sum_j x_ij for all i
N*y_i >= sum_j x_ij for all i // N -- total number of items of ith type,
// fixed value, not a variable; e.g.,
// you have 10 items of each kind then N=10
y_i = {0,1} for all i
x_ij = {0,1} for all i and j.
如果你需要解决一次程序那么我建议写一个cplex .lp文件http://www-01.ibm.com/support/knowledgecenter/SS9UKU_12.4.0/com.ibm.cplex.zos.help/FileFormats/topics/LP.html并用glpsolve解决它;否则使用 c++ 或 python glpk 可调用库。
更新 1：
可以分两步线性化约束 min{50, sum_i x_i*w_i}。为简单起见，考虑一个背包。让
M -- the total possible weight (sum up all input items' weights)
y={0,1} -- when sum_i x_i*w_i >= 50 y=1, otherwise y=0
min{50, sum_i x_i*w_i} <= 100 is equivalent to
(0): (1-y)*50 + y*(sum_i x_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i
这有点不寻常，但它是正确的。实际上，当 sum_i x_i*w_i >= 50 时，求解器必须通过约束 (1) 将 y 设置为 1，同时 (2) 只是 0 >= 50-sum_i x_i*w_i <= 0，即是多余的；当 sum_i x_i*w_i < 50、y=0 by (2) 和现在 (1) 是多余的。
下一步是线性化 (0) 中的第二项。让z_i = {0,1}，它将代表y*x_i项。请注意 y*x_i 只有当两项都为 1 时才为 1，否则为 0。因此，
y*(sum_i x_i*w_i) is equivalent to
sum_i z_i*w_i
2*z_i <= x_i + y, for all i
z_i >= x_i + y - 1, for all i
和以前一样，只有当x_i=y=1 时，很容易检查z_i = 1，否则为0。
线性化后您的约束如下所示：
(0): (1-y)*50 + (sum_i z_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i
(3): 2*z_i <= x_i + y, for all i
(4): z_i >= x_i + y - 1, for all i
y = {0,1}, z_i = {0,1}
为了处理 50 公斤的行李限制，您必须为每个行李的重量创建一个变量，W_j
W_j >= 50 for all j
W_j >= sum_i w_i * X_ij for all j
sum_j W_j <= 700
这样一来，行李的重量始终至少为 50 公斤，但如果物品的重量超过 50 公斤（根据您的问题定义）。
祝你好运:)
我有一个问题涉及游戏中的装备优化，但我会用这个例子来简化它：
- 假设我有 4 个包。
- 我有一套不同的物品，有 4 种类型。
- 每件商品都有其重量和价格。
- 每袋装一种物品，4 袋 - 4 种类型。
我想最大化我携带的所有包的价格，但我有以下限制：
- 每个袋子最多可容纳 6 件物品。也可以为空。
- 所有 4 件行李的总重量不得超过 700 公斤。
- 每个袋子都有最小重量值，即使是空袋子也按50kg计算（一个袋子里装1件25kg的东西还是算50kg，装1件51kg的东西还是算51kg）。
物品数量范围为200~300，最多可以选择6*4=24个物品，无法暴力破解
还有其他因素，但不属于组合问题，可以通过简单的编程来解决
这是什么问题？它是线性规划的子集吗？
你知道我可以研究什么样的算法来解决这个问题吗？
我开始阅读有关线性规划的内容，但我在理解某些符号时遇到了问题。我有编程经验，但不涉及数学。
更新
我调查了一下，现在我知道这是一个多维或多项选择的背包问题。解决了简单的背包问题，现在我只剩下 1 个约束条件，即 6 个项目限制。
有人知道解决这个问题的好方法吗？
更新 2
我现在正在使用 GLPK 对这个问题建模并解决它，我非常接近完成它，但是我被一个简单的约束所困。
# Size of knapsack
param s;
# Total of items
param t;
# Type of items
set Z;
# Min bag
param m;
# Items: index, size, profit, count, type
set I, dimen 5;
# Indices
set J := setof{(i,s,p,o,z) in I} i;
# Assignment
var a{J}, binary;
#maximize profit
maximize obj :
sum{(i,s,p,o,z) in I} p*a[i];
/*s.t. size :
sum{(i,s,p,o,z) in I} s*a[i] <= c;*/
#constraint of total weight, but with the min value for each bag
#the min function doesn't work, it says argument for min has invalid type
#something about it not being a linear function
s.t. size :
sum{zz in Z} (
min(m, sum{(i,s,p,o,z) in I: zz=z} (s*a[i]) )
) <= c;
#constraint of number of items in each bag, i put an extra count number
#in the set so i could sum it and make it a constraint
s.t. count{zz in Z}:
sum{(i,s,p,o,z) in I: zz=z} o*a[i] <= t;
solve;
printf "The bag contains:\n";
printf {(i,s,p,o,z) in I: a[i] == 1} " %i", i;
printf "\n";
data;
#set of type of items
set Z := 1 2 3 4;
# Total weight limit
param c := 100;
# Only 2 items per bag
param t := 2;
# Min bag value, if the bag weights less than it, then it counts as this value
param M := 10;
# Items: index, size, profit, count, type
set I :=
1 10 10 1 1
2 10 10 1 1
3 15 45 1 2
4 20 20 1 2
5 20 20 1 3
6 24 24 1 3
7 24 25 1 4
8 50 50 1 4;
end;
注意：我在这里使用了不同的值以使其较小。
这是我的模型，它在没有最小重量限制的情况下工作，我只需要它求和 50 公斤的最小值或行李总数，但 min 函数在那里不起作用。我试过这个公式
（无法 post 图片）
但是我也不会使用abs函数
有人能为我指出正确的方向吗？
如果您正在寻找一个精确的最优答案，那么该问题是 NP 完全问题，但是，我注意到您描述的问题集非常小。
如果您的问题很小，那么蛮力搜索是可行的：您可以生成所有可能的解决方案，计算解决方案成本，然后选择最佳解决方案。
如果您的示例仅打算概述问题描述，而您的现实生活中的问题集实际上是 "large"，则暴力破解将不起作用，因为执行时间会随着数量的增加呈指数增长项目。这是一个相当 old paper on this problem.
一个有趣的通知是，you can transform your constraints into numerical "penalties" 并使用不受约束的优化技术，稍微简化了您的问题。
保证最优解的算法仍然需要启发式修剪 bad/unfeasible 和 "dominated" 快速解决方案。
根据我读过的研究，即使使用启发式修剪，这种方法对于超过相对较小的集合来说实际上是不可行的 "paper about 2 phase" approach。
典型的元启发式优化技术适用于较大的集合，特别是 Simulated Annealing、禁忌搜索、群体。
您可以将您的问题表述为 0-1 整数规划，并使用 GLPK 或其他线性规划求解器（glpk 是免费的）求解。唯一的问题：你带的是空袋子吗？ 让
i = {1,2,3,4} -- set of item types
j -- set of items
x_ij = {0,1} -- decision variable for jth item of ith type
w_ij and p_ij -- weights and profits
max sum_ij p_ij*x_ij
subject to:
sum_j x_ij <= 6 for all i // at most 6 items in a bag
// if you need empty bags:
sum_ij w_ij*x_ij + 4*50 <= 700 kg // total weight
x_ij = {0,1} for all i and j.
如果你不需要空袋那么配方就变得更复杂了
max sum_ij p_ij*x_ij
subject to:
sum_j x_ij <= 6 for all i // at most 6 items in a bag
sum_ij w_ij*x_ij + 50*(sum_i y_i) <= 700 kg // total weight
y_i <= sum_j x_ij for all i
N*y_i >= sum_j x_ij for all i // N -- total number of items of ith type,
// fixed value, not a variable; e.g.,
// you have 10 items of each kind then N=10
y_i = {0,1} for all i
x_ij = {0,1} for all i and j.
如果你需要解决一次程序那么我建议写一个cplex .lp文件http://www-01.ibm.com/support/knowledgecenter/SS9UKU_12.4.0/com.ibm.cplex.zos.help/FileFormats/topics/LP.html并用glpsolve解决它;否则使用 c++ 或 python glpk 可调用库。
更新 1：
可以分两步线性化约束 min{50, sum_i x_i*w_i}。为简单起见，考虑一个背包。让
M -- the total possible weight (sum up all input items' weights)
y={0,1} -- when sum_i x_i*w_i >= 50 y=1, otherwise y=0
min{50, sum_i x_i*w_i} <= 100 is equivalent to
(0): (1-y)*50 + y*(sum_i x_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i
这有点不寻常，但它是正确的。实际上，当 sum_i x_i*w_i >= 50 时，求解器必须通过约束 (1) 将 y 设置为 1，同时 (2) 只是 0 >= 50-sum_i x_i*w_i <= 0，即是多余的；当 sum_i x_i*w_i < 50、y=0 by (2) 和现在 (1) 是多余的。
下一步是线性化 (0) 中的第二项。让z_i = {0,1}，它将代表y*x_i项。请注意 y*x_i 只有当两项都为 1 时才为 1，否则为 0。因此，
y*(sum_i x_i*w_i) is equivalent to
sum_i z_i*w_i
2*z_i <= x_i + y, for all i
z_i >= x_i + y - 1, for all i
和以前一样，只有当x_i=y=1 时，很容易检查z_i = 1，否则为0。
线性化后您的约束如下所示：
(0): (1-y)*50 + (sum_i z_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i
(3): 2*z_i <= x_i + y, for all i
(4): z_i >= x_i + y - 1, for all i
y = {0,1}, z_i = {0,1}
为了处理 50 公斤的行李限制，您必须为每个行李的重量创建一个变量，W_j
W_j >= 50 for all j
W_j >= sum_i w_i * X_ij for all j
sum_j W_j <= 700
这样一来，行李的重量始终至少为 50 公斤，但如果物品的重量超过 50 公斤（根据您的问题定义）。
祝你好运:)