基于多约束算法找到最优值
Find optimum value based on multiple constraints algorithm
我有以下向量（或 C 矩阵和 V 向量）和 K1、K2、K3 常量
Constraints [c11 + c12 + c13 + ... + c1n] <= K1
[c21 + c22 + c23 + ... + c2n] <= K2
[c31 + c32 + c33 + ... + c3n] <= K3
-------------------------------------------------
Values [ v1 + v2 + v3 + ... + vn] -> Max
作为输入，我得到 C 和 V 的值，作为输出，我想提供 X 向量，它只包含 0 和 1 值， 给我
[c11 * x1 + c12 * x2 + c13 * x3 + ... + c1n * xn <= K1
[c21 * x1 + c22 * x2 + c23 * x3 + ... + c2n * xn <= K2
[c31 * x1 + c32 * x2 + c33 * x3 + ... + c3n * xn <= K3
------------------------------------------------------
[ v1 * x1 + v2 * x2 + v3 * x3 + ... + vn * xn] -> Max
作为一个过度简化的例子：
输入：
K1 = 15
K2 = 20
K3 = 10
c1 = [3, 6, 8] | sum(c1 * X) <= 15
c2 = [8, 9, 3] | sum(c2 * X) <= 20
c3 = [7, 5, 2] | sum(c3 * x) <= 10
v = [2, 5, 3] | sum( v * X) -> Max
提供最大化约束内值的 X 向量的输出：
X = [0, 1, 1]
我正在寻找一种优雅的算法（也可能是 Java 或 C# 实现）根据输入给我输出。我们可以假设约束的数量始终为 3，并且提供了 C 和 V（以及 K1、K2、K3）的所有值。
另一个简单的例子可能是：你有一个房间（3D），所以你的约束是宽度、高度和[=房间的 28=]length (K1, K2, K3) 和你有一个家具项目列表（n 项目）。所有 i 家具项目都有自己的 lenght (c1i), width (c2i ) 和 高度 (c3i) 和值 (vi)。您想要用最有价值 的家具物品装点房间，这些家具物品适合房间尺寸。所以输出是一个 n 长的 X 变量，它只包含 0 和 1 值，如果 xi = 1，第 i 个元素被选为在房间里，如果 xi = 0 则第 i 个元素不会被选为在房间里。
这是多维0-1背包问题，即NP-hard。
可以找到解决方法的概述here, a relatively recent research paper here and a genetic algorithm implementation in python here。
取自 python 实现（上面的 link pyeasyga）是这个例子：
from pyeasyga import pyeasyga
# setup data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
ga = pyeasyga.GeneticAlgorithm(data) # initialise the GA with data
ga.population_size = 200 # increase population size to 200 (default value is 50)
# define a fitness function
def fitness(individual, data):
weight, volume, price = 0, 0, 0
for (selected, item) in zip(individual, data):
if selected:
weight += item[0]
volume += item[1]
price += item[2]
if weight > 12210 or volume > 12:
price = 0
return price
ga.fitness_function = fitness # set the GA's fitness function
ga.run() # run the GA
print ga.best_individual() # print the GA's best solution
data的最后一个维度是价格，另外两个维度是重量和体积。
您可以调整此示例，使其解决二维以上的问题。
希望对您有所帮助。
编辑：遗传算法一般不保证找到最优解。对于三个约束，它可能会找到 好的 解决方案，但不能保证最优性。
更新：数学优化解决方案
另一种选择是使用 PuLP，一种用于数学优化问题的开源建模框架。该框架调用求解器，即专门设计用于解决优化问题的软件。简而言之，框架的工作是link用解决问题时需要的形式描述数学问题，求解器的工作是实际解决问题。
您可以安装纸浆，例如 pip (pip install pulp)。
这是之前在 pulp 中建模的示例，通过修改 this 示例：
import pulp as plp
# Let's keep the same data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
w_cap, v_cap = 12210, 12
rng_items = xrange(len(data))
# Restructure the data in dictionaries
items = ['item_{}'.format(i) for i in rng_items]
weight = {items[i]: data[i][0] for i in rng_items}
volume = {items[i]: data[i][1] for i in rng_items}
price = {items[i]: data[i][2] for i in rng_items}
# Make the problem, declare it as a maximization problem
problem_name = "3D Knapsack"
prob = plp.LpProblem(problem_name, plp.LpMaximize)
# Define the variables
plp_vars = plp.LpVariable.dicts('', items, 0, 1, plp.LpInteger)
# Objective function
prob += plp.lpSum([price[i]*plp_vars[i] for i in plp_vars])
# Constraints
prob += plp.lpSum([weight[i]*plp_vars[i] for i in plp_vars]) <= w_cap
prob += plp.lpSum([volume[i]*plp_vars[i] for i in plp_vars]) <= v_cap
# Solution
prob.solve()
# If you want to save the problem formulation in a file
# prob.writeLP(problem_name + 'lp')
# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
print v.name, "=", v.varValue
# The optimised objective function value is printed to the screen
print "Total gain = ", plp.value(prob.objective)
objective 为 3,540。
如何运行的演示是 here。
完全可以解决，例如使用Gurobi的C#绑定：
var env = new GRBEnv();
var model = new GRBModel(env);
var vars = model.AddVars(v.Length, GRB.BINARY);
model.Update();
GRBLinExpr obj = 0.0;
obj.AddTerms(v, vars, 0, v.Length);
model.SetObjective(obj, GRB.MAXIMIZE);
for (int i = 0; i < 3; i++) {
GRBLinExpr expr = 0.0;
for (int j = 0; j < C[i].Length; j++)
expr.AddTerm(C[i][j], vars[j]);
model.AddConstr(expr, GRB.LESS_EQUAL, K[i], "");
}
model.Update();
model.Optimize();
然后您可以调用 Get(GRB.DoubleAttr.X) 变量来获取它们的值。
我有以下向量（或 C 矩阵和 V 向量）和 K1、K2、K3 常量
Constraints [c11 + c12 + c13 + ... + c1n] <= K1
[c21 + c22 + c23 + ... + c2n] <= K2
[c31 + c32 + c33 + ... + c3n] <= K3
-------------------------------------------------
Values [ v1 + v2 + v3 + ... + vn] -> Max
作为输入，我得到 C 和 V 的值，作为输出，我想提供 X 向量，它只包含 0 和 1 值， 给我
[c11 * x1 + c12 * x2 + c13 * x3 + ... + c1n * xn <= K1
[c21 * x1 + c22 * x2 + c23 * x3 + ... + c2n * xn <= K2
[c31 * x1 + c32 * x2 + c33 * x3 + ... + c3n * xn <= K3
------------------------------------------------------
[ v1 * x1 + v2 * x2 + v3 * x3 + ... + vn * xn] -> Max
作为一个过度简化的例子：
输入：
K1 = 15
K2 = 20
K3 = 10
c1 = [3, 6, 8] | sum(c1 * X) <= 15
c2 = [8, 9, 3] | sum(c2 * X) <= 20
c3 = [7, 5, 2] | sum(c3 * x) <= 10
v = [2, 5, 3] | sum( v * X) -> Max
提供最大化约束内值的 X 向量的输出：
X = [0, 1, 1]
我正在寻找一种优雅的算法（也可能是 Java 或 C# 实现）根据输入给我输出。我们可以假设约束的数量始终为 3，并且提供了 C 和 V（以及 K1、K2、K3）的所有值。
另一个简单的例子可能是：你有一个房间（3D），所以你的约束是宽度、高度和[=房间的 28=]length (K1, K2, K3) 和你有一个家具项目列表（n 项目）。所有 i 家具项目都有自己的 lenght (c1i), width (c2i ) 和 高度 (c3i) 和值 (vi)。您想要用最有价值 的家具物品装点房间，这些家具物品适合房间尺寸。所以输出是一个 n 长的 X 变量，它只包含 0 和 1 值，如果 xi = 1，第 i 个元素被选为在房间里，如果 xi = 0 则第 i 个元素不会被选为在房间里。
这是多维0-1背包问题，即NP-hard。
可以找到解决方法的概述here, a relatively recent research paper here and a genetic algorithm implementation in python here。
取自 python 实现（上面的 link pyeasyga）是这个例子：
from pyeasyga import pyeasyga
# setup data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
ga = pyeasyga.GeneticAlgorithm(data) # initialise the GA with data
ga.population_size = 200 # increase population size to 200 (default value is 50)
# define a fitness function
def fitness(individual, data):
weight, volume, price = 0, 0, 0
for (selected, item) in zip(individual, data):
if selected:
weight += item[0]
volume += item[1]
price += item[2]
if weight > 12210 or volume > 12:
price = 0
return price
ga.fitness_function = fitness # set the GA's fitness function
ga.run() # run the GA
print ga.best_individual() # print the GA's best solution
data的最后一个维度是价格，另外两个维度是重量和体积。
您可以调整此示例，使其解决二维以上的问题。
希望对您有所帮助。
编辑：遗传算法一般不保证找到最优解。对于三个约束，它可能会找到 好的 解决方案，但不能保证最优性。
更新：数学优化解决方案
另一种选择是使用 PuLP，一种用于数学优化问题的开源建模框架。该框架调用求解器，即专门设计用于解决优化问题的软件。简而言之，框架的工作是link用解决问题时需要的形式描述数学问题，求解器的工作是实际解决问题。
您可以安装纸浆，例如 pip (pip install pulp)。
这是之前在 pulp 中建模的示例，通过修改 this 示例：
import pulp as plp
# Let's keep the same data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
w_cap, v_cap = 12210, 12
rng_items = xrange(len(data))
# Restructure the data in dictionaries
items = ['item_{}'.format(i) for i in rng_items]
weight = {items[i]: data[i][0] for i in rng_items}
volume = {items[i]: data[i][1] for i in rng_items}
price = {items[i]: data[i][2] for i in rng_items}
# Make the problem, declare it as a maximization problem
problem_name = "3D Knapsack"
prob = plp.LpProblem(problem_name, plp.LpMaximize)
# Define the variables
plp_vars = plp.LpVariable.dicts('', items, 0, 1, plp.LpInteger)
# Objective function
prob += plp.lpSum([price[i]*plp_vars[i] for i in plp_vars])
# Constraints
prob += plp.lpSum([weight[i]*plp_vars[i] for i in plp_vars]) <= w_cap
prob += plp.lpSum([volume[i]*plp_vars[i] for i in plp_vars]) <= v_cap
# Solution
prob.solve()
# If you want to save the problem formulation in a file
# prob.writeLP(problem_name + 'lp')
# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
print v.name, "=", v.varValue
# The optimised objective function value is printed to the screen
print "Total gain = ", plp.value(prob.objective)
objective 为 3,540。
如何运行的演示是 here。
完全可以解决，例如使用Gurobi的C#绑定：
var env = new GRBEnv();
var model = new GRBModel(env);
var vars = model.AddVars(v.Length, GRB.BINARY);
model.Update();
GRBLinExpr obj = 0.0;
obj.AddTerms(v, vars, 0, v.Length);
model.SetObjective(obj, GRB.MAXIMIZE);
for (int i = 0; i < 3; i++) {
GRBLinExpr expr = 0.0;
for (int j = 0; j < C[i].Length; j++)
expr.AddTerm(C[i][j], vars[j]);
model.AddConstr(expr, GRB.LESS_EQUAL, K[i], "");
}
model.Update();
model.Optimize();
然后您可以调用 Get(GRB.DoubleAttr.X) 变量来获取它们的值。