当添加合理的约束时，Python纸浆MILP目标无效

Question

我正在实现一个已知有效的混合整数线性规划公式。但是，当添加一个约束时，目标函数变为：

MAXIMIZE
0*__dummy + False

以下是没有附加约束的公式，它按预期工作：

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

这个附加约束使目标函数无效：

# 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