Berlin 2018 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 10: Statistical Physics I (General)
DY 10.6: Talk
Monday, March 12, 2018, 11:30–11:45, BH-N 333
Linear Programming and Cutting Planes for Ground States and Excited States of the Traveling Salesperson Problem — •Hendrik Schawe1, Jitesh Jha2, and Alexander K. Hartmann1 — 1Institut für Physik, Carl von Ossietzky Universität Oldenburg — 2Manipal Institute of Technology
The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means that all NP problems, like spin glass groundstate, can be mapped to it.
We look at excited states to explore the energy landscape in detail. The linear programming approach offers capable tools to find excited states fulfilling very specific requirements. This allows us, e.g., to find the second shortest tour or the tour most different to the optimal tour within some allowed excitation є, e.g., 1% longer than the optimum. We are especially interested whether the energy landscape is complex, i.e., shows signatures of replica symmetry breaking in analogy to spin glasses.