Python Pulp整数线性规划与动态约束

Question

我希望解决以下目标函数的混合整数线性规划问题：

J = 最大化 (f1(x) + f2(x)) 约束条件：cost(x) <= 阈值

其中，x是所选变量集合，f1和f2是两个得分函数，cost是成本函数。

f2是基于所选变量之间相似度的函数。我不知道如何在pulp中表达这个函数。

这是我的最小工作示例，其中f2函数是两个成分之间的相似度，如果j已经在所选变量中，则我想将similarity[i][j]添加到目标函数中，但不知道如何实现。

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)

这段代码基本上只考虑了静态成本（以costs变量编码）。如何动态添加相似性成本，这些成本由similarity变量表示？

- CentAu

---

相似度数组代表什么？ - dassouki

这基本上是一个矩阵，返回元素之间的相似度。也就是说，该矩阵的 (i,j) 元素是成分 i 和成分 j 之间的相似度。 - CentAu

Answer 1

我认为你想做的是添加一个交互项，它表明当选择了两个成分i和j时，存在一个额外的成本与i和j同时存在相关，在相似性矩阵中描述。我会假设（因为在你的情况下如此）相似性是对称矩阵，因为i和j的顺序并不重要（只有在两者都被选择或未被选择时才重要）。

一个天真的公式是将选定[i，j] * x [i] * x [j]添加到目标中。这将使问题变得非线性，尽管它的结构并不难以处理，但有一个常见的建模技巧可以保持模型线性。在这里，它是：

我们定义一组新变量y_ij，只有当i和j都参与解决方案时才等于1。请注意，我们可以定义它们，使i>j或j

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

我希望您能从中受益。

---

- Ioannis

---

太棒了！感谢您的详细回复。 - CentAu