妥当な制約が追加されたときにPythonパルプMILPの目的が無効になる

Question

私は動作することが知られている混合整数の線形計画式を実装しています。しかし、制約の1つは、目的関数を追加されたときに次のようになります。

from pulp import * 


words = ['close', 'near', 'intimate'] 
pairs = [u + '-' + v for u in words for v in words if u != v] 

scores = {'close-intimate': 2.0, 
     'close-near'  : 1.5, 
     'intimate-close' : -2.0, 
     'intimate-near' : -1.0, 
     'near-close'  : -1.5, 
     'near-intimate' : 1.0} 

C = sum(abs(scores[uv]) for uv in scores) * 10 

############################################################ 
# milp 

''' 
    initialize problem 
''' 
prob = LpProblem('-'.join(words), LpMaximize) 

''' 
    initialize variables 
''' 
x = dict()  
d = dict()  
w = dict()  
s = dict()  

for uv in pairs: 
    w[uv] = LpVariable('w_' + uv, 0, 1, LpInteger ) 
    s[uv] = LpVariable('s_' + uv, 0, 1, LpInteger ) 
    d[uv] = LpVariable('d_' + uv, 0, 1, LpContinuous) 

for u in words: 
    x[u] = LpVariable('x_' + u, 0, 1, LpContinuous) 


''' 
    objective function 
''' 
objective = [ (w[ij] - s[ij]) * scores[ij] for ij in pairs ] 

prob += lpSum(objective) 

''' 
    constraints 
''' 
# d_ij = x_j - x_i 
for ij in pairs: 
    [i,j] = ij.split('-') 
    prob += x[j] - x[i] == d[ij] 

# d_ij - w_ij * C <= 0 
for ij in pairs: 
    prob += d[ij] - w[ij] * C <= 0 

# d_ij + (1 - w_ij) * C > 0 
for ij in pairs: 
    prob += d[ij] + (1 - w[ij]) * C > 0 

# d_ij + s_ij * C >= 0 
for ij in pairs: 
    prob += d[ij] + s[ij] * C >= 0 

この追加の制約は、目的関数を無効：ここ

MAXIMIZE 
0*__dummy + False 

が意図したとおりに機能追加制約のない製剤である

# d_ij - (1 - sij) * C < 0 
for ij in pairs: 
    prob += d[ij] - (1 - s[ij]) * C < 0 

何が得られますか？

Answer 1

「< =」を使用する必要がある場合は、「<」を使用しているようです。

すべての線形プログラミングツール状パルプは、厳格な不平等を扱うことができないので、あなたに制約を変更してください：

# d_ij - (1 - sij) * C < 0 
for ij in pairs: 
    prob += d[ij] - (1 - s[ij]) * C <= 0