Resource allocation in a mobile telephone network: A constructive repair algorithm

Patrice Boizumault; Philippe David; Housni Djellab

RAIRO - Operations Research (2010)

  • Volume: 35, Issue: 2, page 189-209
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Boizumault, Patrice, David, Philippe, and Djellab, Housni. " Resource allocation in a mobile telephone network: A constructive repair algorithm ." RAIRO - Operations Research 35.2 (2010): 189-209. <http://eudml.org/doc/197813>.

@article{Boizumault2010,
abstract = { 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. },
author = {Boizumault, Patrice, David, Philippe, Djellab, Housni},
journal = {RAIRO - Operations Research},
keywords = {Resource allocation; repair algorithms; constrained resolution time; CSP; telecommunications. ; resource allocation; constrained resolution time; telecommunications},
language = {eng},
month = {3},
number = {2},
pages = {189-209},
publisher = {EDP Sciences},
title = { Resource allocation in a mobile telephone network: A constructive repair algorithm },
url = {http://eudml.org/doc/197813},
volume = {35},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 2
SP - 189
EP - 209
AB - 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.
LA - eng
KW - Resource allocation; repair algorithms; constrained resolution time; CSP; telecommunications. ; resource allocation; constrained resolution time; telecommunications
UR - http://eudml.org/doc/197813
ER -

References

top
  1. A. Borning, M. Maher, A. Martindale and M. Wilson, Constraint hierarchies and logic programming, in Proc. of ICLP'89. Lisbon, Portugal (1989) 149-164.  
  2. P. David, 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. S. de Givry, G. Verfaillie and T. Schiex, 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. E.C. Freuder and R.J. Wallace, Partial constraint satisfaction. Artificial Intelligence 58 (19923) 21-70.  
  5. F. Glover, Tabu search, I. ORSA J. Comput.1 (1989) 190-206.  
  6. F. Glover, Tabu search, II. ORSA J. Comput.2 (1990) 4-32.  
  7. N. Jussien and P. Boizumault, 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. N. Jussien and P. Boizumault, Best-first search for property maintenance in reactive constraints systems, in International Logic Programming Symposium. MIT Press, Port Jefferson, NY, USA (1997) 339-353.  
  9. S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983).  
  10. S. Kirkpatrick, Optimization by simulated annealing: Quantitative studies. J. Statist. Phys. 34 (1984).  
  11. F. Laburthe and Y. Caseau, SALSA, a language for search algorithms, in Proc. of CP'98. Springer, Lecture Notes in Comput. Sci. 1520 (1998) 310-324.  
  12. F. Menezes and P. Barahona, Defeasible constraint solving, in Over-Constrained Systems. Springer, Lecture Notes in Comput. Sci. 1106 (1996) 151-170.  
  13. S. Minton, M.D. Johnston, A.B. Philips and P. Laird, Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence58 (1992) 161-205.  
  14. G. Pesant and M. Gendreau, A view of local search in constraint programming, in Proc. of CP'96. Springer, Lecture Notes in Comput. Sci. 1118 (1996) 353-366.  
  15. A. Schaerf, 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. T. Schiex, 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. E. Tsang, Foundations of constraint satisfaction. Academic Press (1993).  
  18. G. Verfaillie and T. Schiex, 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. M. Wilson and A. Borning, Hierarchical constraint logic programming. J. Logic Programming16 (1993) 277-318.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.