Solve TSP instances to optimality.
Project description
Download the TSP instances.
Extract them and put them in a folder called tsp
.
When installed into your environment (for example using Poetry), you can do:
tisp <path to tsp .dat>
Alternatively, when using it as a library, you can do:
from tisp import cli
cli()
Then run the script. By default it looks for the gr48
instance.
To run a specific instance, do (the path is interpreted relatively):
from tisp import solve_from_path
solve_from_path("gr96.dat")
Or, when you have an instance already loaded, with the costs a simple cost matrix of type list[list[float]]
:
from tisp import do_branch_and_bound
# inst = ... load instance here
do_branch_and_bound(inst)
It only works for fully connected instances. An example is:
3
0 20 5
20 0 3
5 3 0
"3" is the size of the instance, the rest indicates the cost of edge (i, j), where i is the row and j the column.
Supports Python up to 3.11. Uses mip as the underlying LP solving library. By default it uses included CBC binaries.
Performance
The main peformance bottleneck is the computation of the min cut to find the constraint to be added to the LP, although for larger instances solving the LP's also takes significant time.
On my 5-year old laptop, gr48
takes under 10 seconds. Computing it directly as an LP with a solver can take 30-50 seconds. For larger instances, this solver performs even better.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file tisp-0.1.1.tar.gz
.
File metadata
- Download URL: tisp-0.1.1.tar.gz
- Upload date:
- Size: 14.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.11.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb69bfcbdd17bcf7348123055373fcc6be6aef5cdbf4a856dfb7705ead59cd59 |
|
MD5 | 9ca038953a8ffcfa85e46a59469bce39 |
|
BLAKE2b-256 | f0bee70922f3ca4c847d4e893122c0ad715dcbccd1cc104dc7549ed5fc6b7b4f |
File details
Details for the file tisp-0.1.1-py3-none-any.whl
.
File metadata
- Download URL: tisp-0.1.1-py3-none-any.whl
- Upload date:
- Size: 19.2 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.11.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90f7ea3c8d5234170457eafeffb4c7d114ba03a2ab5b70043559b1e3f217b6ea |
|
MD5 | 90d5c077165ea8279debc06e9b59ff65 |
|
BLAKE2b-256 | ad54a7d3af015e37ed49508ba25c77c6fe8d418c1be375d31ea41a159fd03d7c |