Combinatorial Problem Solving
Teknik
Pierre Flener
2011-09-02 16:14
Combinatorial problem solving technologies offer methods and tools for the modelling and solving of problems with constraints. These problems are usually very challenging, but are essential to Swedish industry and academia, such as configuration, design, diagnosis, logistics, planning, routing, scheduling, and workforce management. These technologies include constraint programming (CP), mixed integer programming (MIP), propositional satisfiability (SAT), stochastic local search (SLS), and their hybrids. These technologies are superior for problems with many heterogenous constraints, where algorithmic solutions are difficult to develop and maintain, especially in situations when the constraints are changing.
Applications: In Sweden, many successful applications have been developed. For example, Jeppesen Systems (formerly Carmen Systems) is a supplier of crew and fleet optimisation systems using MIP and CP for airlines and railways; more than a quarter of the world's airline crews fly schedules produced with their tools. The Swedish Institute of Computer Science (SICS.se) has a long track record in using CP for industrial applications: shunting yard scheduling for cargo trains, frequency planning for GSM base stations, scheduling for steel industry, gene expression analysis, dispensation scheduling for DNA sequence analysis, 2D/3D packing in logistics, etc. OptimalSolutions.se uses MIP and CP to develop support for field services, such as a dispatcher for caretakers of elderly people. Tacton.se has a world-leading e-commerce engine for configurable product lines, based on CP. TradeExtensions.se is a world leader in strategic sourcing software, based on MIP.
Tools: SICS is a provider of SICStus Prolog, which includes a leading CP solver. At KTH, many research results have been incorporated into Gecode, a major CP platform that is widely used (several thousand users) for research, teaching, and applications. At Lund University, the Java Constraint Programming library (JaCoP) has been developed, the primary goal being to facilitate the application of CP in electronic design automation, but it became a general CP platform used in projects worldwide.
Research: There are strong (but small) research groups at some Swedish universities and at SICS, all with growing ties to Swedish industry.
Note that France (in Nantes), Ireland (in Cork, via SFI and Enterprise Ireland), and Australia (via NICTA) have realised the importance of combinatorial problem solving and fund large clusters in CP that attract many researchers and much industrial cooperation.
We argue that research in combinatorial problem solving should also be strengthened in Sweden, considering the growing importance of these problems to its industry and academia. Industrial practitioners and academics in other areas are often unaware of leading-edge research in combinatorial problem solving, and hence opportunities for technology transfer and competitive advantage are being missed. Another motivation is to retain and possibly recruit talent in Sweden.
Prof. Pierre Flener, Uppsala University;
Docent Mats Carlsson, SICS;
Prof. Krzysztof Kuchcinski, Lund University;
Docent Justin Pearson, Uppsala University;
Docent Christian Schulte, KTH
Inga kommentarer inlagda.
Fasen är stängd, inte möjligt att kommentera.