Friday, April 15 2022

10:00am - 11:45am

10:00am - 11:45am

PhD Thesis Presentation

Cycle Cancelling Heuristics for The Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most studied problems in optimization. Since it is an NP-Hard problem, there exist several heuristics that find locally optimal solutions, as opposed to the globally optimal solution. We are interested in developing a new algorithm using a connection between Minimum Cost Flow Problems (MCF) and TSP.

MCF, which is a fundamental network flows problem, can be solved efficiently. A popular strategy, known as cycle-cancelling, can solve the MCF in strongly-polynomial time. In this project we study the advantages and disadvantages of cycle-cancelling algorithms in the context of the TSP. We identify scenarios in which a cycle-cancelling algorithm performs well or poorly on the TSP. Specifically, we study the properties that cycles must satisfy to retain a tour when cancelled and how to best deal with subtours that may arise through the cancellation of a general cycle. Practical implementations will lead to new heuristics for the TSP.

MCF, which is a fundamental network flows problem, can be solved efficiently. A popular strategy, known as cycle-cancelling, can solve the MCF in strongly-polynomial time. In this project we study the advantages and disadvantages of cycle-cancelling algorithms in the context of the TSP. We identify scenarios in which a cycle-cancelling algorithm performs well or poorly on the TSP. Specifically, we study the properties that cycles must satisfy to retain a tour when cancelled and how to best deal with subtours that may arise through the cancellation of a general cycle. Practical implementations will lead to new heuristics for the TSP.

Speaker: | Zach Soreson |

Affiliation: | |

Location: |

Done