Afin de couvrir les besoins liés au développement de son réseau, un opérateur français de téléphonie mobile doit périodiquement planifier l'achat et l'installation de nouveaux matériels, tout en respectant un ensemble de contraintes (contraintes obligatoires ou préférences hiérarchisées). Cet article présente la méthode, baptisée «constructive repair», utilisée pour résoudre ce problème dans les délais impartis (1 min de temps de calcul). Cette méthode répare le planning durant sa construction. Une suite de procédures de réparation est définie : si une réparation donnée ne peut aboutir sur une solution partielle, une réparation plus forte (relâchant éventuellement des contraintes plus importantes) est appelée. Nous avons testé notre méthode sur dix problèmes (aussi bien réels que spécifiquement conçus «à la main» pour ces tests). Nos solutions sont toutes au moins aussi bonnes que celles imaginées par l'ingénieur responsable de la planification.
To cope with its development, a French operator of mobile telephone network must periodically plan the purchase and the installation of new hardware, in such a way that a hierarchy of constraints (required and preferred) is satisfied. This paper presents the “constructive repair” method we used to solve this problem within the allowed computing time (1 min). This method repairs the planning during its construction. A sequence of repair procedures is defined: if a given repair cannot be achieved on a partial solution, a stronger repair (possibly relaxing more important constraints) is called upon. We tested our method on ten (both hand-made and real) problems. All our solutions were at least as good as thoses computed by hand by the engineer in charge with the planning.
@article{RO_2001__35_2_189_0,
author = {Boizumault, Patrice and David, Philippe and Djellab, Housni},
title = {Resource allocation in a mobile telephone network : a constructive repair algorithm},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {189--209},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
year = {2001},
mrnumber = {1868869},
zbl = {1014.90061},
language = {en},
url = {http://archive.numdam.org/item/RO_2001__35_2_189_0/}
}
TY - JOUR AU - Boizumault, Patrice AU - David, Philippe AU - Djellab, Housni TI - Resource allocation in a mobile telephone network : a constructive repair algorithm JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2001 SP - 189 EP - 209 VL - 35 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/item/RO_2001__35_2_189_0/ LA - en ID - RO_2001__35_2_189_0 ER -
%0 Journal Article %A Boizumault, Patrice %A David, Philippe %A Djellab, Housni %T Resource allocation in a mobile telephone network : a constructive repair algorithm %J RAIRO - Operations Research - Recherche Opérationnelle %D 2001 %P 189-209 %V 35 %N 2 %I EDP-Sciences %U http://archive.numdam.org/item/RO_2001__35_2_189_0/ %G en %F RO_2001__35_2_189_0
Boizumault, Patrice; David, Philippe; Djellab, Housni. Resource allocation in a mobile telephone network : a constructive repair algorithm. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 189-209. http://archive.numdam.org/item/RO_2001__35_2_189_0/
[1] ,, and, Constraint hierarchies and logic programming, in Proc. of ICLP'89. Lisbon, Portugal (1989) 149-164.
[2] , A constraint-based approach for examination timetabling using local repair techniques, Selected papers (extended version) from the Second International Conference on the Practice and Theory of Automated Timetabling (PATAT'97). Lecture Notes in Comput. Sci. 1408 (1998) 169-186.
[3] , and, Bounding the optimum of constraint optimization problems, in Proc. of the 3rd Int. Conference on Principles and Practice of Constraint Programming (CP'97). Schloss Hagenberg, Austria, Lecture Notes in Comput. Sci. 1330 (1997) 405-419.
[4] and, Partial constraint satisfaction. Artificial Intelligence 58 (19923) 21-70. | MR
[5] , Tabu search, I. ORSA J. Comput. 1 (1989) 190-206. | Zbl
[6] , Tabu search, II. ORSA J. Comput. 2 (1990) 4-32. | Zbl
[7] and, Implementing constraint relaxation over finite domains using ATMS, edited by M. Jampel, E. Freuder and M. Maher, Over-Constrained Systems. Springer-Verlag, Lecture Notes in Comput. Sci. 1106 (1996) 265-280.
[8] and, Best-first search for property maintenance in reactive constraints systems, in International Logic Programming Symposium. MIT Press, Port Jefferson, NY, USA (1997) 339-353. | MR
[9] , and, Optimization by simulated annealing. Science 220 (1983). | MR
[10] , Optimization by simulated annealing: Quantitative studies. J. Statist. Phys. 34 (1984). | MR
[11] and, SALSA, a language for search algorithms, in Proc. of CP'98. Springer, Lecture Notes in Comput. Sci. 1520 (1998) 310-324.
[12] and, Defeasible constraint solving, in Over-Constrained Systems. Springer, Lecture Notes in Comput. Sci. 1106 (1996) 151-170.
[13] ,, and, Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58 (1992) 161-205. | MR | Zbl
[14] and, A view of local search in constraint programming, in Proc. of CP'96. Springer, Lecture Notes in Comput. Sci. 1118 (1996) 353-366.
[15] , Combining local search and look-ahead for scheduling and constraint satisfaction problems, in Proc. of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97). Morgan Kaufmann, Nagoya, Japan (1997) 1254-1259.
[16] , H. fargier and G. Verfaillie, Valued constrain satisfaction problems: Hard and easy problems, in Proc. of the 14th International Joint Conference on Artificial Intelligence (IJCAI'95). Montréal, Canada (1995) 631-637.
[17] , Foundations of constraint satisfaction. Academic Press (1993).
[18] and, Solution reuse in dynamic constraint satisfaction problems, in Proc. of the 12th National Conference on Artificial Intelligence (AAAI'94). Seattle, WA, USA (1994) 307-312.
[19] and, Hierarchical constraint logic programming. J. Logic Programming 16 (1993) 277-318. | MR | Zbl
