Developed by Dominik Krupke and Barak Ugav at Tel Aviv University. Further development at TU Braunschweig with Michael Perk.
⚠️ This is work in progress. The code is not yet ready for production use and can lead to wrong results with some parameters. We are planning to continue our work on this solver, soon. Please contact Dominik Krupke for more information.
The Close-Enough Traveling Salesman Problem asks for the shortest tour that visits a given set of circles. It is related to the classical Traveling Salesman Problem but more challenging as the distances between two successive cities are not constant. The problem is NP-hard, and thus, very challenging to solve to optimality. We provide an algorithm implementation that is capable of solving reasonably sized instances to provable optimality within seconds to minutes. Depending on the character of the instance, the solvable instance size is between 20 to multiple hundred circles.
The implementation is a Branch and Bound algorithm making use of a Second Order Cone Program, building on the work of Coutinho et al..
Primary differences are:
- A highly modular implementation and availability of many search and branching strategies.
- Warm starts with initial solutions provided by heuristics.
- Callbacks allowing to lazy constraints, custom heuristics, and generally heavily influencing the search.
- Parallelization of the search.
- New pruning rules based on geometric insights that can give significant speed-ups.
- Branching degree reduction giving further exponential speed-ups in some cases.
You need a properly installed Gurobi-license for this package, as we need a highly optimized SOCP-solver. You can easily get a free license for academic purposes. The free non-academic license is probably not sufficient and will lead to errors.
(CGAL does not require you to install a license, but you would need to buy one for commercial usage)
You can just check out this repository and run
pip install .
or, without checking it out
pip install git+https://github.com/d-krupke/close-enough-tsp
You can test the installation (if you checked out the repository) via
pytest -s tests
- Copy code into subfolder.
- Install conan dependencies.
- Add subfolder via
add_subdirectory
to your CMakeList.txt
TODO: Write a conan setup file to allow easy installation via conan.
A simple usage could look like this
from cetsp_bnb2.core import Circle, Instance, optimize, Point, plot_solution
# create some instance
instance = Instance([Circle(Point(x, y), 0) for x in range(0, 4) for y in range(0, 5)])
# solve instance
solution = optimize(instance)
# access and plot solution
import matplotlib.pyplot as plt
plt.figure()
plot_solution(plt.gca(), instance, tour)
You can also access the solver directly via C++.
TBD
This Branch and Bound algorithm is an improved version of this paper.
This master thesis provides a good overview over the previous work and provides an LNS-algorithm (highly effective and modern heuristic, probably the most important heuristic out there for hard problems, even if barely teached).
This paper uses a GTSP-MIP for solving the CE-TSP. The reduction techniques and geometric observations may be intersting for us.
The branch and bound algorithm can be easily modified by replacing strategies. There are three primary strategies:
include/cetsp/details/root_node_strategy.h
The root node strategy decides the initial relaxed solution. It should allow to build an optimal solution. We currently have two different ones
- LongestEdgeFarthestCircle: The classical idea also used in previous work that starts with a longest edge and additionally the farthest circle. Thus, the initial tour is a triangle. For paths it is just the farthest circle to source and target of the path.
- ConvexHull: Start with the simplified convex hull. This is needed to do the convex hull pruning.
include/cetsp/strategies/branching_strategy.h
The branching strategy decides how to split the solution space of a node further.
For classical MIP-solver, this usually requires to select a fractional variable
and rounding it up or down, essentially splitting the solution space into two
parts. For our problem, the branching is easier on selecting what to branch (
try to include the farthest circle in some position as this drives up to
lower bound the most), but the split is much larger as we have to consider
inserting a missing circle anywhere in the sequence. A lot of the resulting
sequences allow arguments why they cannot lead to an optimal solution, and thus
can be pruned, without doing the costly trajectory computation. We allow the
addition of rules
to improve the performance of the branching.
The branching also triggers the computation of the newly generated children in parallel to utilize the CPU better. This is not the perfect place for parallelization but the easiest, as it can easily be synchronized while still having big impact for the more complicated instances.
A further point here is simplification: We can shorten the sequence and thus the potential number of branches by only keeping the spanning circles in the sequence. Removing implicitly covered circles does not lower the costs.
We have the following branching strategies:
- FarthestCircle: Just tries to branch on the farthest circle. Allows the addition of further rules.
- ChFarthestCircle: Extension of the previous strategy by a rule that makes sure each sequence follows the convex hull, which can be proved to be optimal.
- RandomCircle: Just tries to branch on a random (uncovered) circle.
Further ideas:
- Add a rule that directly excludes all sequences that can be lower bounded above the current best solution, without computing the trajectory. We can take the parent's trajectory, remove the maximal cost of the edge on which we want to add a further circle, and then add the minimal cost of traveling to this circle. If it is already higher, we do not have to compute its trajectory.
- The convex hull idea can probably be extended recursively.
include/cetsp/strategies/rule.h
You can easily define a new rule to directly exclude any suboptimal branches, if you can find an argument that does not require computing the trajectory. If you need the trajectory, use a callback and then prune in it. This way, the trajectory will be cached.
include/cetsp/details/search_strategy.h
Which leaf of the branch and bound tree should be investigated next?
- Depth First: This strategy always goes into the best child of the current node. This helps to find good feasible solutions quickly.
- Breadth First: Always uses the cheapest leaf, which improves the lower bound but will take a long time to find a feasible solution.
- Mixed: Will do depth first until the node gets pruned or becomes feasible. Then it will look for the cheapest leaf. This is a popular technique used by modern MILP-solvers.
TBD
- The convex hull enforces quite a lot of order into partial solutions. This yields quite some speed ups for important instances in our context.
- Improved Branching of switching between depth (going deeper until feasible) and breadth first (continue on cheapest partial solution).
- Simplifying branch sequences by removing hitting points that do not span the trajectory. This reduces the exponential branching factor, but can also make it more difficult to find feasible solutions.
- Allowing lazy constraints, which are important for the use as coverage path plannning routine.
You can try out new ideas on the lower bound (biggest issue) using this simple python interface.
# import the stuff
from cetsp_bnb2.core import (
Circle,
Instance,
compute_tour_by_2opt,
branch_and_bound,
Point,
plot_solution,
)
import random
circles = [
Circle(Point(x * (1 + random.random()), y * (1 + random.random())), 1)
for x in range(7)
for y in range(7)
]
instance = Instance(circles)
# trigger_lazy_computation an initial solution via 2opt
initial_solution = compute_tour_by_2opt(instance)
def cb(context):
relaxed_sol = context.get_relaxed_solution()
for c in circles:
dist = relaxed_sol.distance(c)
if dist > 0:
# this may not really be a lower bound.
context.current_node.add_lower_bound(relaxed_sol.length() + dist)
timelimit = 60
opt_solution = branch_and_bound(instance, cb, initial_solution, timelimit)
# plot
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 10))
plot_solution(plt.gca(), instance, opt_solution)
plt.show()
Please follow the following project structure. It is carefully designed and follows common guidelines. It uses Scikit-HEP developer information as baseline.
cmake
Should contain all cmake utilities (no cmake package manager, so copy&paste)include
Public interfaces of C++-libraries you write. Should followinclude/libname/header.h
pysrc
Python packages you write. Should be of the shapepysrc/package_name/module_name/file.py
. Can be recursive.src
Your implementation internals. Can also contain header files that are not part of the public interface!tests
Your tests for C++ and Python. Read also this..clang_format
(C&P) C++-formatting rules, so we have a common standard.- Needs to be edited if: You want a different C++-coding style.
.flake8
(C&P) Python checking rules- Needs to be edited if: The rules do not fit your project. Especially, if there are too many false positives of some rule.
.gitignore
(C&P) Automatically ignore system specific files- Needs to be edited if: You use some uncommon tool that creates some kind of artifacts not covered by the current rules.
pyproject.toml
(C&P) Tells pip the dependencies for runningsetup.py
.- Needs to be edited if: You use additional/different packages in
setup.py
- Needs to be edited if: You use additional/different packages in
.pre-commit-config.yaml
(C&P) For applying a set of checks locally. Run, e.g., viapre-commit run --all-files
.- Needs to be edited if: Better tools appear you would like to use, like a better
black
etc.
- Needs to be edited if: Better tools appear you would like to use, like a better
CMakeLists.txt
Defines your C++-project. This is a complex topic we won't dive into here. You should know the basics of CMake to continue.conanfile.txt
Defines the C++-dependencies installed via conan (use CPM within CMakeLists.txt for copy&paste dependencies).- Needs to be edited if: You change C++-dependencies.
MANIFEST.in
(C&P) Defines all the files that need to be packaged for pip.- Needs to be edited if: You need some files included that do not fit the basic coding files, e.g., images.
setup.py
Scripts for building and installing the package.- Needs to be edited if: You add dependencies, rename the project, want to change metadata, change the project structure, etc.
- If you don't have any CPP-components yet, you need to set the target to None!
requirements.txt
The recommended requirements for development on this package- Needs to be edited if: You are using further python packages.
We added a run_tests.sh
to quickly build the project and run some tests.
It should run on Linux and Mac OS without any further setup, but it will install the package into the current environment using pip.
You can also run the tests manually.
Just run pytest
to run the Python tests, after you installed the package.
For the C++-tests, you have to build the target doctests
.
If you run python3 setup.py build
, the conan-dependencies are automatically installed (otherwise you have to run conan install . --build=missing --output-folder=.conan -g CMakeDeps -g CMakeToolchain
).
Now we can use CMake to build our project, but we need to add -DCMAKE_TOOLCHAIN_FILE=.conan/conan_toolchain.cmake -DCMAKE_PREFIX_PATH=.conan
to include the conan dependencies.
conan install . --build=missing --output-folder=.conan -g CMakeDeps -g CMakeToolchain -s build_type=Debug
mkdir build
cmake . -DCMAKE_TOOLCHAIN_FILE=../.conan/conan_toolchain.cmake -DCMAKE_PREFIX_PATH=../.conan -DCMAKE_BUILD_TYPE=Debug -B build
cmake --build build --target doctests -- -j 12
./build/tests/doctests
Please report any further issues you encounter.
Probably, you have a bad Gurobi-license. We currently do not have a good way of checking that.
If you get an error such as
ImportError: /home/krupke/anaconda3/envs/mo310/bin/../lib/libstdc++.so.6: version `GLIBCXX_3.4.30' not found (required by /home/krupke/anaconda3/envs/mo310/lib/python3.10/site-packages/samplns/cds/_cds_bindings.cpython-310-x86_64-linux-gnu.so)
you are probably using conda (good!) but need to update glibcxx. Install the latest version by
conda install -c conda-forge libstdcxx-ng
This problem should be automatically fixed. Please open an issue if you still encounter it.
See https://docs.conan.io/1/howtos/manage_gcc_abi.html for more details.