- Thursday, February 9, 2023
- 3:00 PM–4:00 PM
- NH 276
The Mathematics and Statistics Department Colloquium on Thursday, February 9 will feature Dr. Stephen Dirkse.
You are invited to join with fellow students and professors at the February 9 Mathematics and Statistics Colloquium. Join us in NH 276 for light refreshments at 3:00 and a fascinating lecture at 3:10.
Speaker: Dr. Steven Dirkse, GAMS Corporation
Title: Better Decisions, Better Outcomes, and the Traveling Salesman
Abstract: Recent events have illustrated the importance of making better decisions. These decisions correspond to solutions of problems that are potentially very difficult to solve (even NP-complete), but methods exist that allow nearly- or fully-optimal solutions in practice. In this talk, we outline a theoretically sound and computationally successful framework for effectively (and sometimes only approximately) solving very large TSP instances via linear programming, duality, and cutting planes. Don’t worry, these concepts will be introduced and familiarity with them is not assumed. Computational results obtained using these techniques will be presented, with some long tours visualized. While interesting in their own right, the techniques presented also illustrate a common motif in algorithm design: replacing a difficult problem with a more tractable one and iteratively modifying/strengthening the substitute until the desired solution is obtained.
Location details
North Hall 276
