Accueil des participants

Exact General-Purpose Solvers for Mixed-Integer Bilevel Linear Programs

Ivana Ljubic

Slides of the presentation

In bilevel optimization there are two decision makers, commonly denoted as the leader and the follower, and decisions are made in a hierarchical manner. First the leader makes a decision, and then the follower optimizes its objective, affected by the decisions of the leader. When making her decision, the leader can anticipate the decisions of the follower and can take the follower’s response into consideration. In this tutorial we cover newest theoretical and computational developments for dealing with mixed-integer bilevel linear programs (MIBLPs). MIBLPs constitute a significant subfamily of bilevel optimization problems, where all objective functions and constraints are linear, and some/all variables are required to take integer values.

In the first part of this tutorial we present results from [1] that constitute necessary modifications needed to turn a standard branch-and-bound MILP solver into an exact and finitely-convergent MIBLP solver, also addressing MIBLP unboundedness and infeasibility. The proposed scheme is finitely-convergent in case both the leader and the follower problems are pure integer. In addition, it is capable of dealing with continuous variables both in the leader and in follower problems—provided that the leader variables influencing follower’s decisions are integer and bounded. We then introduce intersection cuts based on feasible-free convex sets, to be embedded in this branch-and-bound framework.

In the second part we present a new general purpose branch-and-cut framework from [2], which extends the basic concepts from [1] by introducing several new classes of valid inequalities, along with a very effective bilevel-specific preprocessing procedure. In an extensive computational study we evaluate the performance of various solution methods on a common testbed of more than 800 instances from the literature—this is by far the most extensive computational analysis ever performed for exact MIBLP solvers. Our new algorithm consistently outperforms (often by a large margin) all alternative state-of-the-art methods from the literature, including methods which exploit problem specific information for special instance classes. In particular, it allows to solve to optimality more than 300 previously unsolved instances from literature.

Literature
[1] M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl, On the Use of Intersection Cuts for Bilevel Optimization, Mathematical Programming, online first, 2017, DOI 10.1007/s10107-017-1189-5
[2] M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl, A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research 65(6): 1615-1637, 2017

Pause déjeuner

Unit Commitment under Market Equilibrium Constraints

Fabio D'Andreagiovanni

The classical Unit Commitment problem (UC) can be essentially described as the problem of establishing the energy output of a set of generation units over a time horizon, in order to satisfy a demand for energy, while minimizing the cost of generation and respecting technological restrictions of the units (e.g., minimum on/off times, ramp up/down constraints). The UC is typically modelled as a (large scale) mixed integer program and its deterministic version, namely the version not considering the presence of uncertain data, has been object of wide theoretical and applied studies over the years.
Traditional (deterministic) models for the UC assume that the net demand for each period is perfectly known in advance, or in more recent and more realistic approaches, that a set of possible demand scenarios is known (leading to stochastic or robust optimization problems). However, in practice, the demand is determined by the amounts that can be sold by the producer at given prices on the day-ahead market. Difficulties thus arise if the optimal production associated with the optimal solution to the UC problem cannot be sold at the price desired by the producer, possibly leading to losses. Another strategy could be to bid for additional quantities at a higher price to increase profit, but this could lead to infeasibilities in the production plan.
In this work, our aim is to model and solve the UC problem with a second level of decisions ensuring that the produced quantities are cleared at market equilibrium. In their simplest form, market equilibrium constraints are equivalent to the first-order optimality conditions of a linear program. The UC, in contrast, is usually a mixed-integer nonlinear program (MINLP), that is linearized and solved with traditional Mixed Integer (linear) Programming (MIP) solvers. Taking a similar approach, we face a bilevel optimization problem where the first level is a MIP and the second level is linear. In this talk, as a first approach to the problem, we assume that demand curves and offers of competitors in the market are known to the operator. This is a strong hypothesis, which, however, is functional to develop a first model. Following the classical approach for these models, we present the transformation of the problem into a single-level program by rewriting and linearizing the first-order optimality conditions of the second level. Then we present some preliminary results on the performance of MIP solvers on this model.
Joint work with Luce Brotcorne, Jerome De Boeck and Bernard Fortz.

DC programming techniques with inexact subproblems' solution for general DC programs resulting from bilevel programs

Wim Van Ackooij

In the upcoming energy landscape, the arrival of proactive consumers (prosumers) requires one to rethink traditional energy management problems. Although traditionally such energy management questions were cast as mathematical programming problems and already non-trivial to solve, in such a future, one would have to account as well for the behaviour of prosumers as independent entities. A favorable modelling framework to capture some interaction is that of bilevel programming. Unfortunately such problems are hard to solve. In some situations these bilevel programs can be cast as general DC (difference of convex) optimization problems. In this talk we will discuss some recent insights on solving the latter problems through an iterative process solving various convex optimization problems. We will in particular show that not all convex problems need to be solved to optimality. This advantage is illustrated on a bilevel energy application.

Pause café

Tropical geometry applied to bilevel programming and an application to price incentives in telecom networks

Jean-Bernard Eytard

Transparents de la présentation

Bilevel programming problems model a large class of pricing problems. However, they are generally NP-hard. In this talk, we study a special class of bilevel programming problems, in which the low-level problem can be studied thanks to tropical algebra and geometry. We present a decomposition method for these problems. Next, we study a particular case in which the optimistic case of the bilevel programming problem can be solved in polynomial time, by using discrete convexity results. Finally, we apply this to a price incentives model for mobile data consumption in telecom networks in order to limit the congestion in the network.

A Bilevel Programming Model for Proactive Countermeasure Selection in Complex ICT Systems

Mohamed Yassine Naghmouchi

We consider the Proactive Countermeasure Selection Problem (PCSP) for complex Information and Communication Technology (ICT) systems. Given 1) the Risk Assessment Graphs (RAGs), a set of digraphs, in which a node is either an access point which is the start point of an attacker, or an asset-vulnerability node to be secured; 2) a positive security threshold for each access point and each asset-vulnerability node; and 3) a set of countermeasures to deploy on the asset-vulnerability nodes, the PCSP consists in selecting the countermeasures placement with minimal cost, guaranteeing the security of all the most likely paths- from attackers point of view between each access point and each asset-vulnerability node.

We propose a bilevel programming model for the PCSP. We present two singlelevel reformulations of the bilevel program. The first formulation is a compact one, based on primal-dual optimality conditions. The second formulation is an extended one, employing an exponential number of path constraints. We propose a branch-and-cut algorithm to solve this formulation to optimality. Several series of experiments are conducted on random instances showing the efficiency of the branch-and-cut algorithm to solve the extended formulation. In addition, computational comparisons between the two formulations are discussed.