Python 具有动态约束的 Pulp 整数线性规划
Python Pulp Integer Linear Program with dynamic constraint
我想用以下 objective 函数求解混合整数线性规划:
J = 最大化 (f1(x) + f2(x))
受约束:成本(x)<=阈值
其中 x 是所选变量的集合,f1 和 f2 是两个评分函数,cost 是成本函数。
f2 是一个基于所选变量之间相似性的函数。我不知道如何在纸浆中表达这个功能。
这是我的最小工作示例,其中函数 f2 是两种成分之间的相似性,如果 j
已经在选定变量中,我想将 similarity[i][j]
添加到 objective 函数,但不知道怎么做。
import numpy as np
import pulp
threshold = 200
model = pulp.LpProblem('selection', pulp.LpMaximize)
similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],
[0.08333333, 1., 0.33333333,
0., 0.11111111, 0.07692308],
[0.1, 0.33333333, 1., 0.2, 0., 0.09090909],
[0., 0., 0.2, 1., 0., 0.],
[0., 0.11111111, 0., 0., 1., 0.27272727],
[0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]])
ingredients = ['var_%d' % i for i in range(6)]
scores = np.random.randint(1, 3, size=len(ingredients))
costs = np.random.randint(20, 60, len(ingredients))
scores = dict(zip(ingredients, scores))
costs = dict(zip(ingredients, costs))
x = pulp.LpVariable.dict(
'x_%s', ingredients, lowBound=0, upBound=1, cat=pulp.LpInteger)
model += sum([scores[i] * x[i] for i in ingredients])
model += sum([costs[i] * x[i] for i in ingredients]) <= threshold
solver = pulp.solvers.PULP_CBC_CMD()
model.solve(solver)
此代码基本上只考虑静态成本(编码在成本变量中)。如何动态添加 similarity
变量的相似性成本?
I believe what you want to do is add an interaction term that essentially says that when both ingredients i
and j
are selected, there is an extra cost associated with the existence of both i
和 j
,这在 similarity
矩阵中进行了描述。我将假设(就像你的情况一样)similarity
是一个对称矩阵,因为 i
和 j
的顺序无关紧要(仅当两者都被选中时才重要)或不)。
一个天真的公式是将术语 selected[i, j] * x[i] * x[j]
添加到 objective。这会使问题成为非线性问题,尽管其结构并没有特别困难,但有一个通用的建模技巧可以使模型保持线性。在这里。
我们定义了一组新变量 y_{ij}
,只有当 i
和 j
都参与求解时,它们才等于 1
。请注意,我们可以将它们定义为 i>j
或 j<i
,因为我们并不真正关心顺序。我们施加限制:
y_{ij} <= x_i
y_{ij} <= x_j
y_{ij} >= x_i + x_j - 1
这组限制保证只有当x_i
和x_j
都等于1
时y_{ij}
才等于1
,这就是我们想要的。
您的代码的实现:
import numpy as np
import pulp
from itertools import product
threshold = 200
model = pulp.LpProblem('selection', pulp.LpMaximize)
similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],
[0.08333333, 1., 0.33333333,
0., 0.11111111, 0.07692308],
[0.1, 0.33333333, 1., 0.2, 0., 0.09090909],
[0., 0., 0.2, 1., 0., 0.],
[0., 0.11111111, 0., 0., 1., 0.27272727],
[0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]])
ingredients = ['var_%d' % i for i in range(6)]
ingredient_pairs = ['var_{}_{}'.format(
ingredients.index(var[0]), ingredients.index(var[1]))
for var in product(ingredients, ingredients)
if ingredients.index(var[0]) > ingredients.index(var[1])]
# Flatten the similarity array
indices = np.triu_indices_from(similarity)
similarity = similarity[indices]
scores = np.random.randint(1, 3, size=len(ingredients))
costs = np.random.randint(20, 60, len(ingredients))
scores = dict(zip(ingredients, scores))
costs = dict(zip(ingredients, costs))
similarity = dict(zip(ingredient_pairs, similarity))
x = pulp.LpVariable.dict(
'x_%s', ingredients, lowBound=0, upBound=1, cat=pulp.LpInteger)
y = pulp.LpVariable.dict(
'y_%s', ingredient_pairs, lowBound=0, upBound=1, cat=pulp.LpInteger)
model += sum([scores[i] * x[i] for i in ingredients]) + sum([
similarity[i] * y[i] for i in ingredient_pairs])
model += sum([costs[i] * x[i] for i in ingredients]) <= threshold
for pair in ingredient_pairs:
indexes = pair.split('_')[1:]
for index in indexes:
# y_{ij} <= x_i and y_{ij} <= x_j Q
model += y[pair] <= x['var_{}'.format(index)]
# y_{ij} >= x_i + x_j - 1
model += y[pair] >= sum(x['var_{}'.format(i)] for i in indexes) - 1
solver = pulp.solvers.PULP_CBC_CMD()
model.solve(solver)
model.writeLP('similarity.lp')
print 'Objective: {}'.format(pulp.value(model.objective))
for v in model.variables():
if v.varValue > 10e-4:
print v.name, v.varValue
希望对您有所帮助。
我想用以下 objective 函数求解混合整数线性规划:
J = 最大化 (f1(x) + f2(x)) 受约束:成本(x)<=阈值
其中 x 是所选变量的集合,f1 和 f2 是两个评分函数,cost 是成本函数。
f2 是一个基于所选变量之间相似性的函数。我不知道如何在纸浆中表达这个功能。
这是我的最小工作示例,其中函数 f2 是两种成分之间的相似性,如果 j
已经在选定变量中,我想将 similarity[i][j]
添加到 objective 函数,但不知道怎么做。
import numpy as np
import pulp
threshold = 200
model = pulp.LpProblem('selection', pulp.LpMaximize)
similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],
[0.08333333, 1., 0.33333333,
0., 0.11111111, 0.07692308],
[0.1, 0.33333333, 1., 0.2, 0., 0.09090909],
[0., 0., 0.2, 1., 0., 0.],
[0., 0.11111111, 0., 0., 1., 0.27272727],
[0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]])
ingredients = ['var_%d' % i for i in range(6)]
scores = np.random.randint(1, 3, size=len(ingredients))
costs = np.random.randint(20, 60, len(ingredients))
scores = dict(zip(ingredients, scores))
costs = dict(zip(ingredients, costs))
x = pulp.LpVariable.dict(
'x_%s', ingredients, lowBound=0, upBound=1, cat=pulp.LpInteger)
model += sum([scores[i] * x[i] for i in ingredients])
model += sum([costs[i] * x[i] for i in ingredients]) <= threshold
solver = pulp.solvers.PULP_CBC_CMD()
model.solve(solver)
此代码基本上只考虑静态成本(编码在成本变量中)。如何动态添加 similarity
变量的相似性成本?
I believe what you want to do is add an interaction term that essentially says that when both ingredients i
and j
are selected, there is an extra cost associated with the existence of both i
和 j
,这在 similarity
矩阵中进行了描述。我将假设(就像你的情况一样)similarity
是一个对称矩阵,因为 i
和 j
的顺序无关紧要(仅当两者都被选中时才重要)或不)。
一个天真的公式是将术语 selected[i, j] * x[i] * x[j]
添加到 objective。这会使问题成为非线性问题,尽管其结构并没有特别困难,但有一个通用的建模技巧可以使模型保持线性。在这里。
我们定义了一组新变量 y_{ij}
,只有当 i
和 j
都参与求解时,它们才等于 1
。请注意,我们可以将它们定义为 i>j
或 j<i
,因为我们并不真正关心顺序。我们施加限制:
y_{ij} <= x_i
y_{ij} <= x_j
y_{ij} >= x_i + x_j - 1
这组限制保证只有当x_i
和x_j
都等于1
时y_{ij}
才等于1
,这就是我们想要的。
您的代码的实现:
import numpy as np
import pulp
from itertools import product
threshold = 200
model = pulp.LpProblem('selection', pulp.LpMaximize)
similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],
[0.08333333, 1., 0.33333333,
0., 0.11111111, 0.07692308],
[0.1, 0.33333333, 1., 0.2, 0., 0.09090909],
[0., 0., 0.2, 1., 0., 0.],
[0., 0.11111111, 0., 0., 1., 0.27272727],
[0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]])
ingredients = ['var_%d' % i for i in range(6)]
ingredient_pairs = ['var_{}_{}'.format(
ingredients.index(var[0]), ingredients.index(var[1]))
for var in product(ingredients, ingredients)
if ingredients.index(var[0]) > ingredients.index(var[1])]
# Flatten the similarity array
indices = np.triu_indices_from(similarity)
similarity = similarity[indices]
scores = np.random.randint(1, 3, size=len(ingredients))
costs = np.random.randint(20, 60, len(ingredients))
scores = dict(zip(ingredients, scores))
costs = dict(zip(ingredients, costs))
similarity = dict(zip(ingredient_pairs, similarity))
x = pulp.LpVariable.dict(
'x_%s', ingredients, lowBound=0, upBound=1, cat=pulp.LpInteger)
y = pulp.LpVariable.dict(
'y_%s', ingredient_pairs, lowBound=0, upBound=1, cat=pulp.LpInteger)
model += sum([scores[i] * x[i] for i in ingredients]) + sum([
similarity[i] * y[i] for i in ingredient_pairs])
model += sum([costs[i] * x[i] for i in ingredients]) <= threshold
for pair in ingredient_pairs:
indexes = pair.split('_')[1:]
for index in indexes:
# y_{ij} <= x_i and y_{ij} <= x_j Q
model += y[pair] <= x['var_{}'.format(index)]
# y_{ij} >= x_i + x_j - 1
model += y[pair] >= sum(x['var_{}'.format(i)] for i in indexes) - 1
solver = pulp.solvers.PULP_CBC_CMD()
model.solve(solver)
model.writeLP('similarity.lp')
print 'Objective: {}'.format(pulp.value(model.objective))
for v in model.variables():
if v.varValue > 10e-4:
print v.name, v.varValue
希望对您有所帮助。