Research on Optimisation
Our research is concerned with both the theory and the practice of optimisation.
The modern tools and methods of optimisation are unfortunately mostly unknown outside computing departments, so that many opportunities for better solutions and/or shorter solving times are wasted, especially by the widespread mistaken belief that (NP-)hard problems cannot be solved at all or can at best only be tackled by greedy algorithms or by other sub-optimal algorithms.
Basic Research
On the theoretical side, we address the following research issues:
- Global Constraints: specification and synthesis; reification; AUTOMATON, CUMULATIVE, and TREE constraints
- Constraint-Based Local Search: MiniZinc back-end; set variables and set constraints; specification of constraints via automata and monadic existential second-order logic; neighbourhood design; massive instance data
- Symmetry in Models and Search: detection and exploitation, in order to avoid exploring redundant parts of the search space
- Constraint-Based Modelling: string variables and constraints; relation variables; symmetry; the constraint-based modelling language ESRA
- Solution characterisation of optimality analysis for optimal scheduling defined over a (arbitrary) service rate region
Applied Research
On the practical side, we apply optimisation in hard real-world tasks:
- Air Traffic Management, with the European Organisation for the Safety of Air Navigation (EuroControl
): airspace sectorisation; contingency planning; air-traffic complexity resolution in multi-sector planning
- Analysis, Testing, and Verification: string variables and string constraints; test-case generation
- Computational Biology: construction of phylogenetic super-trees
- Computational Finance: design of synthetic CDO squared portfolios
- Mobile Communications: resource allocation and caching
- Optical networks: routing and allocation of broadcast domain
- Waste Management: optimal scheduling for waste collection
- Winter Road Maintenance: vehicle routing for road de-icing, with B&M Systemutveckling AB
, under a grant by UU Innovation
, in 2019
- Wireless Sensor Networks: network configuration