Improved Exact Resolution of Multi-Constrained Path Problem

Khallef Walid 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.
Type de document :
Communication dans un congrès
EURO: European Conference on Operational Research, Jul 2015, Glasgow, United Kingdom. 2015, 27th European Conference on Operational Research (EURO2015). 〈http://euro2015.euro-online.org/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01229422
Contributeur : Sylvain Durand <>
Soumis le : lundi 16 novembre 2015 - 16:01:39
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-01229422, version 1

Collections

Citation

Khallef Walid, 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. 2015, 27th European Conference on Operational Research (EURO2015). 〈http://euro2015.euro-online.org/〉. 〈lirmm-01229422〉

Partager

Métriques

Consultations de la notice

120