Computer Science Colloquium
Günther Raidl
Algorithms and Complexity Group, TU Wien, Austria
Joint research seminar Decision Diagrams in Combinatorial Optimization
Tue 01.10.2019, 14:00, 60 minutesJKU Management Zentrum 2nd floor, MZ 202B (Business School)
Abstract
Decision diagrams (DDs) are well-known tools for modeling and verifying properties of digital systems, including electronic circuits and abstract protocols. In recent years, it was discovered that DDs are also powerful tools for discrete optimization. So far, DDs have been primarily used in conjunction with constraint programming and mathematical programming approaches, but clearly utilizing them in or together with metaheuristics also is highly promising. An exact DD closely corresponds to the stategraph of a dynamic programming formulation to a problem at hand and represents all feasible solutions by corresponding paths from a root node to a target node. A shortest (or longest) path then represents an optimal solution. For hard problems such an exact DD usually is of only limited value due to its exponential size. More interesting from a practical point of view are compact restricted and relaxed DDs. A restricted DD represents only part of the whole solution space and therefore an approximation to the original problem. A relaxed DD, on the other hand, represents a discrete relaxation and thus a super-set of the original problem's solution space. It is obtained by superimposing nodes of an exact DD and yields dual bounds but usually not directly a feasible solution. In this talk we will consider different methods for constructing restricted and relaxed DDs and exploiting them in combinatorial optimization. This includes a novel approach based on A* search. Co-Authors: Matthias Horn (Algorithms and Complexity Group, TU Wien, Austria), Elina Rönnberg (Department of Mathematics, Linköping University, Sweden)Bio
Günther Raidl is Professor at the Institute of Logic and Computation, TU Wien, Vienna, Austria and member of the Algorithms and Complexity Group. He received his PhD in 1994 and completed his habilitation in Practical Computer Science in 2003 at TU Wien. In 2005 he received a professorship position for combinatorial optimization at TU Wien. His research interests include algorithms and data structures in general and combinatorial optimization in particular, with a specific focus on metaheuristics, mathematical programming, intelligent search methods, and hybrid optimization approaches. His research work typically combines theory and practice for application areas such as scheduling, network design, transport optimization, logistics, and cutting and packing. Günther Raidl is associate editor for the INFORMS Journal on Computing and the International Journal of Metaheuristics and at the editorial board of the Metaheuristics journal, Evolutionary Computation Journal, the Journal of Applied Metaheuristic Computing, and the Journal of Memetic Computing. He is co-founder and steering committee member of the annual European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP). He was co-chair of the 10th Metaheuristics International Conference (MIC 2013), editor-in-chief of the 2009 Genetic and Evolutionary Computation Conference (GECCO 2009), and hosted Hybrid Metaheuristics 2010 in Vienna. Since 2016 he is faculty member of the Vienna Graduate School on Computational Optimization. He has recently co-authored a text book on hybrid metaheuristics, (co-)edited 13 books and authored over 160 reviewed articles in journals, books, and conference proceedings. In 2012 he received the EvoStar Award for Outstanding Contributions to Evolutionary Computation. More information can be found at http://www.ac.tuwien.ac.at/raidl.Invited by Prof. Armin Biere (FMV) and Prof. Sophie Parragh (PLM)
The Computer Science Colloquium is organized by the Department of Coputer Science at JKU, the Österreichische Gesellschaft für Informatik (ÖGI) and the Österreichische Computergesellschaft (OCG).