Optimisation: The Science of Taking Better Decisions
Solving an optimisation problem is about finding solutions that satisfy constraints. One is often interested in the best solutions.
Overview
Solving an optimisation problem is about finding solutions that satisfy constraints. One is often interested in the best solutions. An optimisation problem is categorised as discrete or continuous, depending on what the optimisation variables represent.
In discrete optimisation, a solution might be an allocation of resources (say a personnel roster, with work regulations and employee preferences as constraints), a packing (say of containers), a plan, a set of routes (say of vehicles in logistics, or of dataflows in a communication network), a schedule (say a school timetable), or a plan for energy usage (say for the charging of electric buses).
In continuous optimisation, a solution is instead one or more continuous entities like concentrations (say of pharmaceutical compounds), intensities (say in medical imaging or radiotherapy planning), or model parameters (say weights in a neural network). These problems are often solved by iterative, gradient-based, methods.
The challenge is to find good solutions fast. Our research focuses on identifying new and efficient optimisation models and methods, often driven by real-world applications.
Research topics
- Constraint programming (CP) is an AI approach to optimisation: modelling languages; high-level constraints; high-level types for decision variables; symmetry breaking
- Local search (LS): modelling languages; search languages; solver design; autonomous search
- Mathematical optimisation (MP): efficient mathematical modelling; linear programming (LP); mixed integer (linear) programming (MIP)
- Propositional satisfiability (SAT) and Satisfiability modulo theories (SMT): trustworthy and verified solvers; proofs and certificates; competitions and evaluations
- Large-scale optimisation (LSO) and inverse problems (IP): optimisation for deep learning; non-convex optimisation; ill-posed inverse problems; simulation-based inference; etc
- Surrogate-based optimisation and Bayesian optimisation (SBO): scalable acquisition functions/sampling algorithms; multi-objective and constrained black-box optimisation; optimisation of multi-fidelity (simulation-based) objective functions; evolutionary optimisation; etc
- Applied optimisation: air traffic management; resource allocation in networks and mobile communications; cutting patterns for sawmills; software testing, analysis, and verification; vehicle routing for waste management; vehicle routing for winter road maintenance; charging of electric buses; expectation-maximisation (EM) for hidden Markov models; etc
Research entities
- Optimisation research group: CP, LS, MP, applications
- Uppsala Learning, Inference, and Optimisation Lab: SBO, LSO, IP, applications
We are also part of eSSENCE, a strategic collaborative research programme in e-science between Uppsala University, Lund University, and Umeå University.
Faculty members
- José Mairton Barros da Silva Júnior (also see his homepage): MP, MIP, applications
- Pierre Flener (also see his homepage): CP, LS, applications
- María Andreína Francisco Rodríguez (also see her homepage): CP, applications
- Carl Nettelblad (also see his homepage): LSO, EM, SAT, applications
- Justin Pearson (also see his homepage): CP, LS, applications
- Prashant Singh (also see his homepage): SBO, LSO, IP, applications
- Jens Sjölund (also see his homepage): MP, LSO, IP, SBO, applications
- Tjark Weber (also see his homepage): SAT, SMT
- Di Yuan: MP, applications
Research awards
- Jens Sjölund: Göran Gustafsson Prize 2024 for young researchers, 2024
- Gustav Björdal: Honorable Mention for the ACP Doctoral Research Award, 2023 (PhD dissertation)
- Mats Carlsson: ACP Research Excellence Award, 2023
- Lei You: INFORMS Telecommunications & Network Analytics Best Dissertation Award, 2020 (PhD dissertation)
Education
- 1DL442: Combinatorial Optimisation and Constraint Programming (10 credits): CP, LS
- 1DL451: Modelling for Combinatorial Optimisation (5 credits): CP, LS, MP, SAT, SMT
- 1DL481: Algorithms and Data Structures III (5 credits): LS, MP, SAT, SMT
- 1RT242: Applied Systems Analysis (5 credits): LP, MIP
- 1TD184: [Continuous] Optimisation (5 credits): MP
- Convex Optimisation (PhD course, 7 or 10 credits): MP, IP, applications
- Large-Scale Optimisation (PhD course, 6 or 9 credits): LSO, IP, applications
- Numerical Optimisation (PhD course, 7.5 credits): LSO, IP, SBO