Блог

При запуске SCIP-Jack (приложения STP) для конкретного экземпляра проблемы древовидности Штайнера выходной файл журнала не содержит допустимого решения, если значение stp / reduction равно 1 или 2.

Мне интересно, правильно ли отформатирован мой файл, содержит ли мой график ошибки или сокращения применены неправильно.

Мой график был построен на python с использованием NetworkX. Я проверяю, доступно ли каждое ребро из корневого узла, и всегда присваиваю как дуге, так и антипараллельной дуге вес. Тип проблемы также устанавливается на «SAP». Большинство ребер являются двунаправленными и, следовательно, имеют одинаковый вес в обоих направлениях.

Мой входной файл выглядит следующим образом

 33D32945 STP File, STP Format Version 1.0
SECTION Comment
Problem "SAP"
END

SECTION Graph
Nodes 49
Edges 62
A 23 47 289.36 10000000000
A 27 44 297.37 10000000000
A 29 46 295.36 10000000000
A 32 48 294.02 10000000000
A 34 45 295.66 10000000000
A 1 2 0.0 0.0
A 1 6 0.0 0.0
A 2 37 12.24 12.24
A 2 38 4.82 4.82
A 3 4 0.0 0.0
A 3 5 0.0 0.0
A 3 22 382.56 382.56
A 3 41 367.16 367.16
A 3 42 15.51 15.51
A 5 6 0.0 0.0
A 5 37 274.53 274.53
A 5 41 176.09 176.09
A 5 49 0 0
A 7 8 338.24 338.24
A 7 9 65.86 65.86
A 7 43 97.23 97.23
A 8 40 46.79 46.79
A 9 10 573.38 573.38
A 10 11 162.1 162.1
A 11 12 729.19 729.19
A 12 13 3.23 3.23
A 13 14 136.91 136.91
A 13 28 818.47 818.47
A 14 15 184.65 184.65
A 15 16 2.03 2.03
A 15 30 818.4 818.4
A 16 17 20.2 20.2
A 17 18 2023.02 2023.02
A 17 31 818.4 818.4
A 18 19 1465.78 1465.78
A 18 33 817.96 817.96
A 19 20 3.54 3.54
A 20 21 13.11 13.11
A 20 35 817.71 817.71
A 21 22 3.55 3.55
A 22 36 817.7 817.7
A 23 24 452.58 452.58
A 23 25 96.21 96.21
A 25 26 319.98 319.98
A 25 40 779.27 779.27
A 26 27 709.62 709.62
A 26 43 726.02 726.02
A 27 28 852.76 852.76
A 28 29 328.06 328.06
A 29 30 30.42 30.42
A 30 31 40.42 40.42
A 31 32 1280.36 1280.36
A 32 33 742.84 742.84
A 33 34 482.5 482.5
A 34 35 986.65 986.65
A 35 36 16.66 16.66
A 36 37 398.31 398.31
A 38 39 3.14 3.14
A 38 41 450.94 450.94
A 40 43 342.61 342.61
A 41 42 366.82 366.82
END

SECTION Terminals
Terminals 6
Root 49
T 44
T 45
T 46
T 47
T 48
T 49
END

EOF
  

Я бы ожидал, что решение будет иметь не менее 10 ребер, чтобы соединить все. Однако сообщаемое решение выглядит следующим образом (с stp / reduction = 2).

 SECTION Finalsolution
Vertices 2
V 5
V 49
Edges 1
E 5 49
End
  

Такое поведение вызвано ошибкой в SCIP-Jack; К сожалению, SCIP-Jack не очень хорошо протестирован для SAP (из-за отсутствия тестовых экземпляров). Это будет исправлено в рамках следующего выпуска исправления ошибок. Пожалуйста, свяжитесь со мной (Даниэль Рефельдт), если вы хотите уже иметь исправленную версию.