Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

tisp-0.1.1.tar.gz (14.7 kB view details)

Uploaded Source

Built Distribution

tisp-0.1.1-py3-none-any.whl (19.2 kB view details)

Uploaded Python 3

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

Hashes for tisp-0.1.1.tar.gz
Algorithm Hash digest
SHA256 fb69bfcbdd17bcf7348123055373fcc6be6aef5cdbf4a856dfb7705ead59cd59
MD5 9ca038953a8ffcfa85e46a59469bce39
BLAKE2b-256 f0bee70922f3ca4c847d4e893122c0ad715dcbccd1cc104dc7549ed5fc6b7b4f

See more details on using hashes here.

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

Hashes for tisp-0.1.1-py3-none-any.whl
Algorithm Hash digest
SHA256 90f7ea3c8d5234170457eafeffb4c7d114ba03a2ab5b70043559b1e3f217b6ea
MD5 90d5c077165ea8279debc06e9b59ff65
BLAKE2b-256 ad54a7d3af015e37ed49508ba25c77c6fe8d418c1be375d31ea41a159fd03d7c

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page