CALMA: Combinatorial ALgorithms for Military Applications

CALMA is the name of a research project setting out to determine strengths and weaknesses of a range of solution approaches to combinatorial problems. The project has been financed by the Ministeries of Defence of the Netherlands, France, and the United Kingdom in the EUCLID programme RTP 6-4 as part of CEPA 6 (Artificial Intelligence). EUCLID stands for EUropean Cooperation for the Long term In Defence.

Several research groups from the three participating countries have applied their expertise in Computing Science, Mathematics of Operations Research and Local Search to the Radio Link Frequency Assignment Problem which was chosen to serve as a testbed for development and comparison of distinct optimization strategies and methods.

More detailed information of the distinct approaches can be obtained from the various participants. Coordinator of the project was ONERA/CERT in Toulouse. Test problems and reports have been distributed among participants via the CERT ftp-server, but due to safety measures this site is only accessible by personal logins. The Eindhoven ftp-site holds documents that describe the scientific results from this project, as well as several sets of test-problems.

The following groups participate in the project:

• Eindhoven University, on good neighborhood-structures: Jan Karel Lenstra, Cor Hurkens, Sergey Tiourine. See Eindhoven Combinatorial Optimization Group for further information.
• Eindhoven University, on polyhedral methods: Stan van Hoesel, Karen Aardal, Giovanni Righini. See Eindhoven Combinatorial Optimization Group for further information.
• Delft University, combining polyhedral techniques with heuristic methods: Kees Roos, Tamas Terlaky, Alexander Hipolito, Benjamin Jansen, Henk van Benthem, Joost Warners. See Delft CALMA Group for more information.
• Limburg University, Maastricht, on Constraint Satisfaction Propagation and on Genetic Algorithms: Antoon Kolen, Jaap Geerdink, Stan van Hoesel.
  NEW RESULTS in frequency assignment planning, obtained in the years following the CALMA project can be found at the Maastricht WEBsite.
• ONERA CERT Computer Science Department (Centre d'Etudes et de Recherces de Toulouse) on Simulated Annealing and Constraint Satisfaction: Paul Bourret, Eric Bensana, Thomas Schiex.
• University of East Anglia, Norwich, on Genetic Algorithms and Parallellization: Vic Rayward Smith, George Smith, Geoff McKeown, members of the Mathematical Algorithms Group.
• King's College London CALMA Group, on Tabu Search and GENET: John Taylor, James Boyce, Harry Dimitropoulos (KCL-IPG), Gregor vom Scheidt (see KCL-Genet).
• TNO Human Factors Research Institute (Soesterberg, NL) on military applications: Alexander Toet.

CALMA-Symposium

The results of the research have been discussed on a conference concluding the project. This Calma Symposium was organized by DUT and TNO and took place on November 24, 1995, in Scheveningen. For more information, click here.

Publications

The Eindhoven ftp-site holds documents written in the context of this project. Other publications are expected to appear in regular scientific papers. Here are some references to such papers that are published or have been submitted:

• C.A.J. Hurkens, S.R. Tiourine, "Upper and lower bounding techniques for frequency assignment problems". Memorandum COSOR 95-34, Eindhoven University of Technology. [submitted for publication]
• J.P. Warners, T. Terlaky, C. Roos, B. Jansen, "Potential Reduction Algorithms for Structured Combinatorial Optimization Problems", DUT-TWI report no. 95-88, Delft University of Technology, Delft, The Netherlands. [submitted to "Operations Research Letters"]
• J.P. Warners, T. Terlaky, C. Roos, B. Jansen, "A Potential Reduction Approach to the Frequency Assignment Problem", DUT-TWI report no. 95-98, Delft University of Technology, Delft, The Netherlands. [submitted to "Discrete Applied Mathematics"]
• H.P. van Benthem, "GRAPH: Generating Radio link Frequency Assignments Problems Heuristically", Master's Thesis, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands, May 1995.
• J.P. Warners, "A Potential Reduction Approach to the Radio Link Frequency Assignment Problem", Master's Thesis, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands, April 1995.
• Dr.A.Bouju, Dr.J.F.Boyce, C.H.D.Dimitropoulos, G.vom Scheidt, Prof.J.G.Taylor, "Tabu Search for the Radio Links Frequency Assignment Problem", Presented in : Applied Decision Technologies [ADT'95], Brunel Conference Centre, London, UK: 3-5 April 1995 / Organised by UNICOM.
• Dr.A.Bouju, Dr.J.F.Boyce, C.H.D.Dimitropoulos, G.vom Scheidt, Prof.J.G.Taylor [KCL] Dr.A.Likas, G.Papageorgiou, Prof.A.Stafylopatis [NTUA], "Intelligent Search for the Radio Links Frequency Assignment Problem", Presented in : Int. Conf. for Digital Signal Processing [DSP'95], Limassol, CYPRUS: 26-28 June 1995 / IEEE.
• Dr.J.F.Boyce, C.H.D.Dimitropoulos, G.vom Scheidt, Prof.J.G.Taylor, "GENET and Tabu Search for Cominatorial Optimization Problems", Presented in : World Congress on Neural Networks [WCNN'95], Washington, D.C., USA: 17-21 July 1995 / INNS.
• Gregor vom Scheidt, "Extension of GENET to n-ary Partial Constraint Satisfaction Problems and Constraint Satisfaction Optimisation Problems", MSc. Thesis - King's College London
• A. Kapsalis, V.J. Rayward-Smith and G.D. Smith, "A Unified Parallel Genetic Algorithm", in Evolutionary Computing, Lecture Notes in Computer Science, No 865, Springer-Verlag, pp 131-149.
• A. Kapsalis, P. Chardaire, V.J. Rayward-Smith and G.D. Smith, "The Radio-Link Frequency Assignment: A Case Study using Genetic Algorithms", appearing in Evolutionary Computing 2, Lecture Notes in Computer Science, No 993, Springer-Verlag, pp 117-131.
• P. Chardaire, A. Kapsalis, J.W. Mann, V. J. Rayward-Smith, and G.D. Smith, "Applications of Genetic Algorithms in Telecommunications", Proc. Applications of Neural Networks to Telecommunications 2, Stockholm, May, 1995, J. Alspector, R. Goodman, T. X. Brown (eds), Lawrence Erlbaum, pp 290-299.
• A. Kapsalis and G.D. Smith, " A Meta Genetic Algorithm for the Radio Link Frequency Assignment Problem", accepted for SOCO96, International Conference on Soft Computing, Reading 1996.
• A. Kapsalis, V.J. Rayward-Smith and G.D. Smith, "Using Genetic Algorithms to solve the Radio-Link Frequency Assignment", Proc. 2nd Int. Conf. on Artificial Neural Networks and Genetic Algorithms, Ales, France, 1995, D. W. Pearson, N. C. Steele and R. F. Albrecht (eds), Springer-Verlag (1995) pp 37-40.
• B. Cabon, P. Bourret, E. Bensana, J.L. Bussenot, M. Ouedraogo (CERT), G. Strausz (University of Budapest), "Behaviour of three methods applied to easy and hard combinatorial problems", CP'95 Workshop on Studying and solving really hard problems, Cassis (France), September 1995.
• T. Schiex, H. Fargier, G. Verfaillie, "Valuated constraint satisfaction problems; hard and easy problems", 14th International Joint Conference on Artificial Intelligence, August 1995