Improved Exact Resolution of Multi-Constrained Path Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2015

Improved Exact Resolution of Multi-Constrained Path Problem

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.
No file

Dates and versions

lirmm-01229422 , version 1 (16-11-2015)

Identifiers

  • HAL Id : lirmm-01229422 , version 1

Cite

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⟩
167 View
0 Download

Share

More