PuLP挂在不可行整数LP问题上

Question

我有一个循环，它使用PuLP解决了大量整数LP问题。在某个时刻，它会遇到类似2a + 2b = 1的东西。这显然是不可行的，但是PuLP只是挂在这个输入上。

我尝试过使用CBC来解决这个问题，它会立即返回正确的结果——不可行或无边界。所以这不是加拿大广播公司的问题。

这是重现问题的代码：

from pulp import *
a = LpVariable('a', cat=LpInteger)
b = LpVariable('b', cat=LpInteger)
prob = LpProblem()
prob += 2*a + 2*b == 1
prob.solve(solver=PULP_CBC_CMD())
print(prob.status)

Answer 1

问题不是来自PuLP(PuLP是一个建模库(，而是来自CBC求解器。

我得到的输出示例：

...
Cbc0010I After 35000 nodes, 30979 on tree, 1e+50 best solution, best possible 0 (666.85 seconds)
Cbc0010I After 36000 nodes, 31979 on tree, 1e+50 best solution, best possible 0 (691.99 seconds)
Cbc0010I After 37000 nodes, 32979 on tree, 1e+50 best solution, best possible 0 (717.61 seconds)
Cbc0010I After 38000 nodes, 33977 on tree, 1e+50 best solution, best possible 0 (742.93 seconds)
...

1e+50作为最佳解意味着在分支树中没有找到可行点(没有现任点(
然而，它继续分支。

对于我尝试过的其他解算器，答案是立竿见影的。

GLPK

GLPK Integer Optimizer, v4.60
1 row, 3 columns, 2 non-zeros
2 integer variables, none of which are binary
Preprocessing...
1 row, 0 columns, 0 non-zeros
0 integer variables, none of which are binary
Scaling...
A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Solving LP relaxation...
GLPK Simplex Optimizer, v4.60
1 row, 0 columns, 0 non-zeros
~     0: obj =   0.000000000e+00  infeas =  1.000e+00
PROBLEM HAS NO FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.0 Mb (40416 bytes)

CPLEX

Presolve time = 0.00 sec. (0.00 ticks)
Root node processing (before b&c):
Real time             =    0.00 sec. (0.00 ticks)
Parallel b&c, 4 threads:
Real time             =    0.00 sec. (0.00 ticks)
Sync time (average)   =    0.00 sec.
Wait time (average)   =    0.00 sec.
------------
Total (root+branch&cut) =    0.00 sec. (0.00 ticks)

MIP - Integer infeasible.
Current MIP best bound =  0.0000000000e+00 (gap is infinite)
Solution time =    0.00 sec.  Iterations = 0  Nodes = 0
Deterministic time = 0.00 ticks  (2.89 ticks/sec)

GUROBI

OBJ: 1 rows, 3 columns, 2 nonzeros
Optimize a model with 1 rows, 3 columns and 2 nonzeros
Variable types: 1 continuous, 2 integer (0 binary)
Coefficient statistics:
Matrix range     [2e+00, 2e+00]
Objective range  [1e+00, 1e+00]
Bounds range     [0e+00, 0e+00]
RHS range        [1e+00, 1e+00]
Presolve removed 0 rows and 2 columns
Presolve time: 0.00s
Solution count 0
Model is infeasible