Реализация ветвей и границ для TSP в Java

Question

Интересно, есть ли полезная реализация Java алгоритма Branch And Bound для TSP или вообще платформы OR, которая включает BnB для TSP.

Спасибо за вашу помощь!* Marco

Answer 1

BnB обычно взаимодействует с complete решателем подзадач:

best_cost_soln_so_far = +inf
while (better_cost_soln = search_for_soln_cheaper_than(best_cost_soln_so_far))
{
    best_cost_soln_so_far = better_cost_soln
    backtrack_into_search
}

То есть, ваш поиск подзадачи будет возвращаться, когда стоимость любого частичного решения, которое он исследует, превышаетграница, установленная best_cost_soln_so_far.Если поиск подзадачи действительно находит лучшее решение, best_cost_soln_so_far обновляется, и поиск продолжается с того места, на котором он остановился, в поисках еще лучшего решения.Это довольно легко реализовать.

Тем не менее, я очень сомневаюсь, что вы хотите заняться большими TSP с помощью полного поиска из-за огромного пространства поиска;Вы можете добиться большего успеха с помощью приблизительных методов, таких как имитация отжига.

Answer 2

OptaPlanner (с открытым исходным кодом, Java) имеет реализацию Branch and Bound. См. Раздел документации, посвященный BaB. Реализация алгоритма начинается с этого класса , но это трудно понять.

В нем также есть пример TSP: хотяпо умолчанию не настроен с BaB, это легко сделать, настроив tspSolverConfig.xml следующим образом:

<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

Существуют дополнительные необязательные параметры для управления сортировкой узлов, способом исследования узлов и т. д.

Answer 3

Я нашел этот PDF. Это очень полезно и имеет подробный пример и реализацию java для Branch и bound для TSP Вот ссылка на файл

Answer 4

Хотя все мы знаем, что "Java и Javascript похожи, как Car и Carpet похожи" , я бы рекомендовал взглянуть на SimplexJS , который является простым линейным и MIP-решателем, написанным на Javascript. Так как он небольшой (менее 400 LOC), его можно легко перевести на Java. У автора проекта также есть хороший пример Решения TSP с целочисленным программированием .