Skip to Main content Skip to Navigation
Conference papers

Improved Exact Resolution of Multi-Constrained Path Problem

Walid Khallef 1 Sylvain Durand 1, 2 Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Several challenging issues exist in quality-of-service (QoS) provisioning in networks, and the QoS constrained routing is one of the most important issues. The QoS routing from a source to a destination leads to the well known multi-constrained path problem (MCP). The objective of MCP is to find a feasible path with respect to a set of QoS constraints. Since this problem is NP-complete, the solutions proposed in the literature are either time-consuming, or do not guarantee to find a solution even if the problem is feasible. Some of the most efficient algorithms proposed by Kuipers and al. are SAMCRA (exact resolution) and TAMCRA (heuristic). Based on the same ideas (using a Dijkstra-like search with a non-linear function and a reduction of the space search by non-dominance principle), we propose an exact algorithm, that manipulates the constraints to improve significantly the computation time. For hard instances, the results are similar to SAMCRA, but for easier instances, reinforcing the constraints leads to reduce the space search with a high probability of finding a solution. In some cases the algorithm memorized 40% less non-dominated paths than SAMCRA. We then show how, in specific cases, the solution can be improved by using a more flexible structure than paths.
Complete list of metadatas
Contributor : Sylvain Durand <>
Submitted on : Monday, November 16, 2015 - 4:01:39 PM
Last modification on : Wednesday, October 14, 2020 - 4:04:14 AM


  • HAL Id : lirmm-01229422, version 1


Walid Khallef, Sylvain Durand, Miklós Molnár. Improved Exact Resolution of Multi-Constrained Path Problem. EURO: European Conference on Operational Research, Jul 2015, Glasgow, United Kingdom. ⟨lirmm-01229422⟩



Record views