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 

我希望這有助於。

---