Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Speed up the traveling_salesman_problem method #23842

Closed
dcoudert opened this issue Sep 12, 2017 · 7 comments
Closed

Speed up the traveling_salesman_problem method #23842

dcoudert opened this issue Sep 12, 2017 · 7 comments
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-8.1

Comments

@dcoudert
Copy link
Contributor

The constraint generation formulation of the traveling_salesman_problem method adds a single edge-cut constraints per round (only for one connected component of the graph of selected edges). With this patch, we add all the constraints we can (one per connected component).

Before

sage: G = graphs.Grid2dGraph(10,10)
sage: %timeit G.traveling_salesman_problem()
10 loops, best of 3: 89.8 ms per loop

After

sage: G = graphs.Grid2dGraph(10,10)
sage: %timeit G.traveling_salesman_problem()
10 loops, best of 3: 40 ms per loop

Component: graph theory

Author: David Coudert

Branch/Commit: 3be0593

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/23842
@dcoudert dcoudert added this to the sage-8.1 milestone Sep 12, 2017
@dcoudert
Copy link
Contributor Author

Commit: 3be0593

@dcoudert
Copy link
Contributor Author

Branch: u/dcoudert/23842

@dcoudert
Copy link
Contributor Author

New commits:

3be0593trac #23842: add more constraints in TSP

@tscrim
Copy link
Collaborator

tscrim commented Sep 15, 2017

comment:2

LGTM.

@tscrim
Copy link
Collaborator

tscrim commented Sep 15, 2017

Reviewer: Travis Scrimshaw

@dcoudert
Copy link
Contributor Author

comment:3

Thank you.

@vbraun
Copy link
Member

vbraun commented Sep 18, 2017

Changed branch from u/dcoudert/23842 to 3be0593

@vbraun vbraun closed this as completed in 2706da5 Sep 18, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-8.1
Development

No branches or pull requests
3 participants
@vbraun @tscrim @dcoudert