SCIP-Jack дает неправильное решение Штейнера для Дерева при включенных сокращениях - PullRequest
Новая
       8

SCIP-Jack дает неправильное решение Штейнера для Дерева при включенных сокращениях

1 голос
/ 09 апреля 2019

При запуске 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 / сокращение = 2). 

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

1 Ответ

1 голос
/ 10 апреля 2019

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

...