Visitors :
Title : Tabu-NG: hybridization of constraint programming and local search for solving CSP
Abstract: A very large number of combinatorial problems belong to the family of Constraint Satisfaction Problems (CSP): configuration, planning, scheduling, resource allocation... These problems share a common description that generally allows a clear and intuitive modeling. In this thesis, we proposed and studied a new hybrid method for solving CSPs. We named this method Tabu-NG for Tabu Search based on NoGood. The name is a bit simplistic because it is a hybrid of filtering algorithm, constraint propagation, Tabu Search and nogood management. The method was applied to two types of problems. The first is the Frequency Assignment Problem (FAP) in military radio networks, particularly the problems proposed from 1993 (benchmarks of the European project CALMA) until 2010 (benchmarks of a DGA project). The second is the academic problem of k-coloring of graphs on the DIMACS instances. The method has improved some high scores currently known. In both problems we dealt with unary and binary constraints, and also with n-ary constraints and function optimization under constraints for FAP. The principles of Tabu-NG are general and can be applied to other CSPs. It can also accommodate specific heuristics to problems, we practiced it on the problems cited, and in this sense we believe we can qualify the method as metaheuristic without abusing this definition.
Under a contract with the General Delegation of Army “DGA” on a call for national project, I adapted my proposed hybrid method for solving frequency Assignment Problems in military networks. The main difficulties we encountered are related to the large size of the problems treated (240 test cases of real dimension) and the multitude of constraints and objectives to satisfy. The project is closed, and the method I have developed has shown very good performance on all benchmarks provided by the DGA .
Participation in the Project:
. Conception of the theoretical part (conception of the resolution method).
. Design / Development of data structures.
. Software Development.
. Testing and validation on different provided benchmarks.
. Ensuring the quality of the software. (memory leak, clean code, etc ...)
. Writing documents.
. Exchange with the DGA groups during the project.
. Attending all meetings (Belfort, Paris and Rennes).
International Conferences
1. M. DIB, R. Abdallah; A. Caminada, 2010. Arc-consistency in Constraint Satisfaction Problems: A survey, 2nd International Conference on Computational Intelligence, Modelling and Simulation Bali, Indonesia, 28–30 September 2010.
2. M. DIB, A. Caminada, H. Mabed. Frequency management in Radio military Networks. The 10th INFORMS Telecommunications Conference, Concordia University (CANADA) , May 5 - 7, 2010
3. M. DIB, A. Caminada, H. Mabed. A New Method to Solve and Optimize FAP with N-ary Constraints. 8th International Conference of Modeling and Simulation - MOSIM’10 - May 10-12, 2010 - Hammamet - Tunisia.
4. M. DIB, A. Caminada, H. Mabed. MinOrder optimization in FAP with NoGood-Tabu Search. 39th International Conference on Computers & Industrial Engineering (CIE39), Troyes France, July 6-8, 2009.
5. M. DIB, A. Caminada, H. Mabed. A fast Algorithm to solve frequency assignment problem. 6th international conference on Integration of Artificial Intelligence and Operations Research techniques in Constraint Programming for Combinatorial Optimization Problems, Pittsburgh USA, May 27-31, LNCS Springer, 2009.
6. M. DIB, A. Caminada, H. Mabed. Nogood Recording with Tabu Search for CSP (Application to FAP). Third Asia International Conference on Modelling & Simulation, 25-26 May, Indonesia - Bali, IEEE, 2009.
7. M. DIB, A. Caminada, H. Mabed. Constraint Propagation with Tabu List for Min-Span Frequency Assignment Problem. 2nd international conference on Modelling, Computation and Optimization in Information Systems and Management Sciences MCO2008, Springer CCIS, CCIS14, pp. 97-106, 2008.
National Conferences
1. M. DIB, A. Caminada. H. Mabed, Renforcement des contraintes n-aires en binaires dans un FAP. 11ème conférence ROADEF’10, 24-26 février, Toulouse, 2010.
2. M. DIB, I. Devarenne, H. Mabed, A. Caminada. Etude comparative de recherche locale et de propagation de contraintes en CSP n-aire. 10ème conférence ROADEF’09, 10-12 février, Nancy, 2009.
3. J. HU, M. DIB, A. Caminada, H. Mabed, Recherche de zone de blocage dans un graphe. 10ème conférence ROADEF’09, 10-12 février, Nancy, 2009.
4. M. DIB, A. Caminada, H. Mabed. Propagation de Contraintes avec une liste Tabou pour le CSP. JFPC2008, PP. 409 – 413, 2008.
5. M. DIB, A. Caminada, H. Mabed, J. Hu. Propagation de contraintes et gestion de Nogood pour le CSP. 9ème conférence ROADEF’08, 25-27 février, Clermont, 2008.
