Mathieu Besançon
email: mathieu.besancon@polymtl.ca

Miguel F Anjos

Luce Brotcorne

Near-optimal robust bilevel optimization

Keywords: bilevel optimization, robust optimization, game theory, bounded rationality, duality, bilinear constraints, extended formulation Mathematics Subject Classification (2010) 90C33, 90C46, 91A65, 90C26, 90C34

Introduction

Bilevel optimization problems embed the optimality conditions of a sub-problem into the constraints of another one. They can model various decision-making problems such as Stackelberg or leader-follower games, market equilibria, or pricing and revenue management. A review of methods and applications of bilevel problems is presented in [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF]. In the classical setting of bilevel problems, when optimizing their objective function, the upper level anticipates an optimal reaction of the lower level to its decisions. However, in many practical cases, the lower level can make near-optimal decisions [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF]. An important issue in this setting is the definition of the robustness of the upper-level decisions with respect to near-optimal lower-level solutions.

For example, in some engineering applications [START_REF] Dempe | Foundations of bilevel programming[END_REF][START_REF] Stavroulakis | Optimal structural design in nonsmooth mechanics[END_REF][START_REF] Nicholls | Optimizing the operations of an aluminium smelter using non-linear bilevel programming[END_REF], the decision-maker optimizes an outcome over a dynamical system (modelled as the lower level). For stable systems, the rate of change of the state variables decreases as the system converges towards a minimum of its potential function. If the system is stopped before reaching the minimum, the designer of the system would require that the upper-level constraints be feasible for near-optimal lower-level solutions.

The concept of bounded rationality initially proposed in [START_REF] Simon | Theories of bounded rationality[END_REF], sometimes referred as ε-rationality [START_REF] Aumann | Rationality and bounded rationality[END_REF], defines an economic and behavioural interpretation of a decision-making process where an agent aims to take any solution associated with a "satisfactory" objective value instead of the optimal one.

Protecting the upper level from a violation of its constraints by deviations of the lower level is a form of robust optimization, as a protection of some constraints against uncertain parameters of the problem. Therefore, we use the terms "near-optimal robustness" and "near-optimal robust bilevel problem" or NORBiP in the rest of the paper.

The introduction of uncertainty and robustness in games has been approached under different angles in the literature. In [START_REF] Aghassi | Robust game theory[END_REF], the authors prove the existence of robust counterparts of Nash equilibria under standard assumptions for simultaneous games without the knowledge of probability distributions associated with the uncertainty. In [START_REF] Ordóñez | Robust wardrop equilibrium[END_REF], the robust version of a network congestion problem is developed. Users are assumed to make decisions under bounded rationality, leading to a robust Wardrop equilibrium. A column generation scheme is designed to build path candidates. Robust versions of bilevel problems modelling specific Stackelberg games have been studied in [START_REF] Jain | Robust solutions in stackelberg games: Addressing boundedly rational human preference models[END_REF][START_REF] Pita | Robust solutions to stackelberg games: Addressing bounded rationality and limited observations in human cognition[END_REF], using robust formulations to protect the leader against non-rationality or partial rationality of the follower. A stochastic version of the pessimistic bilevel problem is studied in [START_REF] Yanıkoğlu | Decision rule bounds for two-stage stochastic bilevel programs[END_REF], with the random variable being realized after the upper level and before the lower level. The authors then derive lower and upper bounds on the pessimistic and optimistic versions of the stochastic bilevel problem as MILPs, leveraging an exact linearization by assuming the upperlevel variables are all binary. In the model developed in this paper, we derive an exact MILP reformulation while not relying on the assumption of pure binary upper-level variables. The models developed in [START_REF] Zare | On a class of bilevel linear mixedinteger programs in adversarial settings[END_REF] and [START_REF] Zare | On bilevel optimization with inexact follower[END_REF] explore different forms of bounded or partial rationality of the lower level in bilevel optimization, where the lower level either makes a decision using an imperfect algorithm or may deviate from their optimal value in a way that hurts the ob-jective of the upper level. By defining the uncertainty in terms of a deviation from optimality of the lower level, our formulation offers a novel interpretation of robustness for bilevel problems and Stackelberg games.

Solving bilevel problems under limited deviations of the lower-level response was introduced in [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF] under the term "ε-approximation" of the pessimistic bilevel problem. The authors focus on the independent case, i.e. cases where the lower-level feasible set is independent of the upper-level decision. Problems in such settings are shown to be simpler to handle than the dependent case and can be solved in polynomial time when the lower-level problem is linear under the optimistic and pessimistic assumptions. A custom algorithm is designed for the independent case, solving a sequence of non-convex non-linear problems relying on global optimization solvers. We consider bilevel problems involving upper-and lower-level variables in the constraints and objective functions at both levels, thus more general than the independent "εapproximation" from [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF]. Unlike the independent case, the dependent bilevel problem is NP-hard even when the constraints and objectives are linear. Since this variant consists in protecting the upper-level feasibility against the uncertainty of near-optimal solutions of the lower-level, we next use the terms near-optimal robustness and near-optimal robust bilevel problem (NORBiP ) to qualify this extension.

The main contributions of the paper are:

1. The definition and formulation of the dependent near-optimal robust bilevel problem, resulting in a generalized semi-infinite problem and its interpretation as a special case of robust optimization applied to bilevel problems. 2. The study of duality-based reformulations of NORBiP where the lowerlevel problem is convex conic or linear in Section 3, resulting in a finitedimensional single-level optimization problem. 3. An extended formulation for the linear-linear NORBiP in Section 4, linearizing the bilinear constraints of the single-level model using disjunctive constraints. 4. A solution algorithm for the linear-linear NORBiP in Section 5 using the extended formulation and its implementation with several variants.

The paper is organized as follows. In Section 2, we define the concepts of near-optimal set and near-optimal robust bilevel problem. We study the cases of convex and linear lower-level problems in Section 3 and Section 4 respectively. In these cases, the near-optimal robust bilevel problem can be reformulated in a single level. A solution algorithm is provided and computational experiments are conducted for the linear case in Section 5, comparing the extended formulation to the compact bilinear one and studying the impact of valid inequalities. Finally, in Section 6 we draw some conclusions and highlight research perspectives on near-optimal robustness. 2 Near-optimal set and near-optimal robust bilevel problem

In this section, we first define the near-optimal set of the lower level and their extensions to near-optimal robust bilevel problems. Next, we illustrate the concepts on an example and highlight several properties of general nearoptimal robust bilevel problems before focusing on the convex and linear cases in the following sections. The generic bilevel problem is classically defined as:

min x F (x, v) (1a) s.t. G k (x, v) ≤ 0 ∀k ∈ [[m u ]] (1b) x ∈ X (1c) v ∈ arg min y∈Y {f (x, y) s.t. g i (x, y) ≤ 0 ∀i ∈ [[m l ]]}. (1d)
The upper-and lower-level objective functions are noted F, f : X × Y → R respectively. Constraint (1b) and g i (x, y) ≤ 0 ∀i ∈ [[m l ]] are the upper-and lower-level constraints respectively. In this section, we assume that Y = R n l in order that the lower-level feasible set can be only determined by the g i functions. The optimal value function φ(x) is defined as follows:

φ : R nu → {-∞} ∪ R ∪ {+∞} φ(x) = min y {f (x, y) s.t. g(x, y) ≤ 0}. (2)
To keep the notation succinct, the indices of the lower-level constraints g i are omitted when not needed as in Constraint [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF]. Throughout the paper, it is assumed that the lower-level problem is feasible and bounded for any given upper-level decision.

When, for a feasible upper-level decision, the solution to the lower-level problem is not unique, the bilevel problem is not well defined and further assumptions are required [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF]. In the optimistic case, we assume that the lower level selects the optimal solution favouring the upper level and the optimal solution disfavouring them the most in the pessimistic case. We refer the reader to [START_REF] Dempe | Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks[END_REF]Chapter 1] for further details on these two approaches. The near-optimal set of the lower level Z(x; δ) is defined for a given upper-level decision x and tolerance δ as:

Z(x; δ) = {y | g(x, y) ≤ 0, f (x, y) ≤ φ(x) + δ}.
A Near-Optimal Robust Bilevel Problem, NORBiP, of parameter δ is defined as a bilevel problem where the upper-level constraints are satisfied for any lower-level solution z in the near-optimal set Z(x; δ).

min x,v F (x, v) (3a) s.t. G k (x, v) ≤ 0 ∀k ∈ [[m u ]] (3b) f (x, v) ≤ φ(x) (3c) g(x, v) ≤ 0 (3d) G k (x, z) ≤ 0 ∀z ∈ Z(x; δ) ∀k ∈ [[m u ]] (3e)
x ∈ X .

Each k constraint in (3b) is satisfied if the corresponding constraint set in (3e) holds and is therefore redundant, since v ∈ Z(x; δ). However, we mention Constraint (3b) in the formulation to highlight the structure of the initial bilevel problem in the near-optimal robust formulation.

The special case Z(x; 0) is the set of optimal solutions to the original lowerlevel problem, NORBiP with δ = 0 is therefore equivalent to the pessimistic bilevel problem as formulated in [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF]:

f (x, y) ≤ φ(x) ∀y ∈ Z(x; 0).
For δ < 0, Z(x; δ) is the empty set, in which case Problem (3) is equivalent to the original optimistic bilevel problem while the set Z(x; ∞) corresponds to the complete lower-level feasible set, assuming the lower-level optimal solution is not unbounded for the given upper-level decision x.

Unlike the constraint-based pessimistic bilevel problem presented in [START_REF] Wiesemann | Pessimistic Bilevel Optimization[END_REF], the upper-level objective F (x, v) depends on both the upper-and lower-level variables, but is only evaluated with the optimistic lower-level variable v and not with a worst-case near-optimal solution. This implies the upper level chooses the best optimistic decision which protects its feasibility from near-optimal deviations. One implication for the modeller is that a near-optimal robust problem can be constructed directly from a bilevel instance where the objective function often depends on the variables of the two levels. Alternatively, the near-optimal robust formulation can protect both the upper-level objective value and constraints from near-optimal deviations of the lower level using an epigraph formulation introducing an additional variable:

min x,v,τ τ (4a) s.t. G k (x, v) ≤ 0 ∀k ∈ [[m u ]] (4b) f (x, v) ≤ φ(x) (4c) g(x, v) ≤ 0 (4d) F (x, z) ≤ τ ∀z ∈ Z(x; δ) (4e) G k (x, z) ≤ 0 ∀z ∈ Z(x; δ) ∀k ∈ [[m u ]] (4f) x ∈ X . (4g)
The two models define different levels of conservativeness and risk. Indeed: opt(1a-1d) ≤ opt(3a-3f) ≤ opt(4a-4g), with opt(P ) the optimal value of problem P . Both near-optimal robust formulations can be of interest to model decision-making applications. It can also be noted that Problem 3 includes the special case of opposite objectives between the two levels, i.e. problems for which F (x, v) = -f (x, v). The two models offer different levels of conservativeness and risk and can both be of interest when modelling decision-making situations.

Constraint (3e) is a generalized semi-infinite constraint, based on the terminology from [START_REF] Still | Generalized semi-infinite programming: Theory and methods[END_REF]. The dependence of the set of constraints Z(x; δ) on the decision variables leads to the characterization of Problem (3) as a robust problem with decision-dependent uncertainty [START_REF] Goel | A class of stochastic programs with decision dependent uncertainty[END_REF]. Each constraint in the set (3e) can be replaced by the corresponding worst-case second-level decision z k obtained as the solution of the adversarial problem, parameterized by (x, v, δ):

z k ∈ arg max y G k (x, y) (5a) s.t. f (x, y) ≤ φ(x) + δ (5b) g(x, y) ≤ 0. (5c)
Finally, the near-optimal robust bilevel optimization problem can be expressed as:

min x,v F (x, v) (6a)
s.t. f (x, v) ≤ φ(x) (6b) g(x, v) ≤ 0 (6c) 0 ≥ max y {G k (x, y) s.t. y ∈ Z(x; δ)} ∀k ∈ [[m u ]] (6d)
x ∈ X .

In the robust optimization literature, models can present uncertainty on the constraints and/or on the objective function [START_REF] Gabrel | Recent advances in robust optimization: An overview[END_REF]. In bilevel optimization, the first case corresponds to NORBiP, where the impact of near-optimal lowerlevel solutions on the upper-level constraints is studied. The second case corresponds to the impact of near-optimal lower-level decisions on the upper-level objective value.

We next prove that the model including uncertainty on the objective, named Objective-Robust Near-Optimal Bilevel Problem (ORNOBiP ), is a special case of NORBiP.

ORNOBiP is defined as:

min x∈X sup z∈Z(x;δ) F (x, z) (7a) s.t. Z(x; δ) = {y s.t. g(x, y) ≤ 0, f (x, y) ≤ φ(x) + δ}. (7b)
In contrast to most objective-robust problem formulations, the uncertainty set Z depends on the upper-level solution x, qualifying Problem (7) as a problem with decision-dependent uncertainty.

Proposition 1 ORNOBiP is a special case of NORBiP.

Proof The reduction of the objective-uncertain robust problem to a constraintuncertain robust formulation is detailed in [START_REF] Bertsimas | Theory and Applications of Robust Optimization[END_REF]. In particular, Problem ( 7) is equivalent to:

min x,τ τ s.t. x ∈ X τ ≥ F (x, z) ∀z ∈ Z(x, δ),
this formulation is a special case of NORBiP.

The pessimistic bilevel optimization problem defined in [START_REF] Loridan | Weak via strong Stackelberg problem: New results[END_REF] is both a special case and a relaxation of ORNOBiP. For δ = 0, the inner problem of ORNOBiP is equivalent to finding the worst lower-level decision with respect to the upper-level objective amongst the lower-level-optimal solutions. For any δ > 0, the inner problem can select the worst solutions with respect to the upper-level objective that are not optimal for the lower level. The pessimistic bilevel problem is therefore a relaxation of ORNOBiP.

We illustrate the concept of near-optimal set and near-optimal robust solution with the following linear bilevel problem, represented in Fig. 1.

min x,v x (8)
s.t. x ≥ 0 v ≥ 1 - x 10 v ∈ arg max y {y s.t. y ≤ 1 + x 10 }.
The high-point relaxation of Problem [START_REF] Aghassi | Robust game theory[END_REF], obtained by relaxing the optimality constraint of the lower-level, while maintaining feasibility, is:

min x,v x s.t. x ≥ 0 v ≥ 1 - x 10 v ≤ 1 + x 10 .
The shaded area in Fig. 1 represents the interior of the polytope, which is feasible for the high-point relaxation. The induced set, resulting from the optimal lower-level reaction, is given by:

{(x, y) ∈ (R + , R) s.t. y = 1 + x 10 }.
The unique optimal point is (x, ŷ) = (0, 1).

0.5 1 1.5 2 0.5 1 1.5 f(x) = -y F(x,y) = x E Fig. 1 Linear bilevel problem
Let us now consider a near-optimal tolerance of the follower with δ = 0.1. If the upper-level decision is x, then the lower level can take any value between 1 -δ = 0.9 and 1. All these values except 1 lead to an unsatisfied upper-level constraint problem. The problem can be reformulated as:

min x,v x s.t. x ≥ 0 v ≥ 1 - x 10 v ∈ arg max y {y s.t. y ≤ 1 + x 10 } z ≥ 1 - x 10 ∀z s.t. {z ≤ 1 + x 10 , z ≥ v -δ}.
Fig. 2 illustrates the near-optimal equivalent of the problem with an additional constraint ensuring the satisfaction of the upper-level constraint for all near-optimal responses of the lower level. This additional constraint is represented by the dashed line. The optimal upper-level decision is x = 0.5, for which the optimal lower-level reaction is y = 1 + 0.1 • 0.5 = 1.05. The boundary of the near-optimal set is y =

0.5 1.1 1.7 0.5 1 1.5 f(x) = -y F(x,y) = x E F
Fig. 2 Linear bilevel problem with a near-optimality robustness constraint

1 -0.1 • 0.5 = 0.95.
In the rest of this section, we establish properties of the near-optimal set and near-optimal robust bilevel problems. If the lower-level optimization problem is convex, then the near-optimal set Z(x; θ) is convex as the intersection of two convex sets:

-{y | g(x, y) ≤ 0} -{y | f (x, y) ≤ φ(x) + δ}.
In robust optimization, the characteristics of the uncertainty set sharply impact the difficulty of solving the problem. The near-optimal set of the lowerlevel is not always bounded; this can lead to infeasible or ill-defined nearoptimal robust counterparts of bilevel problems. In the next proposition, we define conditions under which the uncertainty set Z(x; δ) is bounded.

Proposition 2 For a given pair (x, δ), any of the following properties is sufficient for Z(x; δ) to be a bounded set:

1. The lower-level feasible domain is bounded. 2. f (x, •) is radially unbounded with respect to y.

3. f (x, •) is radially bounded such that: lim r∈R,r→+∞ f (x, rs) > f (x, v) + δ ∀s ∈ S,
with S the unit sphere in the space of lower-level decisions.

Proof The first case is trivially satisfied since Z(x; δ) is the intersection of sets including the lower-level feasible set. If f (x, •) is radially unbounded, for any finite δ > 0, there is a maximum radius around v beyond which any value of the objective function is greater than f (x, v) + δ. The third case follows the same line of reasoning as the second, with a lower bound in any direction y → ∞, such that this lower bound is above f (x, v) + δ.

The radius of robust feasibility is defined as the maximum "size" of the uncertain set [START_REF] Liers | Radius of robust feasibility for mixed-integer problems[END_REF][START_REF] Goberna | Radius of robust feasibility formulas for classes of convex programs with uncertain polynomial constraints[END_REF], such that the robust problem remains feasible. In the case of near-optimal robustness, the radius can be interpreted as the maximum deviation of the lower-level objective from its optimal value, such that the near-optimal robust bilevel problem remains feasible.

Definition 1 For a given optimization problem BiP , let N O(BiP ; δ) be the optimum value of the near-optimal robust problem constructed from BiP with a tolerance δ. The radius of near-optimal feasibility δ is defined by:

δ = arg max δ {δ s.t. N O(BiP ; δ) < ∞}. (9)
It is interesting to note that the radius as defined in Definition 1 can be interpreted as a maximum robustness budget in terms of objective value of the lower level. It represents the maximum level of tolerance of the lower level on its objective, such that the upper level remains feasible.

Proposition 3

The standard optimistic bilevel problem BiP is a relaxation of the equivalent near-optimal robust bilevel problem for any δ > 0.

Proof By introducing additional variables

z jk , j ∈ [[n l ]], k ∈ [[m u ]
] in the optimistic bilevel problem, we obtain:

min x,v,z F (x, v) (10)
s.t. G k (x, v) ≤ 0 ∀k ∈ [[m u ]] f (x, v) ≤ φ(x) g(x, v) ≤ 0 x ∈ X , v ∈ R n l , z ∈ R n l ×mu .
Problem [START_REF] Jain | Robust solutions in stackelberg games: Addressing boundedly rational human preference models[END_REF] is strictly equivalent to the optimistic bilevel problem with additional variables z that are not used in the objective nor constraints. Furthermore, it is a relaxation of Problem [START_REF] Simon | Theories of bounded rationality[END_REF], which has similar variables but additional constraints (6d). At each point where the bilevel problem is feasible, either the objective value of the two problems are the same or NORBiP is infeasible.

Proposition 4 If the bilevel problem is feasible, then the adversarial problem (5) is feasible.

Proof If the bilevel problem is feasible, then the solution z = v is feasible for the primal adversarial problem.

Proposition 5 If (x, ŷ) is a bilevel-feasible point, and G k (x, •) is K k -Lipschitz continuous for a given k ∈ [[m u ]] such that: G k (x, ŷ) < 0, then the constraint G k (x, y) ≤ 0 is satisfied for all y ∈ F (k)
L such that:

F (k) L (x, ŷ) = {y ∈ R n l | y -ŷ ≤ |G k (x, ŷ)| K k }.
Proof As G k (x, ŷ) < 0, and G k (x, •) is continuous, there exists a ball B r (ŷ) in R n l centered on (ŷ) of radius r > 0, such that G(x, y) ≤ 0 ∀y ∈ B r (ŷ).

Let us define:

r 0 = arg max r r (11)
s.t. G(x, y) ≤ 0 ∀y ∈ B r (ŷ).
By continuity, Problem [START_REF] Pita | Robust solutions to stackelberg games: Addressing bounded rationality and limited observations in human cognition[END_REF] always admits a feasible solution. If the feasible set is bounded, there exists a point y 0 on the boundary of the ball, such that G k (x, y 0 ) = 0. It follows from Lipschitz continuity that:

|G k (x, ŷ) -G k (x, y 0 )| ≤ K k y 0 -ŷ |G k (x, ŷ)| K k ≤ y 0 -ŷ . G k (x, y) ≤ G k (x, y 0 ) ∀y ∈ B r0 (ŷ)
, therefore all lower-level solutions in the set

F (k) L (x, ŷ) = {y ∈ R n l s.t. y -ŷ ≤ |G k (x, ŷ)| K k } satisfy the k-th constraint.
Corollary 1 Let (x, ŷ) be a bilevel-feasible solution of a near-optimal robust bilevel problem of tolerance δ, and

F L (x, ŷ) = mu k=1 F (k) L (x, ŷ), then Z(x; δ) ⊆ F L (x, ŷ
) is a sufficient condition for near-optimal robustness of (x, ŷ).

Proof Any lower-level solution y ∈ F L (x, ŷ) satisfies all m u upper-level constraints, thus Z(x; δ) ⊆ F L (x, ŷ) is a sufficient condition for the near-optimality robustness of (x, ŷ).

Corollary 2 Let (x, ŷ) be a bilevel-feasible solution of a near-optimal robust bilevel problem of tolerance δ, R be the radius of the lower-level feasible set and G k (x, •) be K k -Lipschitz for a given k, then the k-th constraint is robust against near-optimal deviations if:

|G k (x, ŷ)| ≤ K k R.
Proof The inequality can be deduced from the fact that y -ŷ ≤ R.

Corollary 2 can be used when the lower level feasible set is bounded to verify near-optimal robustness of incumbent solutions.

3 Near-optimal robust bilevel problems with a convex lower level

In this section, we study near-optimal robust bilevel problems where the lowerlevel problem (1d) is a parametric convex optimization problem with both a differentiable objective function and differentiable constraints. If Slater's constraint qualifications hold, the KKT conditions are necessary and sufficient for the optimality of the lower-level problem and strong duality holds for the adversarial subproblems. These two properties are leveraged to reformulate NORBiP as a single-level closed-form problem.

Given a bilevel solution (x, v), the adversarial problem associated with constraint k can be formulated as:

max y G k (x, y) (12a) s.t. g(x, y) ≤ 0 (12b) f (x, y) ≤ f (x, v) + δ. ( 12c
)
Even if the upper-level constraints are convex with respect to y, Problem ( 12) is in general non-convex since the function to maximize is convex over a convex set. First-order optimality conditions may induce several non-optimal critical points and the definition of a solution method needs to rely on global optimization techniques [START_REF] Pardalos | Methods for global concave minimization: A bibliographic survey[END_REF][START_REF] Benson | A branch and bound-outer approximation algorithm for concave minimization over a convex set[END_REF].

By assuming that the constraints of the upper-level problem G k (x, y) can be decomposed and that the projection onto the lower variable space is affine, the adversarial problem:

G k (x, y) ≤ 0 ⇔ G k (x) + H T k y ≤ q k , (13)
is convex. The k-th adversarial problem is then expressed as:

max y H k , y (14a)
s.t. g i (x, y) ≤ 0 ∀i ∈ [[m l ]] (α i ) (14b) f (x, y) ≤ f (x, v) + δ (β) (14c)
and is convex for a fixed pair (x, v). Satisfying the upper-level constraint in the worst-case requires that the objective value of Problem ( 14) is lower than q k -G k (x). We denote by A k and D k the objective values of the adversarial problem [START_REF] Zare | On bilevel optimization with inexact follower[END_REF] and its dual respectively. D k takes values in the extended real set to account for infeasible and unbounded cases. Proposition 4 holds for Problem [START_REF] Zare | On bilevel optimization with inexact follower[END_REF]. The feasibility of the upper-level constraint with the dual adversarial objective value as formulated in Constraint ( 15) is, by weak duality of convex problems, a sufficient condition for the feasibility of a near-optimal solution. If Slater's constraint qualifications hold, it is also a necessary condition [START_REF] Boyd | Convex optimization[END_REF] by strong duality:

A k ≤ D k ≤ q k -G k (x). (15)
The generic form for the single-level reformulation of the near-optimal robust problem can then be expressed as:

min x,v,α,β F (x, v) (16a) s.t. G(x) + Hv ≤ q (16b) f (x, v) ≤ φ(x) (16c) g(x, v) ≤ 0 (16d) D k ≤ q k -G k (x) ∀k ∈ [[m u ]] (16e)
x ∈ X ,

where (α, β) are certificates of the near-optimality robustness of the solution.

In order to write Problem ( 16) in a closed form, the lower-level problem (16c-16d) is reduced to its KKT conditions:

∇ v f (x, v) - m l i=1 λ i ∇ v g i (x, v) = 0 (17a) g i (x, v) ≤ 0 ∀i ∈ [[m l ]] (17b)
λ i ≥ 0 ∀i ∈ [[m l ]] (17c)
λ i g i (x, v) = 0 ∀i ∈ [[m l ]]. (17d)
Constraint (17d) derived from the KKT conditions cannot be tackled directly by non-linear solvers [START_REF] Dempe | Computing locally optimal solutions of the bilevel optimization problem using the kkt approach[END_REF]. Specific reformations, such as relaxations of the equality constraints (17d) into inequalities or branching on combinations of variables (as developed in [START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF][START_REF] Schewe | Computing feasible points for binary MINLPs with MPECs[END_REF]) are often used in practice.

We focus in the rest of this section on bilevel problems such that the lower level is a conic convex optimization problem. Unlike the convex version developed above, the dual of a conic optimization problem can be written in closed form.

min y d, y (18)
max y H k , y (19a)
s.t. By = b -Ax (19b) d, y + r = d, v + δ (19c) y ∈ K (19d) r ≥ 0 ( 19e
)
where r is a slack variable used to formulate the near-optimality constraint in standard form. With the following change of variables:

ŷ = y r B = B 0 d = d 1 Ĥk = H k 0 K = {(y, r), y ∈ K, r ≥ 0}.
K is a cone as the Cartesian product of K and the nonnegative orthant. Problem ( 19) is reformulated as:

max ŷ Ĥk , ŷ s.t. ( B ŷ) i = b i -(Ax) i ∀i ∈ [[m l ]] (α i ) d, ŷ = d, v + δ (β) ŷ ∈ K
which is a conic optimization problem, for which the dual problem is:

min α,β,s k (b -Ax), α + ( d, v + δ)β (20a) s.t. BT α + β d + s = Ĥk (20b) s ∈ -K * , (20c)
with K * the dual cone of K. In the worst case (maximum number of non-zero coefficients), there are (m l •n u +n l ) of these terms in m u non-linear non-convex constraints. This number of bilinear terms can be reduced by introducing the following variables (p, o), along with the corresponding constraints:

min α,β,s,p,o p, α + (o + δ)β (21a) s.t. p = b -Ax (21b) o = d, v (21c) BT α + β d + s = Ĥk (21d) s ∈ -K * . ( 21e
)
The number of bilinear terms in the set of constraints is thus reduced from n u • m l + n l to m l + 1 terms in (21a). Problem [START_REF] Loridan | Weak via strong Stackelberg problem: New results[END_REF] or equivalently Problem (21) have a convex feasible set but a bilinear non-convex objective function.

The KKT conditions of the follower problem [START_REF] Gabrel | Recent advances in robust optimization: An overview[END_REF] are given for the primal-dual pair (x, λ):

By = b -Ax (22a) y ∈ K (22b) d -B T λ ∈ K * (22c) d -B T λ, y = 0. (22d)
The single-level problem is:

min x,v,λ,α,β,s F (x, v) (23a) s.t. G(x) + Hv ≤ q (23b) Ax + Bv = b (23c) d -B T λ ∈ K * (23d) d -B T λ, v = 0 (23e) Ax -b, α k + β k ( v, d + δ) ≤ q k -(Gx) k ∀k ∈ [[m u ]] (23f) BT α k + dβ k + s k = Ĥk ∀k ∈ [[m u ]] (23g) x ∈ X , v ∈ K (23h) s k ∈ -K * ∀k ∈ [[m u ]]. (23i)
The Mangasarian-Fromovitz constraint qualification is violated at every feasible point of Constraint (23e) [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF]. In non-linear approaches to complementarity constraints [START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF][START_REF] Dempe | Computing locally optimal solutions of the bilevel optimization problem using the kkt approach[END_REF], parameterized successive relaxations of the complementarity constraints are used:

d -B T λ, v ≤ ε (24a) -d -B T λ, v ≤ ε. (24b)
Constraints (23f) and ( 24) are both bilinear non-convex inequalities, the other ones added by the near-optimal robust model are conic and linear constraints. Near-optimal robustness has thus only added a finite number of constraints of the same nature (bilinear inequalities) to the reformulation proposed in [START_REF] Dempe | Computing locally optimal solutions of the bilevel optimization problem using the kkt approach[END_REF]. Solution methods used for bilevel problems with convex lower-level thus apply to their near-optimal robust counterpart.

Linear near-optimal robust bilevel problem

In this section, we focus on near-optimal robust linear-linear bilevel problems. More precisely, the structure of the lower-level problem is exploited to derive an extended formulation leading to an efficient solution algorithm.We consider that all vector spaces are subspaces of R n , with appropriate dimensions. The inner product of two vectors a, b is equivalently written a T b.

The linear near-optimal robust bilevel problem is formulated as:

min x,v c T x x + c T y v (25a) s.t. Gx + Hv ≤ q (25b) d T v ≤ φ(x) (25c) Ax + Bv ≤ b (25d) Gx + Hz ≤ q ∀z ∈ Z(x; δ) (25e) v ∈ R n l + (25f) x ∈ X . ( 25g
)
For a given pair (x, v), each semi-infinite robust constraint (25e) can be reformulated as the objective value of the following adversarial problem:

max y H T k y (26a) s.t. (By) i ≤ b i -(Ax) i ∀i ∈ [[m l ]] (α i ) (26b) d T y ≤ d T v + δ (β) (26c)
y ∈ R n l + . (26d)
Let (α, β) be the dual variables associated with each group of constraints (26b-26c). The near-optimal robust version of Problem ( 25) is feasible only if the objective value of each k-th adversarial subproblem [START_REF] Dempe | Computing locally optimal solutions of the bilevel optimization problem using the kkt approach[END_REF] is lower than q k -(Gx) k . The dual of Problem ( 26) is defined as:

min α,β α T (b -Ax) + β (d T v + δ) (27a) s.t. B T α + βd ≥ H k (27b) α ∈ R m l + β ∈ R + . (27c)
Based on Problem (4) and weak duality results, the dual problem is either infeasible or feasible and bounded. By strong duality, the objective value of the dual and primal problems are equal. This value must be smaller than q k -(Gx) k to satisfy Constraint (25e). This is equivalent to the existence of a feasible dual solution (α, β) certifying the feasibility of (x, v) within the near-optimal set Z(x; δ). We obtain one pair of certificates (α, β) for each upper-level constraint in [[m u ]], resulting in the following problem:

min x,v,α,β c T x x + c T y v (28a) s.t. Gx + Hv ≤ q (28b) d T v ≤ φ(x) (28c) Ax + Bv ≤ b (28d) α T k (b -Ax) + β k (d T v + δ) ≤ q k -(Gx) k ∀k ∈ [[m u ]] (28e)
B T α k + β k d ≥ H k ∀k ∈ [[m u ]] (28f) α k ∈ R m l + β k ∈ R + ∀k ∈ [[m u ]] (28g) v ∈ R n l + (28h) x ∈ X . (28i)
Lower-level optimality is guaranteed by the corresponding KKT conditions:

d j + i B ij λ i -σ j = 0 ∀j ∈ [[n l ]] (29a) 0 ≤ b i -(Ax) i -(Bv) i ⊥ λ i ≥ 0 ∀i ∈ [[m l ]] (29b) 0 ≤ v j ⊥ σ j ≥ 0 ∀j ∈ [[n l ]] (29c) σ ≥ 0, λ ≥ 0 (29d)
where ⊥ defines a complementarity constraint. A common technique to linearize Constraints (29b-29c) is the "big-M" reformulation, introducing auxiliary binary variables with primal and dual upper bounds. The resulting formulation has a weak continuous relaxation. Furthermore, the correct choice of bounds is itself an NP-hard problem [START_REF] Kleinert | There's no free lunch: On the hardness of choosing a correct big-m in bilevel optimization[END_REF], and the incorrect choice of these bounds can lead to cutting valid and potentially optimal solutions [START_REF] Pineda | Solving linear bilevel problems using big-ms: Not all that glitters is gold[END_REF]. Other modelling and solution approaches, such as special ordered sets of type 1 (SOS1) or indicator constraints avoid the need to specify such bounds in a branch-and-bound procedure.

The aggregated formulation of the linear near-optimal robust bilevel problem is:

min x,v,λ,σ,α,β c T x x + c T y v (30a) s.t. Gx + Hv ≤ q (30b) Ax + Bv ≤ b (30c) d j + i λ i B ij -σ j = 0 ∀j ∈ [[n l ]] (30d) 0 ≤ λ i ⊥ A i x + B i v -b i ≤ 0 ∀i ∈ [[m l ]] (30e) 0 ≤ σ j ⊥ v j ≥ 0 ∀j ∈ [[n l ]] (30f)
x ∈ X (30g)

α k • (b -Ax) + β k (d T v + δ) ≤ q k -(Gx) k ∀k ∈ [[m u ]] (30h) m l i=1 B ij α ki + β k d j ≥ H kj ∀k ∈ [[m u ]], ∀j ∈ [[n l ]] (30i)
α k ∈ R m l + , β k ∈ R + ∀k ∈ [[m u ]]. (30j)
Problem ( 30) is a single-level problem and has a closed form. However, constraints (30h) contain bilinear terms, which cannot be tackled as efficiently as convex constraints by branch-and-cut based solvers. Therefore, we exploit the structure of the dual adversarial problem and its relation to the primal lower level to design a new efficient reformulation and solution algorithm.

Extended formulation

The bilinear constraints (30h) involve products of variables from the upper and lower level (x, v) as well as dual variables of each of the m u dual-adversarial problems. For fixed values of (x, v), m u dual adversarial sub-problems [START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF] are defined. The optimal value of each k-th subproblem must be lower than q k -(Gx) k . The feasible region of each sub-problem is defined by (30h-30j) and is independent of (x, v). The objective functions are linear in (α, β). Following Proposition 4, Problem ( 27) is bounded. If, moreover, Problem ( 27) is feasible, a vertex of the polytope (30h-30j) is an optimal solution. Following these observations, Constraints (30h-30j) can be replaced by disjunctive constraints, such that for each k, at least one extreme vertex of the k-th dual polyhedron is feasible. This reformulation of the bilinear constraints has to the best of our knowledge never been developed in the literature. Let V k be the number of vertices of the k-th sub-problem and α l k , β l k be the l-th vertex of the k-th sub-problem. Constraints (30h-30j) can be written as:

V k l=1 m l i=1 α l ki (b -Ax) i + β l k • (d T v + δ) ≤ q k -(Gx) k ∀k ∈ [[m u ]], (31)
where N i=1 C i is the disjunction (logical "OR") operator, expressing the constraint that at least one of the constraints C i must be satisfied. These disjunctions are equivalent to indicator constraints [START_REF] Bonami | On mathematical programming with indicator constraints[END_REF]. This reformulation of bilinear constraints based on the polyhedral description of the (α, β) feasible space is similar to the Benders decomposition. Indeed in the near-optimal robust extended formulation, at least one of the vertices must satisfy a constraint (a disjunction) while Benders decomposition consists in satisfying a set of constraints for all extreme vertices and rays of the dual polyhedron (a constraint described with a universal quantifier). Disjunctive constraints [START_REF] Kleinert | There's no free lunch: On the hardness of choosing a correct big-m in bilevel optimization[END_REF] are equivalent to the following formulation, using set cover and SOS1 constraints:

θ l k ∈ B ∀k, ∀l (32a)
ω l k ≥ 0 ∀k, ∀l (32b)
(b -Ax) T α l k + β l k (d T v + δ) -ω l k ≤ q k -(Gx) k ∀k, ∀l (32c)
V k l=1 θ l k ≥ 1 ∀k (32d) SOS1(θ l k , ω l k ) ∀k, ∀l. (32e)
In conclusion, using disjunctive constraints over the extreme vertices of each dual polyhedron, and SOS1 constraints to linearize the complementarity constraints leads to an equivalent reformulation of Problem [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF]. The finite solution property holds even though the boundedness of the dual feasible set is not required. This single-level extended reformulation can be solved by any off-the-shelf MILP solver. Nevertheless, to decrease the computation time, we have designed a specific algorithm based on necessary conditions for the existence of a solution.

We illustrate the extended formulation with the following example.

Bounded example

Consider the bilevel linear problem defined by the following data:

x ∈ R + , y ∈ R + G = -1 1 H = 4 2 q = 11 13 c x = 1 c y = -10 A = -2 5 B = -1 -4 b = -5 30 d = 1 .
The optimal solution of the high-point relaxation (x, v) = (5, 4) is not bilevel-feasible. The optimal value of the optimistic bilevel problem is reached at (x, v) = (1, 3). These two points are respectively represented by the blue diamond and red cross in Fig. 3. The dotted segments represent the upper-level constraints and the solid lines represent the lower-level constraints. The (α, β) feasible space is defined as:

-1α 11 -4α 12 + β 1 ≥ 4 -1α 21 -4α 22 + β 2 ≥ 2 α ki ≥ 0, β k ≥ 0.
This feasible space can be described as a set of extreme points and rays. It consists in this case of one extreme point (α ki = 0, β 1 = 4, β 2 = 2) and 4 extreme rays. The (x, v) solution needs to be valid for the corresponding near-optimality conditions:

β 1 (v + δ) ≤ 11 + x β 2 (v + δ) ≤ 13 -x.
This results in two constraints in the (x, v) space, represented in Fig. 4 for δ = 0.5 and δ = 1.0 in dotted blue and dashed orange respectively. The radius of near-optimal feasibility can be computed using the formulation provided in Definition 1, a radius of δ = 5 can be computed, for which the feasible domain at the upper-level is reduced to the point x = 5, for which v = 0, represented as a green circle at (5, 0).

Solution algorithm

The solution procedure is defined as follows based on the structure of the extended formulation. The main goal of the algorithm is to prove infeasibility early in the resolution process and to solve the extended formulation only in the last step. Let P 0 (BiP ), P 1 (BiP ), FEAS k ((BiP ), P no (BiP ; δ) be the highpoint relaxation, optimistic bilevel problem, dual feasibility and near-optimal robust problem respectively. Let C k be the list of extreme vertices of the k-th dual adversarial polyhedron.

Algorithm 1 Near-Optimal Robust Vertex Enumeration Procedure (NORVEP) Each step solves a problem that must be feasible for NORBiP to also be feasible, and terminates the algorithm without proceeding to the subsequent steps in an infeasibility is detected.

Valid inequalities

The extended formulation and Algorithm 1 can be applied directly. Nonetheless, we propose two groups of valid inequalities that can be used to tighten the formulation.

The first group of inequalities consists of the primal upper-level constraints:

(Gx) k + (Hv) k ≤ q k ∀z ∈ [[m u ]].
These constraints are necessary for the optimistic formulation but not for the near-optimal robust formulation since they are always redundant with and included in the near-optimal robust constraints. However, their addition can strengthen the linear relaxation of the extended formulation and lead to faster convergence.

The second group of inequalities is defined in [START_REF] Kleinert | Closing the gap in linear bilevel optimization: A new valid primal-dual inequality[END_REF] and based on strong duality of the lower level. Following the computational results from the paper, we only implement the valid for the root node:

λ, b + v, d ≤ A + , λ , (33)
where A + i is an upper bound on A i , x . The computation of each upper bound A + i relies on solving an auxiliary problem:

max x,v,λ A i , x (34a)
s.t. Gx + Hv ≤ q (34b)

Ax + Bv ≤ b (34c) d + B T λ ≥ 0 (34d) x ∈ X , v ≥ 0, λ (34e)
(x, v, λ) ∈ Υ, (34f)
where Υ is the set containing all valid inequalities [START_REF] Bonami | On mathematical programming with indicator constraints[END_REF]. The method proposed in [START_REF] Kleinert | Closing the gap in linear bilevel optimization: A new valid primal-dual inequality[END_REF] relies on solving each i-th auxiliary problem once. Instead, we compute the best bounds of the root node in an interative procedure detailed in the following steps:

1. Solve Problem (34a) ∀i ∈ [[m l ]] and obtain A + ; 2. If ∃i, A + i is unbounded, terminate; 3. Otherwise, add Constraint [START_REF] Bonami | On mathematical programming with indicator constraints[END_REF] to (34f), go to step 1.

Computational setup

The configuration used in the computational experiments is described below. Algorithm 1 is implemented in Julia [START_REF] Bezanson | Julia: A Fresh Approach to Numerical Computing[END_REF] using the JuMP v0.21 modelling framework [START_REF] Dunning | JuMP: A Modeling Language for Mathematical Optimization[END_REF][START_REF] Legat | MathOptInterface: a data structure for mathematical optimization problems[END_REF]; the MILP solver is SCIP 6.0 [START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF] with SoPlex 4.0 as the inner LP solver, both with default solving parameters. SCIP handles indicator constraints in the form of linear inequality constraints activated only if a binary variable is equal to one. Polyhedra.jl [START_REF] Legat | 0.5.1[END_REF] is used to model the dual subproblem polyhedra with CDDLib [START_REF] Legat | JuliaPolyhedra/CDDLib[END_REF] as a solver running the double-description algorithm, computing the list of extreme vertices and rays from the constraintbased representation. The exact rational representation of numbers is used in CDDLib instead of floating-point types to avoid rounding errors. Moreover, CDDLib fails to produce the list of vertices for some instances when set in floating-point mode. All experiments are performed on a consumer-end laptop with 15.5GB of RAM and an Intel i7 1.9GHz CPU running Ubuntu 18.04LTS.

Bilinear and extended formulation

To assess the efficiency of the extended formulation, we compare its solution time to that of the non-extended formulation including bilinear constraints [START_REF] Boyd | Convex optimization[END_REF]. The bilinear formulation is implemented with SCIP using SoPlex as the linear optimization solver and Ipopt as the non-linear solver. SCIP handles the bilinear terms through bound computations and spatial branching. We test the two methods on 100 small instances. The bilinear version only manages to solve the small random instances and runs out of time or memory for all other instance sets. A time limit of 3600 seconds and a memory limit of 5000MB were fixed. The distribution of runtimes is presented in Fig. 5. The extended formulation with the disjunction dominates at almost any time the bilinear formulation that uses spatial branching. The latter runs out of time or memory for most instances.

Robustness of optimistic solutions and influence of δ

We solve the MIPS instances to bilevel optimality and verify the near-optimal robustness of the obtained solutions. We use various tolerance values:

δ = max(0.05, δ r o)
with o the lower-level objective value at the found solution and δ r ∈ (0.01, 0.05, 0.1, 0.5, 3.0).

Out of the 100 instances, 57 have canonical solutions that are not robust to even the smallest near-optimal deviation 0.01o. Twelve more instances that have a near-optimal robust solution with the lowest tolerance are not nearoptimal robust when the tolerance is increased to 3o Out of the 57 instances that are not near-optimal robust with the lowest tolerance, 40 have exactly one upper-level constraint that is violated by near-optimal deviations of the lower level and 17 that have more than one. Finally, we observe 31 instances out of 100 for which the number of violated constraints changes across the range of tolerance values. For the other 69 instances, the number of violated upper-level constraints remains identical for all tolerance values. Table 1 summarizes the number of infeasible instances for different values of δ. As δ increases, so does the proportion of infeasible problems. This is due to the increase in the left-hand side in constraints [START_REF] Kleinert | There's no free lunch: On the hardness of choosing a correct big-m in bilevel optimization[END_REF] In Fig. 6, we present the runtime difference between the canonical bilevel problem and its near-optimal robust counterpart.

Scaling up the dimension of the tackled problems is limited not only by time but also by memory since the formulation of the problem requires allocating binary variables and a disjunctive constraint over all vertices of the dual polyhedron of each of the k ∈ [[m u ]] subproblems. These runtime profiles highlight the fact that near-optimality robustness implemented using the extended formulation adds a significant runtime cost to the resolution of linear-linear bilevel problems. Nonetheless, the study of near-optimal lower-level decisions on optimistic solutions shows that these optimistic solutions are not robust, even for small tolerance values. This time difference also motivates the design of Algorithm 1: since the optimistic bilevel problem is solved in a much shorter time, it is interesting to verify its feasibility before solving the near-optimal robust version.

Computational time of the algorithm

Statistics on the computation times of the two phases of Algorithm 1 for each instance size are provided in Table 2 The solution time, corresponding to phase 2 of Algorithm 1, is greater than the vertex enumeration phase, corresponding to the first phase of the algorithm, but does not dominate it completely for any of the problem sizes.

Figure 7 shows the distribution of the upper-level objective values across small and medium-sized instances. The number of problems solved to optimality monotonically decreases when δ increases (Table 1); greater δ values indeed make reduce the set of feasible solutions to NORBiP. The optimal values only slightly increase with δ and the lower-level objective value does not vary significantly with δ. Even though more instances become infeasible as δ increases, the degradation of the objective value is in general insignificant for the optimal nearoptimal robust solution compared to the optimistic solution.

Implementation of valid inequalities

In the last group of experiments, we implement and investigate the effect of the valid inequalities defined in Section 4.4.

On the 200 medium-sized instances, adding the valid inequality ( 33) is enough to prove infeasibility of 61 instances out of 68 that are infeasible but possess a feasible high-point relaxation. On 100 large instances, adding the valid inequality proves the infeasibility of 29 out of 45 infeasible instances for which the high-point relaxation is feasible. For all medium and large instances, a non-trivial valid inequality i.e. where all A + i are finite was computed. These results highlight the improvement of the model tightness with the addition of the valid inequalities, compared to the high-point relaxation where primal and dual variables are subject to distinct groups of constraints. These inequalities thus discard infeasible instances without the need to solve the complete MILP reformulation. In Fig. 8, the distribution of the number of iterations of the inequality-finding procedure is presented for the medium and large instances. For the majority of instances of both sizes (about 80% and 60% of instances for the medium and large instances), a single iteration is sufficient to find the best valid inequality [START_REF] Bonami | On mathematical programming with indicator constraints[END_REF]. The number of iteration, however, goes up to 40 and 50 for the medium and large instances respectively (truncated on the graph for clarity).

In Fig. 9, we compare the total runtime for MIPS and medium instances under near-optimal robustness constraints using δ = 0.1 with and without valid inequalities for all instances solved to optimality. The runtime for instances with valid inequalities includes the runtime of the inequality computation. Valid inequalities do not improve the runtime for NORBiP in either group of instances, a result similar to the observations in [START_REF] Kleinert | Closing the gap in linear bilevel optimization: A new valid primal-dual inequality[END_REF] for instances of the canonical bilevel linear problem without near-optimality robustness.

The inequalities based on the upper-level constraints are studied on the small, medium and MIPS instances.

As shown in Fig. 10, the addition of primal upper-level constraints accelerates the resolution of the MIPS and medium instances and dominates the standard extended formulation. For the small instances, we observe smaller runtimes for the first instances solved. This can be due to the upper-level constraints making the linear relaxation larger by adding constraints, thus creating overhead for smaller problems. This overhead is compensated for instances that are harder to optimize, i.e. that require more than 0.02 seconds to solve.

Conclusion

This paper introduces near-optimal robust bilevel optimization, a specific formulation of bilevel optimization where the upper level is protected from potential deviations of the lower level from optimality. From a robust optimization perspective, the tolerance δ of the lower level on its objective value can be interpreted as an uncertainty budget with the same dimension as the lower-level objective value. The near-optimal robust formulation is a generalization of the constraint-based pessimistic bilevel problem, and more specifically of the dependent case where the upper-and lower-level constraints depend on both upper-and lower-level variables. The model offers a complement to bilevel optimization by relaxing the assumption that the lower level is solved to exact optimality.

A closed-form, single-level expression of NORBiP is developed for convex lower-level problems, relying on the lower-level KKT conditions and dual adversarial certificates to guarantee near-optimality robustness. In the linear case, characterization of optimal solutions of the primal and dual adversarial solutions are leveraged to derive an extended formulation that can be represented as a MILP with disjunctive constraints.

Numerical experiments highlight the efficiency of the extended method compared to the compact bilinear formulation, the impact of some valid inequalities on both solution time and model tightness, and the influence of near-optimality robustness on the upper-level objective and solution time.

Although the novel extended formulation relies on the specific properties of optimal solutions to the dual adversarial problem, its application to other problems with bilinear constraints could be of interest for future investigation. Future work will also tackle the design of solution methods to handle more general near-optimal robust convex bilevel problems and accelerate the resolution of linear instances based on the extended formulation.

  s.t. Ax + By = b y ∈ Kwhere •, • is the inner product associated with the space of the lower-level variables. This class encompasses a broad class of convex optimization problems of practical interest[START_REF] Nesterov | Interior-point polynomial algorithms in convex programming[END_REF] Chapter 4], while the dual problem can be written in a closed-form if the dual cone is known, letting us derive a closed-form singlelevel reformulation. K is considered to be a proper cone in the sense of[START_REF] Boyd | Convex optimization[END_REF] Chapter 2]. The k-th adversarial problem is given by:

Fig. 3 5 Fig.

 35 Fig. 3 Representation of the bilevel problem.

Fig. 5

 5 Fig. 5 Runtime of the two methods on 100 of the small instances

Fig. 6

 6 Fig.6Runtime cost of adding near-optimality robustness constraints.

Fig. 7

 7 Fig. 7 Violin plots of the upper objective value distributions versus δ.

Fig. 8

 8 Fig.8Distribution of the number of iterations for the computation of valid inequalities.

Fig. 9

 9 Fig.9Runtime for MIPS and medium instances with and without valid inequalities.

Fig. 10

 10 Fig. 10 Runtime for small, medium and MIPS instances with and without upper-level constraints.

Table 1

 1 . Number of infeasible problems for various tolerance levels δ

	δ	0.01	0.1	0.2	1	3	5	7	10	12
	Small (/1000)	366	423	466	595	658	670	672	674	676
	Medium (/200)	78	88	95	118

Table 2

 2 and Table3. Runtime statistics for the vertex enumeration (s).

	Size	mean	10% quant. 50% quant. 90% quant.
	Small	0.023	0.014	0.019	0.046
	Medium	1.098	0.424	0.956	2.148
	MIPS	21.061	0.231	3.545	65.004
	Instance type	# optimized	mean	10% quant. 50% quant. 90% quant.
	Small		577	0.205	0.004	0.064	0.596
	Medium		106	207.399	0.797	14.451	317.624
	MIPS		70	909.302	57.592	344.202	2613.404

Table 3

 3 Runtime statistics for the optimization phase (s).

4. When an iteration does not improve any of the bounds, terminate and return the last inequality with the sharpest bound.

This allows us to tighten the bound as long as improvement can be made in one of the A + i . If the procedure terminates with one A + i unbounded, the right-hand side of ( 33) is +∞, the constraint is trivial and cannot be improved upon. Otherwise, each iteration improves the bound until the convergence of A + . A computational study of these two groups of inequalities is presented in the next section.

Computational experiments

In this section, we demonstrate the applicability of our approach through numerical experiments on instances of the linear-linear near-optimal robust bilevel problem. We first describe the sets of test instances and the computational setup and then the experiments and their results. All matrices are randomly generated with each coefficient having a 0.6 probability of being 0 and uniformly distributed on [0, 1] otherwise. High-point feasibility and the vertex enumeration procedures are run after generating each tuple of random parameters to discard infeasible instances. Collecting 1000 small instances required generating 10532 trials, the 200 medium-sized instances were obtained with 18040 trials and the 100 large instances after 90855 trials. A second dataset is created from the 50 MIPS/Random instances of the Bilevel Problem library [START_REF] Ralphs | Bilevel Optimization Problem Library v0.1[END_REF], where integrality constraints are dropped. All of these instances contain 20 lower-level constraints and no upper-level constraints. For each of them, two new instances are built by moving either the first 6 or the last 6 constraints from the lower to the upper level, resulting in 100 instances. We will refer to the first set of instances as the small/medium/large instances and the second as the MIPS instances. All instances are available in [START_REF] Besançon | Near-optimal robust bilevel linear instances[END_REF] in JLD format, along with a reader to import them in Julia programs.