441. LP relaxations for the elementary shortest path problem
Invited abstract in session TB-13: Numerical Methods and Applications I, stream Numerical Methods and Applications.
Tuesday, 10:30-12:30Room: B100/6009
Authors (first author is the speaker)
| 1. | Regina Schmidt
|
| University of Augsburg | |
| 2. | Mirjam Duer
|
| Augsburg University |
Abstract
The Elementary Shortest Path Problem (ESPP) is the problem of finding an elementary minimum-cost path between two nodes in a directed graph in such a way that each node on the path is visited exactly once. If negative arc costs are allowed, then the problem is NP-hard. We study an exact integer programming formulation for the ESPP and we discuss its LP relaxations. We present a solution approach based on these relaxations.
Keywords
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers