Research project: Multilevel Optimisation

Currently Active:: Yes

Multilevel optimisation problems are optimisation problems with a hierarchical structure involving multiple levels of decision making, respectively controlled by a leaders (upper-level players) and followers (lower-level players). They represent a very powerful tool for modelling a large number of real-world problems from Economics, Engineering, Health Technology, Climate Change, etc. Such problems are however very difficult to solve, and most of the attention is still focus on problems with two-level structure. Our work here is mainly devoted to the development of exact and approximate solution approaches that can solve both the optimistic case, where the follower(s) make choices that are in favour of the leader, and the pessimistic framework, where the leader takes decisions that help to minimise potential damages from adverse decisions from the follower(s).

Project Overview

Bilevel Programs with non-compact set of lower-level optimality conditions

Bilevel Programs with Non-compact Lower-level Optimality Conditions Set

The project focuses on the formulation and solution of bilevel programming problems where the second level problem does not necessarily admit a (compact) set of optimality conditions. Among different applications of this growing area of research, we mention network routing problems with fairness constraints (for which a compact reformulation is possible) and leader-follower Stackelberg games (for which the lack of optimality conditions calls for specialized algorithms). From a methodological perspective, we are also interested in bilevel programming aspects of cutting plane generation. The attention is on bound-optimal cutting planes, a cutting plane paradigm which entails the solution of a bilevel cut generating problem with a linear program at the second level, and on the generation of rank inequalities for the maximum stable set problem, with extension to the generation of template-free inequalities for general integer programs.

Newton-Type Bilevel Optimisation Methods

Newton Bilevel Optimisation Methods

Newton’s method is one of the main approaches to solve nonlinear optimisation problems. The aim of this project is to construct suitable functions or set-valued mapping that can lead to the development of a fundamental theoretical and practical framework for the computation of stationary points for bilevel optimisation problems. We intend to derive rigorous methods which present suitable convergence properties. Our first aim is to focus on the construction of such a framework for the standard optimistic version of the problem. The models will then be extended to original optimistic, pessimistic and possibly, problems with more than two levels.

Pessimistic Bilevel Optimisation

We are interested here in bilevel programs where there is no cooperation between the leader and the follower. Hence, the upper-level (leader) takes decisions that help to bound damages from the unfavourable choices from the lower-level player (follower). The aim here is to develop approximate solution methods based on the notion of two-level value functions, which are optimal value functions with the feasibility set partly defined the solution map of another (parametric) optimisation problem. We are mainly interested in building bundle-type mappings for the pessimistic two-level value functions or construct solution procedure that rely on intrinsic set-valued nature of the optimistic bilevel optimisation problem.

Transportation problems with a hierarchiecal structure

Hierarchiecal Transportation Problems

We are working on solution algorithms to solve toll optimisation, network design or origin-destination (O-D) matrices. Toll optimisation (or network pricing) problems are problems where there is a road authority managing a network system where tolls are set on various parts/links to achieve goals such as traffic and pollution reduction or just to raise revenues to be invested in the maintenance/development of the infrastructure. In the network design problem, authorities or a company has the responsibility to develop a network system while taking into account the way the users will be choosing their origin-destination points based on their knowledge of its structure. As for O-D matrix estimation problem, knowing the demand for traffic going from one origin point to a given destination point is a strategic information for key decisions in network design, network pricing, infrastructure development, etc.

Related research groups

Operational Research
Computational Optimisation

Share Share this on Facebook Share this on Twitter Share this on Weibo