Python的纸浆整数线性规划与动态约束

Question

我要解决的混合整数线性规划具有以下目标函数：

J =最大化（F1（x）+ F2（x）的） 受约束：成本（x）< =阈值

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

f2是基于所选变量之间的相似性的函数。我不知道如何在纸浆中制定这个功能。

这是我最小的工作示例中，函数f2是两种成分之间的相似性，我想补充similarity[i][j]目标函数，如果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) 

此代码基本上只考虑静态成本（编码成本变量）。我如何动态添加​​变量的相似性成本？

Answer 1

我相信你想要做的是补充，实际上是说，当这两种成分i和j被选中，说明两个i和j存在相关的额外费用，这是在​​描述的交互项是什么矩阵。我将假设（因为它是在你的情况下）​​是一个对称矩阵，因为i和j的顺序无关紧要（只有当它们都被选中时才重要）。

一个幼稚的公式将增加术语selected[i, j] * x[i] * x[j]到目标。这会使问题成为非线性问题，尽管其结构并不是非常困难，但有一个常见的建模技巧来保持模型的线性。这里是。

我们定义了一组新的变量y_{ij}，仅当i和j参与解决方案时，才会等于1。请注意，我们可以将它们定义为i>j或j<i，因为我们并不真正关心排序。在我们施加的限制：

y_{ij} <= x_i 
y_{ij} <= x_j 
y_{ij} >= x_i + x_j - 1 

这组限制，保证y_{ij}等于只有当x_i和x_j等于1，这是我们想要的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 

我希望这有助于。

---