Ta Anh Son, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao: "Solving QoS Routing Problems by DCA".

Abstract: The Quality of Service (QoS) routing emphasizes to find paths from source to destination satisfying the QoS requirements. In this paper, we consider the five problems in QoS Routing called the MCP (Multi-Constrained Path) and the MCOP (Multi-Constrained Optimal Path). They are all NP-hard problems. We first formulate them as Binary Integer Linear Programs (BILP) and then investigate a new solution method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results show that the proposed algorithm is promising: it is more robust than CPLEX, the best solver for BILP.

Keywords: Multi-Constrained Path, Multi-Constrained Optimal Path, QoS routing, DC programming, DC Algorithm, Exact Penalty, Binary Integer Linear Programming (BILP).

Citation: Ta Anh Son, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao: Solving QoS Routing Problems by DCA, in “Intelligent Information and Database Systems”, Lecture Notes in Artificial Intelligence (LNAI), volume 5991, pp. 460-470, Springer Verlag 2010.