PuLP зависает от неразрешимой целочисленной задачи LP - PullRequest
Новая
       21

PuLP зависает от неразрешимой целочисленной задачи LP

0 голосов
/ 31 октября 2019

У меня есть цикл, который решает большое количество целочисленных задач LP, используя PuLP. В какой-то момент он сталкивается с чем-то вроде 2a + 2b = 1. Это, очевидно, недостижимо, и все же PuLP просто зависает на этом входе.

Я пытался решить эту проблему с помощью CBC, и он мгновенно возвращает правильный результат - неосуществимый или неограниченный. Так что это не проблема с 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)

1 Ответ

0 голосов
/ 09 ноября 2019

Проблема не в 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)

ГУРОБИ 

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
...