|
|
 |
|
Jeudi 2 Juillet
| Heure: |
12:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Solving the quadratic shortest path problem |
| Description: |
Borzou Rostami Finding the shortest path in a directed graph is one of the
most important combinatorial optimization problems, having applications
in a wide range of fields. In its basic version, however, the problem
fails to represent situations in which the value of the objective function
is determined not only by the choice of each single arc, but also
by the combined presence of pairs of arcs in the solution. In this paper
we model these situations as a Quadratic Shortest Path Problem, which
calls for the minimization of a quadratic objective function subject to
shortest-path constraints. We prove strong NP-hardness of the problem
and analyze polynomially solvable special cases, obtained by restricting
the distance of arc pairs in the graph that appear jointly in a quadratic
monomial of the objective function. Based on this special case and problem
structure, we devise fast lower bounding procedures for the general
problem and show computationally that they clearly outperform other
approaches proposed in the literature in terms of their strength. |
|
|
