Topic outline

  • General

    Introduction

    Bilevel optimization problems model hierarchical non-cooperative decision processes in which the upper-level decision maker (the leader) and the lower level decision maker (the follower) control different sets of variables and have their own objective functions subject to interdependent constraints.  The lower level problem is embedded in the constraints of the upper-level problem. Decisions are made sequentially, as the leader makes his decisions first by selecting values for his variables. The follower then reacts by optimizing his objective function(s) on the feasible choices restricted by the leader’s decisions. Thus, the leader needs to consider the follower’s reaction to the setting of his variables since this influences feasibility and the leader’s objective function(s) value(s). Sequential decision-making processes that can be modelled by bilevel optimization problems arise in many aspects of resource planning, management and policy-making, namely the design of pricing policies.

    A multiobjective bilevel problem (MOBP) may have multiple objective functions at one or both levels. A special case of MOBP is the semivectorial bilevel problem (SVBP), in which there is a single objective function at the upper level and multiple objectives at the lower level. The existence of multiple objective functions at the lower level problem adds further challenges and difficulties to a bilevel problem because the leader has to deal with the uncertainty related to the follower’s reaction. For each leader’s decision, the follower has a set of efficient solutions. If the leader has no (or has little) knowledge about the follower’s preferences, it may be very difficult for him to anticipate the follower’s choice among his efficient set. 

    This course aims to present the main concepts in single and multi-objective bilevel optimization using illustrative graphical examples, some methodological approaches to compute optimal/nondominated solutions, also addressing possible pitfalls associated with the computation of those solutions, as well as applications on real-world problems, particularly in the energy sector. A particular application in the electricity retail market will be presented, which studies the interaction between electricity retailers and consumers engaging in demand response: a retailer (leader) aims to determine dynamic (time-of-use) tariffs to be offered to consumers to maximize profits; however, it should take into account that consumers (follower) can re-schedule the operation of their appliances to minimize cost and/or maximize comfort.


    Contents

    • Formulations and main concepts of single-objective bilevel optimization;
    • Optimistic vs. pessimistic solutions;
    • Models and applications of single-objective bilevel optimization;
    • Application in the energy sector: optimization of time-of-use electricity pricing considering demand response
    • Formulations and main concepts of multi-objective bilevel optimization;
    • The semivectorial bilevel problem (SVBP);
    • Different types of solutions to the SVBP: optimistic, pessimistic, deceiving and rewarding solutions;
    • Optimistic and pessimistic Pareto fronts of bilevel problems with multiple objective functions at both levels;
    • Models and applications of multi-objective bilevel optimization;
    • A SVBP approach to optimize electricity dynamic retail pricing.


    Lecturers:  Carlos Henggeler Antunes and Maria João Alves (University of Coimbra, Portugal)

    Assistant: Ellie Dillon (Department of Mathematics and Systems Analysis)


    References:

    • Alves, M. J., C. H. Antunes (2016) “An illustration of different concepts of solutions in semivectorial bilevel programming”, Proc. 2016 IEEE Symposium Series on Computational Intelligence (SSCI), Athens. doi: 10.1109/SSCI.2016.7850219.

    • Alves, M. J., C. H. Antunes (2018) “A semivectorial bilevel programming approach to optimize electricity dynamic time-of-use retail pricing”, Computers & Operations Research, 92, 130-144. doi: 10.1016/j.cor.2017.12.014

    • Alves, M. J., C. H. Antunes, J. P. Costa (2019) “Multiobjective Bilevel Programming: concepts and perspectives of development”. In: M. Doumpos, J. Figueira, S. Greco, C. Zopounidis (Editors), “New Perspectives in Multicriteria Decision Making - Innovative Applications and Case Studies”, 267-293, Springer, 2019.   

    • Alves, M. J., C. H. Antunes, P. Carrasqueira (2016) "A hybrid genetic algorithm for the interaction of electricity retailers with demand response", In:  G. Squillero and P. Burelli, "Applications of Evolutionary Computation", Proc. 19th Conference EvoApplications, Part I, Lecture Notes in Computer Science, vol. 9597, 459-474, Springer. doi: 10.1007/978-3-319-31204-0_30 

    • Bard, J. F. (2013) “Practical bilevel optimization: algorithms and applications”, vol. 30. Springer Science & Business Media.

    • Labbé, M., A. Violin (2013) “Bilevel programming and price setting problems”, 4OR, 11(1), 1–30. doi: 10.1007/s10288-012-0213-0.

    • Sinha, A., P. Malo, K. Deb (2018) “A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications”, IEEE Transactions on Evolutionary Computation, 22(2), 276–295. doi: 10.1109/TEVC.2017.2712906.