DFG SFB 531

Application of Computational Intelligence
in Combinatorial Optimization

Project director: Prof. Dr. Martin Skutella, Technische Universität Berlin
Prof. Dr. Petra Mutzel, Technische Universität Dortmund
Researcher: Dr. Joachim Reichel, Technische Universität Berlin
Maria Kandyba, Technische Universität Dortmund
Support: Deutsche Forschungsgemeinschaft (DFG)
within Collaborative Research Center 531 "Computational Intelligence"

Collaborative Research Center 531 "Design and Management of Complex Technical Processes and Systems by Means of Computational Intelligence Methods"

The field of Computational Intelligence (CI) covers all sorts of techniques for subsymbolic (numerical) knowledge processing, such as the well known Fuzzy Logic (FL), Neural Networks (NN), and Evolutionary Algorithms (EA) as well as other approaches with lesser dissemination. Although CI techniques are widely in use, there still exists a large gap between theory and application. To close this gap the Collaborative Research Center (SFB) 531 has been founded at the University of Dortmund in 1997 as an interdisciplinary research institute. It is financially supported by the Deutsche Forschungsgemeinschaft (DFG). The scientific goals of the SFB are the investigation and improvement of the foundations, applications, as well as combinations of CI methods.

Project B10 "Application of Computational Intelligence in Combinatorial Optimization"

The aim of this project is to apply methods of Computational Intelligence to problems and algorithms of Combinatorial Optimization. We focus on the development of exact and approximate optimization schemes. Our particular interest is to what extent the methods of Computational Intelligence may be useful to find optimal and/or provably good solutions for optimization problems. Up to today these methods were mainly used within heuristic context where the real quality of the solutions cannot be predicted. In this project hybrid algorithmic techniques will be developed and analyzed for the purpose of combining the approaches of Computational Intelligence with those of Mathematical Programming. By using the benefits of both research fields, we hope to find new algorithms which are more efficient or compute solutions of higher qualitiy. In particular, problems of Graph Layout, Network Design and Network Flow will be considered.

One of our further goals is to use Mathematical Programming to analyze methods of Computational Intelligence and to compare them with the algorithms of Combinatorial Optimization. We expect a better insight into the relationship between these research areas, which in turn may lead us to enhanced techniques in the future.

The expected results of this project can be outlined in a following way:

  1. New and improved algorithms combining classical methods of Combinatorial Optimization and Mathematical Programming with those of Computational Intelligence.
  2. Empirical results on the efficiency of these algorithms and a comparison with known methods for NP-hard problems.
  3. Theoretical analysis of the efficiency of these algorithms and quality of the solutions for simple problems.
  4. An insight into the structural relationship beween methods of Computational Intelligence and Mathematical Programming.

Publications

F. Neumann, J. Reichel, M. Skutella
Computing Minimum Cuts by Randomized Search Heuristics
Technical Report CI-242/08, Dept. of Computer Science, TU Dortmund, 2008
also available as: Preprint 3-2008, Institut für Mathematik, TU Berlin, 2008
[pdf]
[ps]
J. Reichel, M. Skutella
Evolutionary Algorithms and Matroid Optimization Problems
Proceedings of the 9th Genetic and Evolutionary Computation Conference (GECCO '07), London,
pp. 947 - 954, 2007 (best paper award)
[pdf]
[ps]
J. Reichel, M. Skutella
Evolutionary Algorithms and Matroid Optimization Problems
Technical Report CI-225/07, Dept. of Computer Science, University of Dortmund, 2007
[pdf]
[ps]

Copyright notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.