我有以下整数线性规划问题,该问题按预期分配值,但是当我添加某些约束时,目标函数似乎变得空洞。我不知道该怎么办。我正在使用 python 来解决这个问题。
非真空配方
score12 = 1
score21 = -1
C = 1000000
maximize : (w12 - s12) * score12 + (w21 - s21) * score21
subject to:
d12 = x2 - x1
d21 = x1 - x2
d12 - w12*C <= 0
d21 - w21*C <= 0
d12 + (1 - w12)*C > 0
d21 + (1 - w21)*C > 0
d12 + s12*C >= 0
d21 + s21*C >= 0
0 <= xi <= 1 , continuous
0 <= wij, sij <= 1, integer
目标函数符合预期:
MAXIMIZE
-1*s_12 + 1*s_21 + 1*w_12 + -1*w_21 + 0
解决方案符合预期:
('d_12', '= ', 0.0)
('d_21', '= ', 0.0)
('s_12', '= ', 0.0)
('s_21', '= ', 1.0)
('w_12', '= ', 1.0)
('w_21', '= ', 0.0)
('x_1', '= ', 0.0)
('x_2', '= ', 0.0)
但是当我添加以下约束或仅添加其中之一时:
d12 - (1 - s12)*C < 0
d21 - (1 - s21)*C < 0
Python 将目标函数更改为:
MAXIMIZE
0*__dummy + False
SUBJECT TO
... omited
我不知道该怎么做,解决方案变得空洞:
('__dummy', '= ', None)
('d_12', '= ', 0.0)
('d_21', '= ', 0.0)
('s_12', '= ', 1.0)
('s_21', '= ', 1.0)
('w_12', '= ', 1.0)
('w_21', '= ', 1.0)
('x_1', '= ', 0.0)
('x_2', '= ', 0.0)
最佳答案
我没有分析你的限制,但这里有一些关于可能存在什么样的问题的评论。
您正在使用它来定义约束:
d12 - (1 - s12)*C < 0
- 在线性规划中,仅存在
<=
形式的不等式。和>=
(==
可以由这些构建;忽略数值困难);其他一切都不自然(在数学方面没有多大意义) - pulp-or仅定义上面提到的运算符;但不是
<
和>
link; scroll to bottom; also see next image from the docs
Pulp 对于库的错误使用并不那么稳健,并且当添加一些格式错误的约束时,通常会默默地覆盖目标(这里可能就是这种情况)。也许你会在 PuLP 的issue-tracker中找到类似的经验。
考虑使用约束类而不是使用重载运算符。
关于python - 整数线性规划程序的行为不符合预期,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40143661/