Using Python to Solve Computationally Hard Problems

Location: D135 Audience level: Intermediate
Average rating: **...
(2.67, 9 ratings)

The Traveling Salesman Problem, an example of an NP-Complete task that is much more difficult than it seems on the surface, can be used to model such tasks as Printed Circuit Board design, job sequencing, and aircraft routing. This session will use the TSP to demonstrate Python’s capabilities in mathematical computation.

First, we will select a few of the algorithms available for solving it. We will then examine options within Python for implementing them, and discuss what makes a given solution best for the specific algorithm. Evaluation criteria will include runtime and the quality of the solution given.

An in-depth examination of the process of researching algorithms will be presented in the earlier session, Finding the Right Algorithm for the Job: Math Research for Non-Mathematicians.

Rachael Madsen

Optimal Design Software LLC

Rachael has been using her mathematics degree in software development for more than 35 years. Her experience ranges from compiler design to terminal and computer emulation software, from database design and administration to medical diagnostic software, from nationwide order management and inventory control to workflow management for a web-based business. In the process, Rachael has helped many people understand the advantages of using mathematics in their software designs.

Comments on this page are now closed.


Picture of Alex Martelli
Alex Martelli
07/19/2012 9:23am PDT

good materials, presentation unfortunately not quite as smooth (maybe the lack of the “right algorithm for the job” earlier talk hampered the presentation flow a bit).


For information on exhibition and sponsorship opportunities at the conference, contact Sharon Cordesse at (707) 827-7065 or

View a complete list of OSCON contacts