Цель Python Pulps MILP аннулируется, когда добавляется разумное ограничение

Я реализую формулу смешанного целочисленного линейного программирования, которая, как известно, работает. Однако при добавлении одного из ограничений целевая функция становится следующей:

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

Что дает?


python pulp
person xiaolingxiao    schedule 12.12.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, вы используете '‹' вместо '‹='.

Как и все инструменты линейного программирования, PuLP не может обрабатывать строгое неравенство, поэтому измените ограничение на:

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