Message > Post Doc INRIA Lille, Team INOCS
Le 14/03/2019 par LBrotcorne :
Solving Integer Bilevel Bilinear problems
Supervisors: Luce Brotcorne (Luce.firstname.lastname@example.org ) , Bernard Fortz (email@example.com) , Martine Labbé (firstname.lastname@example.org)
Location INRIA team INOCS, Lille Nord Europe
Application documents should contain a motivation letter, a curriculum vitae and a list of publications .
Duration : 18 months
Bilevel programs allow the modeling of situations in which a decision-maker, hereafter the leader, optimizes his/her objective by taking explicitly into account the response of another decision maker or a set of decision makers (the follower) to his/her decisions. Bilevel programs are closely related to Stackelberg (leader-follower) games as well as to the principal-agent paradigm in economics. In other words, bilevel programs can be considered as demand-offer equilibrium models where the demand is the result of another mathematical problem. The structure of bilevel problems allows the modeling of a large number of real-life problems involving two decision makers interacting sequentially hierarchically (2) and (3).
Bilevel programming problems, being generically difficult due to their non-convexity and non- differentiability, it is not surprising that most research to date has focused on the simplest cases of bilevel programs, that is problems having nice properties such as linear, quadratic or convex objective and/or constraint functions.
When the second level problem is NP-hard, the single-level reformulation of the bilevel program based on the KKT conditions cannot be applied because no complete linear description of the convex envelope of the solution set is available. Up to now most of the research devoted to integer bilevel programs has been devoted to the case where the objective functions of both levels are linear (4) and (5).
The goal of the post-doc is to study the properties of mixed integer bilevel bilinear programs on two levels and develop efficient solution methods. This field of research is and very innovative and promising because of many problems of everyday life fall within this framework (e.g. pricing problems) (1). The particular cases of energy pricing problems or joint pricing and location problems could be considered.
Candidates should hold a PhD Thesis in Operations research, mathematics, computer science, or similar fields and should ideally have a solid background in discrete optimization, integer programming, decomposition techniques. Computer science skills in algorithmic and C/C++ development are also welcome.
Knowledge of French is not required, but good communication skills and a solid knowledge of English are essential.
The INOCS team aims to develop new models, algorithmic techniques and implementations for optimization problems with complex structure (CS). More precisely, we consider that an optimization problem presents a CS when for example it involves some hierarchical leader-follower structure (bilevel optimization). Luce Brotcorne is specialist in bilevel optimization with a particular expertise to solve Stackelberg games, while Bernard Fortz has also a strong experience in decomposition methods that will be at the core of algorithms developed in the project.
(1) S. Afsar, L. Brotcorne, P. Marcotte and G. Savard, Algorithms for Load Balancing in Energy Systems with Smart Grids, soumis a? Computers and Operations Research, 2019.
(2) L. Brotcorne, P. Marcotte, and G. Savard. Bilevel programming: The Montreal school. INFOR: Information Systems and Operational Research, 56(4):231–246, 2008.
(3) B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235–256, 2007.
(4) S. DeNegre and T. K. Ralphs, “A Branch-and-Cut Algorithm for Bilevel Integer Programming,” in Proceedings of the Eleventh INFORMS Computing Society Meeting, 2009, pp. 65-78.
(5) I. Ljubic, M. Fischetti, M. Monaci and M. Sinnl, "On the use of intersection cuts for bilevel optimization", Mathematical Programming Series A & B, 2018, Vol. 172, Numéro 1-2, p. 77-103