Boris Detienne
email: boris.detienne@u-bordeaux.fr

Henri Lefebvre
email: henri.lefebvre@unibo.it

Enrico Malaguti
email: enrico.malaguti@unibo.it

Michele Monaci
email: michele.monaci@unibo.it

Adaptive robust optimization with objective uncertainty

Keywords: two-stage robust optimization, reformulation, Fenchel duality, column generation, branch-and-bound, computational experiments

In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and involve mixed-integer variables, thus extending the existing literature to a much wider class of problems. We show how these problems can be reformulated using Fenchel duality, allowing to derive an enumerative exact algorithm, for which we prove -convergence in a finite number of operations. An implementation of the resulting algorithm, embedding a column generation scheme, is then computationally evaluated on two different problems, using instances that are derived starting from the existing literature. To the best of our knowledge, this is the first approach providing results on the practical solution of this class of problems.

Introduction

Robust Optimization (RO) has emerged as a solution approach to deal with uncertainty in optimization problems. Contrary to stochastic optimization, another popular approach that relies on probability distributions, robust optimization considers an uncertainty set for the unknown parameters, against which the taken decision should be immune. In that sense, constraints have to be respected in every possible realization of the parameters and the objective function evaluated in the least advantageous case. The concept was first introduced in [START_REF] Soyster | Technical note-convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF] and received considerable attention in the scientific literature. Recent advances in RO can be found in Bertsimas et al (2010), [START_REF] Hassene | Min-max and min-max regret versions of combinatorial optimization problems: A survey[END_REF], [START_REF] Ben-Tal | Robust Optimization[END_REF], [START_REF] Leyffer | A survey of nonlinear robust optimization[END_REF] and [START_REF] Yanıkoglu | A survey of adjustable robust optimization[END_REF], among others.

More formally, a basic robust optimization problem can be cast as follows:

inf z z z sup ξ ξ ξ∈Ξ f (ξ ξ ξ, z z z)
subject to g g g(ξ ξ ξ, z z z) ≤ 0 ∀ξ ξ ξ ∈ Ξ z z z ∈ Z (1SR-P)

Here, the unknown data is represented by variables ξ ξ ξ that belong to the socalled uncertainty set Ξ. As mentioned above, decision z z z has to be feasible in every possible occurrence of the uncertainty, hence robust solutions tend to be overly conservative. To tackle this drawback, so-called adjustable robust optimization [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], also known as two-stage robust optimization, was introduced. As its name suggests, in a two-stage context, part of the decisions are made in a here-and-now phase (i.e., before uncertainty reveals), while recourse decisions can be taken in a wait-and-see phase (i.e., once the actual values of the uncertain data are known) as an attempt to react to the outcome of the uncertain process. Typically, the feasible space of (1SR-P) can, indeed, be recast to embed a two-stage decision process by splitting variables z z z in (x x x, y y y) and defining set Z as X ×Y accordingly. With the convention that the minimum objective function value for an infeasible problem is +∞, a two-stage robust problem can be formulated as follows: where Y(x x x, ξ ξ ξ) = {y y y : y y y ∈ Y, g g g(ξ ξ ξ, x x x, y y y) ≤ 0}, and g g g(ξ ξ ξ, x x x, y y y) ≤ 0 are the so-called linking constraints. Set X is now referred to as the first-stage feasible space. Given x x x ∈ X and ξ ξ ξ ∈ Ξ, the corresponding second-stage feasible space is Y(x x x, ξ ξ ξ), and the second-stage problem is inf{f (ξ ξ ξ, x x x, y y y) : y y y ∈ Y(x x x, ξ ξ ξ)}.

It is known [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] that problems which can be cast as twostage robust problems often are at least NP-hard, even in the case where first and second stage variables are continuous and all the involved functions are linear. Several approaches have been developed to tackle this class of problems. Assuming that the second stage is continuous and exhibits strong duality, it can be replaced by its dual. This way, the inner maximization problem can be reformulated using its epigraph, leading to a constraintgeneration algorithm in the spirit of Benders' decomposition (see, e.g., [START_REF] Terry | Robust linear optimization with recourse[END_REF], [START_REF] Bertsimas | Adaptive robust optimization for the security constrained unit commitment problem[END_REF], [START_REF] Jiang | Two-stage network constrained robust unit commitment problem[END_REF] and [START_REF] Gabrel | Robust location transportation problems under uncertain demands[END_REF].

A column-and-constraint-generation scheme has been proposed in [START_REF] Zeng | Solving two-stage robust optimization problems by a column-and-constraint generation method[END_REF], which consists in adding one set of recourse decision variables and the corresponding second-stage constraints associated with a realization of the uncertainty. These realizations are dynamically generated by solving a bilevel problem. Later, the same approach was used in [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF], where the constraint-generation problem was modelled as a mixed integer program exploiting a description of the uncertainty set in terms of its extreme points. Note that this method can handle mixed-integer second-stage decisions, which is not the case for classical Benders-type approaches. Unfortunately, this method seems to be of practical relevance only when a small number of variables has to be added for reaching optimality.

The inherent difficulty of this class of problems motivated the development of approximate solution methods. In the affine decision rule approach proposed in [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], the recourse decisions are expressed as affine functions of the uncertainty. Another relevant approach, introduced in Bertsimas and Caramanis (2010), is the finite adaptability (also known as K-adaptability) in which the number of recourse decisions is restricted to some finite number. An MILP formulation for the case of binary second-stage decisions and objective uncertainty was proposed in [START_REF] Hanasusanto | K-adaptability in two-stage robust binary programming[END_REF] and a branch-and-bound algorithm was later proposed in [START_REF] Subramanyam | K-adaptability in two-stage mixed-integer robust optimization[END_REF] to address cases with uncertain linear constraints.

An important special case of (2SR-P) arises when uncertainty affects the objective function only, i.e., Y(x x x, ξ ξ ξ) = Y(x x x), ∀ξ ξ ξ ∈ Ξ. For this specific case, [START_REF] Kämmerling | Oracle-based algorithms for binary twostage robust optimization[END_REF] proposed an oracle-based algorithm relying on a hull relaxation combining the first-and second-stage feasible spaces embedded within a branch-and-bound framework. However, this approach applies to purely binary variables and linear constraints only. On the other hand, [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF] proposed an exact MILP reformulation of the problem in case of linear linking constraints that involve binary variables only. Besides solving the problem by means of a branch-and-price algorithm, a further contribution of [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF] is proving the NP-completeness of the problem in this setting.

In the setting where uncertainty affects the objective function only, our analysis shows that further effort is needed to tackle with more general cases, in particular when linking constraints are defined by nonlinear functions or involve both integer and continuous variables. Similarly, to the best of our knowledge, the case in which the objective function is nonlinear has not been considered yet. This paper contributes in filling this gap, as we consider two-stage robust problems with objective uncertainty, convex constraints and mixed-integer first and second stage. By extending in a non-trivial way some recent results from the two-stage stochastic optimization literature (see [START_REF] Sherali | A modification of Benders' decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse[END_REF], [START_REF] Sherali | On solving discrete two-stage stochastic programs having mixed-integer first-and second-stage variables[END_REF] and [START_REF] Li | A finite ε-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and secondstage variables[END_REF]), we obtain a relaxation of the problem, and analyze its tightness for different special cases. This relaxation can be embedded within a branch-andbound scheme thus producing an exact solution approach, for which we prove finite ε-convergence. Besides the theoretical analysis, we also show that, from a computational viewpoint, the proposed algorithm is able to solve instances of practical relevance arising from two different applications. We also point out that the class of problems which can be addressed by our solution approach is quite large since we only require mild assumptions on the nature of the involved optimization problem.

The article is organized as follows. In Section 2 we formally introduce the class of problems we are considering throughout this work, whereas Section 2.2 describes in greater details the algorithmic solution approach proposed in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF] for a special case of our problem. In Section 3 we present a relaxation of the problem, and an effective algorithm for its solution. We then derive sufficient conditions for the relaxation to coincide with the original problem in a mixed-integer context. In the purely binary case, the equivalence between problem (2SRO-P) and our lower-bounding problem is established without any condition. We then present a branch-and-bound algorithm able to close the optimality gap with finite ε-convergence assuming that the lower-bounding problem can be finitely solved with ε tolerance. In section 3.4, we propose a column-generation algorithm to solve the lowerbounding problem with such property. Finally, section 4 applies the proposed algorithm to two problems: a capital budgeting problem and a capacitated facility location problem.

Notations Throughout this paper, matrices and vectors are written in bold case, e.g., x x x ∈ R n or A A A ∈ R n×m , while components are written in normal font, e.g., x i or a ij . Columns of A A A are written in bold case with exponent indexing, e.g., a a a i . Let f : R n → R be a given function with dom(f ) = {x x x ∈ R n : f (x x x) < +∞}; its convex conjugate is denoted by f * : R n → R and is given by

f * (π π π) = sup x x x∈dom(f ) {π π π T x x x -f (x x x)}
Similarly, we denote by f * the concave conjugate of f . Let X ⊆ R n × {0, 1} n-p be a given set, we denote X its continuous relaxation, i.e., X = X ∩ R n × {0, 1} n-p , conv (X) its convex hull, i.e., the smallest convex set C satisfying X ⊆ C.

The indicator function of X is noted δ( • |X) and equals zero if its argument belongs to X and +∞ otherwise. Its convex conjugate is therefore given by δ * (π π π|X) = sup{π π π T x x x : x x x ∈ X}. If X is a convex polytope, we note vert (X) the set of its extreme points. Finally, for a logical proposition E, function 1 1 1(E) equals one if E is true and zero otherwise.

Problem description

General setting

As anticipated, our goal is to solve problem (2SR-P) with objective uncertainty, convex constraints and mixed-integer first and second stages.

For the sake of clarity, let us first introduce several sets. Set I = {1, . . . , n 1 } denotes the set of indices for the first-stage variables, and is partitioned into two sets I B and I C : variables whose index belongs to I B are required to take binary values, while those whose index belongs to I C are continuous variables, i.e., wlog, X ⊂ R |I C | × {0, 1} |I B | . Similarly, we introduce set J = {1, . . . , n 2 } as the indices for the second-stage variables and partition this set into J B and J C , i.e., wlog, Y ⊂ R |J C | × {0, 1} |J B | . Sets I B and J B , which correspond to binary first and second-stage binary variables, may be defined in the same way in case of general integer variables; all the results presented in the paper directly extend to the integer case as well. Finally, we introduce set U = {1, . . . , n 3 } as the index set for the uncertain variables, i.e., Ξ ⊂ R n3 .

We now explicit some assumptions on the problem.

2. For all i ∈ Q, ψ i is separable in ξ ξ ξ and (x x x, y y y) meaning that there exists functions (w i : R |U | → R) i∈Q and (ϕ i : R |I|+|J| → R) i∈Q such that ψ i (ξ ξ ξ, x x x, y y y) = w i (ξ ξ ξ)ϕ i (x x x, y y y). In addition, we assume that w i (•) is a concave function and ϕ i (•) is a convex function.

A few remarks regarding these assumptions are necessary. First, note that Assumptions 1 and 2 are here to define what we refer to as convex mixedinteger robust problems with objective uncertainty. It is important to highlight that the word "convex" is here to suggest that all involved functions are convex with respect to the first-and second-stage variables. Yet, in general, even under these assumptions, problem (2SR-P) may fail to have a straightforward convex MINLP formulation, as function h : x x x → max ξ ξ ξ∈Ξ min y y y∈Y(x x x) f (ξ ξ ξ, x x x, y y y) is not necessarily a convex function over the continuous relaxation of X . We give here a small example.

Example 1 (nonconvex MINLP) Consider the following first-and second-stage feasible regions:

X = [0, 1] and Y(x) = y y y ∈ {0, 1} 2 y 1 + y 2 ≤ 1 y 1 ≤ 1 -x
By inspection, we have that (y 1 , y 2 ) = (0, 0) and (y 1 , y 2 ) = (0, 1) are always feasible second-stage solutions, while (y 1 , y 2 ) = (1, 0) is feasible only when x = 0. Fixing the uncertainty set Ξ = [0, 1], we take interest in the following convex mixed-integer two-stage robust problem:

min x∈[0,1] h(x) with h : x → max ξ∈[0,1] min (y1,y2)∈Y(x)
ξ(-2y 1 + y 2 + 1)

Though every involved functions are convex (in fact, affine), the following holds:

h(x) =      max ξ∈[0,1] min {ξ; 2ξ; -ξ} = 0 if x = 0 max ξ∈[0,1] min {ξ; 2ξ} = 1 if x > 0 = 1 1 1(x > 0)
Clearly, h fails to be convex over [0, 1] which ends our example.

Assumption 3 is a standard assumption in the two-stage optimization literature, and is known to be easy to enforce as soon as the considered problem is bounded, which is implied by Assumption 4.1. Assumption 4.2 is not restrictive in practice, and will be used in the proof of lemma (2).

Finally, Assumption 5 is structural to our work, and implies the following remark.

Remark 1 Without loss of generality, for all i ∈ Q, we can assume that ϕ i (•) is a convex function (at most affine).

Proof Let i ∈ Q such that ϕ i (•) is concave, then, to fulfill Assumption 2.1, w i (ξ ξ ξ) must be negative forall ξ ξ ξ ∈ Ξ. Thus, one may equivalently replace w i (•) by -w i (•) and ϕ i (•) by -ϕ i (•).

Remark 2 For all i ∈ Q such that ϕ i (•) (resp. w i (•)) is not single-signed, then w i (•) (resp. ϕ i (•)) is affine. Remark 3 For all i ∈ Q such that ϕ i (•) (resp. w i (•)) is not affine, then w i (•) (resp. ϕ i (•)) is a non-negative function.
Note that Assumption 5 could be relaxed to address situations in which, for i ∈ Q such that ϕ i (•) (resp. w i (•)) is affine, there is no restriction on the concavity (resp. convexity) of the associated w i (•) (resp. ϕ i (•)).

Example 2 (Fulfilling Assumption 5) We give here some examples of functions which satisfy Assumption 5. For simplicity, we denote z z z = (x x x, y y y).

• Uncertain linear functions of the form (ξ ξ ξ, z z z) → ξ ξ ξA A Az z z where A A A is a given real matrix; • Diagonal uncertain convex quadratic form (ξ ξ ξ, z z z) → z z z T diag(ξ ξ ξ)z z z where ξ ξ ξ ≥ 0;

• Uncertain positively weighted sum of convex functions of the form (ξ ξ ξ, z z z)

→ i∈Q ξ i ϕ i (z z z) with Ξ ⊂ R |U |
+ , e.g., (ξ ξ ξ, x x x, y y y) → i∈Q ξ i x 2 i /y i with y y y ≥ 0.

Example 3 (Violating Assumption 5) We give here some examples of functions which do not satisfy Assumption 5.

• Non-concave functions of the uncertainty, e.g., (ξ ξ ξ, z z z) → ||z z zξ ξ ξ|| for any given norm;

• General uncertain quadratic form (Σ Σ Σ, z z z) → z z z T Σ Σ Σz z z even with Σ Σ Σ 0 (unless Ξ ∩ R |U | -= ∅)
In the following lemma, we finally state the class of problems we consider.

Lemma 1 Under Assumptions (1)-( 5), there exists [l l l, u u u] ⊂ R |I|+|J| such that (2SR-P) is equivalent to the following problem:

inf x x x∈X ∩[l l l,u u u] sup ξ ξ ξ∈Ξ inf (t t t,y y y)∈Y (x x x) i∈Q w i (ξ ξ ξ)t i (2SRO-P)
with Y (x x x) such that Y(x x x) = proj y y y (Y (x x x)) and Y (x x x) is a convex and finitedimensional set.

Proof The existence of the hyper-rectangle [l l l, u u u] is trivial as X is assumed to be bounded (Assumption 2.1). Moreover, the following equality holds:

inf y y y    i∈Q w i (ξ ξ ξ)ϕ i (x x x, y y y) : y y y ∈ Y(x x x)    = inf y y y,t t t    i∈Q w i (ξ ξ ξ)t i : y y y ∈ Y(x x x), t i = ϕ i (x x x, y y y), ∀i ∈ Q  
 However, the optimization problem on the right side of the equality may fail to be convex if there exists i ∈ Q such that ϕ i is not affine. Let Q A ⊆ Q be the set of indices for which ϕ i is affine. By Assumption 5, for all i ∈ Q\Q A , we have w i (•) ≥ 0 and thus constraint "t i = ϕ i (x x x, y y y)" may be equivalently replaced by "t i ≥ ϕ i (x x x, y y y)", which is convex. We therefore can choose

Y (x x x) =    (t t t, y y y) : y y y ∈ Y(x x x) t i = ϕ i (x x x, y y y) ∀i ∈ Q A t i ≥ ϕ i (x x x, y y y) ∀i ∈ Q\Q A   
For every x x x ∈ X , the continuous relaxation of Y (x x x) is convex and non-empty (Assumption 3); by construction, it is also finite dimensional.

In what remains, we will assume to know a hyper-rectangle [l l l, u u u] as described in lemma 1.

Special case: linear and binary setting

We complete the introduction by discussing the special case of (2SRO-P) under the following additional assumptions:

1. X , Ξ and x x x → Y(x x x) are defined by linear constraints; 2. there exists a matrix

A A A ∈ R |U |×|Q| such that ∀i ∈ Q, w i (ξ ξ ξ) = ξ ξ ξ T a
a a i ; and 3. linking constraints are defined by functions g(x x x, y y y) that do not depend on first-stage variables in I c .

In a recent paper Arslan and Detienne (2021), the authors observed that, for this variant of the problem, the inner minimization min y y y∈Y(x x x) ξ ξ ξ T A A Ay y y can be equivalently replaced by min y y y∈conv(Y(x x x)) ξ ξ ξ T A A Ay y y, i.e., the second-stage feasible space can be substituted by its convex hull. This allows to transform the minmax-min problem into a min-max problem using the well known minimax theorem for convex sets. Assuming that Ξ is expressed as

{ξ ξ ξ ∈ R |U | + : F F Fξ ξ ξ ≤ d d d},
the inner maximization problem is dualized so as to obtain the following equivalent problem:

min x x x,y y y,λ λ λ d d d T λ λ λ (1) subject to x x x ∈ X (2) y y y ∈ conv (Y(x x x))
(3)

F F F T λ λ λ ≥ A A Ay y y (4) λ λ λ ≥ 0, (5)
where λ λ λ are the dual variables associated to the inner maximization problem. Note that, besides the integrality requirements on the variables, the only nonconvex constraint is (3). By exploiting a reformulation already used in [START_REF] Sherali | A modification of Benders' decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse[END_REF], [START_REF] Sherali | On solving discrete two-stage stochastic programs having mixed-integer first-and second-stage variables[END_REF] and [START_REF] Li | A finite ε-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and secondstage variables[END_REF] for two-stage stochastic optimization problems with mixed-integer first and second stage, [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF] showed that this constraint may be equivalently enforced as (x x x, y y y) ∈ conv (S) ∩ {(x x x , y y y ) :

x x x = x x x }, (6)
where S = {(x x x, y y y) : x x x ∈ {0, 1}, y y y ∈ Y(x x x)}. The obtained reformulation is then solved by means of a branch-and-price algorithm where the convex hull of set S is expressed in terms of convex combinations of its extreme points, and branching is performed on the first-stage variables only.

A hull-relaxation-based branch-and-bound algorithm

In this section we present our main contribution and its theoretical foundations. In the same spirit as in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF], we first turn problem (2SRO-P) from a min-max-min problem to a min-max problem in our mixedinteger and convex context. Then, since linear duality does not apply in our setting, we resort to Fenchel duality to obtain a reformulation of the problem.

Similarly to the linear and binary case, we then replace the counterpart of constraint ( 3) by ( 6), though this only provides a relaxation of the problem in the general setting. This relaxation is thus embedded into a branch-and-bound scheme to obtain an optimal solution of (2SRO-P).

Problem reformulation

The following lemma extends to the mixed-integer and convex context the result given in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF].

Lemma 2 (Single-stage reformulation) Problem (2SRO-P) is equivalent to the following problem: inf

(x x x,t t t,y y y)∈F sup ξ ξ ξ∈Ξ i∈Q w i (ξ ξ ξ)t i (7) with F = {(x x x, t t t, y y y) : x x x ∈ X ∩ [l l l, u u u], (t t t, y y y) ∈ conv Y (x x x) }.
Proof This lemma relies on the same arguments as those employed in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF]: first, the feasible space of the inner minimization problem is replaced by its convex hull by linearity of the objective function and convexity of the feasible region. By assumption 2.2 and Lemma 2, both Ξ and conv Y (x x x) (for all x x x ∈ X ) are convex and finite dimensional. Thus, the result in [START_REF] Perchet | A minmax theorem for concave-convex mappings with no regularity assumptions[END_REF] can be used to turn the inner sup -inf into an inf -sup problem. This achieves the proof.

The inner maximization problem may be turned into a minimization problem by use of Fenchel duality, as done in [START_REF] Ben-Tal | Robust Optimization[END_REF]. In the following proposition, we therefore derive a general reformulation of problem (2SRO-P).

Proposition 1 (Deterministic reformulation) Problem (2SRO-P) is equivalent to the following problem:

inf x x x,y y y,t t t,(v v v i ) i∈Q ,ξ ξ ξ δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i (8) subject to x x x ∈ X ∩ [l l l, u u u] (9) (t t t, y y y) ∈ conv Y (x x x) (10) i∈Q v v v i = ξ ξ ξ (11) v v v i ∈ R |U | ∀i ∈ Q (12)
Proof By a direct application of Fenchel duality and some conjugate calculus results, the following holds

sup ξ ξ ξ∈Ξ i∈Q tiwi(ξ ξ ξ) = sup ξ ξ ξ∈R |U |    i∈Q tiwi(ξ ξ ξ) -δ(ξ ξ ξ|Ξ)    = inf ξ ξ ξ∈R |U |    δ * (ξ ξ ξ|Ξ) -   i∈Q tiwi(ξ ξ ξ)   *    = inf ξ ξ ξ∈R |U |    δ * (ξ ξ ξ|Ξ) - sup v v v i ∈R |U | ,i∈Q    i∈Q (tiwi) * v v v i : i∈Q v v v i = ξ ξ ξ       = inf    δ * (ξ ξ ξ|Ξ) - i∈Q (tiwi) * v v v i : i∈Q v v v i = ξ ξ ξ, v v v i ∈ R |U | , i ∈ Q, ξ ξ ξ ∈ R |U |   
See also appendix A for more details on conjugate calculus.

Remark 4 Assume wlog that |Q| = |U |. If, for all i ∈ Q, w i (ξ ξ ξ) = w i (ξ i ), then problem (2SRO-P) is equivalent to inf (x x x,t t t,y y y)∈F    δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * (ξ ξ ξ)    (13) Remark 5 Let i ∈ Q such that w i (•) is affine, i.e., w i (ξ ξ ξ) = (r r r i ) T ξ ξ ξ + r i0 . Problem (2SRO-P) is equivalent to inf (x x x,t t t,y y y)∈F δ * (R R Rt t t|Ξ) + r r r T 0 t t t (14)
Proof Indeed, we have

(t i w i ) * (v v v) = inf ξ ξ ξ∈R |U | {v v v T ξ ξ ξ -t i ((r r r i ) T ξ ξ ξ + r i0 )} = -t i r i0 if v v v = t i r r r i -∞ otherwise.
These results show that although the reformulation for the general case adds |Q| × |U | continuous variables, for some relevant cases these additional variables can be omitted. In particular this is true in case all the w i (•) functions are either separable or affine.

Relaxation

Note that the deterministic reformulation presented above still is not, in general, a convex MINLP and that no tractable, compact form is known in the general case. To overcome this drawback, we replace constraint (10) by the following requirement: (x x x, t t t, y y y) ∈ conv (S) ∩ {(x x x , t t t , y y y ) :

x x x = x x x } with S =    (x x x, t t t, y y y) : l j ≤ x j ≤ u j ∀j ∈ I x j ∈ {0, 1} ∀j ∈ I B (t t t, y y y) ∈ Y (x x x)    (15)
The problem obtained from this substitution is thus min

x x x,y y y,(v v v i ) i∈Q ,ξ ξ ξ δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i subject to x x x ∈ X ∩ [l l l, u u u] (x x x, t t t, y y y) ∈ conv (S) i∈Q v v v i = ξ ξ ξ v v v i ∈ R |U | ∀i ∈ Q ξ ξ ξ ∈ R |U | (P)
It is clear that, for any fixed x

x x ∈ X , we have {x x x} × Y (x x x) = S ∩ {(x x x, t t t, y y y) :

x x x = x
x x}, and that the same holds even for x x x ∈ X . However, as shown, e.g., in [START_REF] Sherali | On solving discrete two-stage stochastic programs having mixed-integer first-and second-stage variables[END_REF], the convexified counterpart does not hold, in the sense that the inclusion "{x x x} × conv (Y(x x x)) ⊆ conv (S) ∩ {(x x x, t t t, y y y) : x x x = x

x x}" may be strict. Example 4 below illustrates this case. The following Lemma follows from the considerations above. In other words, (P) is a relaxation of (2SRO-P). In the next proposition, we introduce a condition under which a feasible solution for problems (P) is feasible for problem (2SRO-P) as well.

Proposition 2 If x x x ∈ vert ([l l l, u u u]), then {x x x} × conv Y (x x x) = conv (S) ∩ {(x x x, t t t, y y y) : x x x = x x x} Proof Let x x x ∈ vert ([l l l, u u u]
) and let (x x x, t t t, ŷ y y) ∈ conv (S) ∩ {(x x x, t t t, y y y) : x x x = x x x}. Then, (x x x, t t t, ŷ y y) can be expressed as a (finite) convex combination of points of conv (S) (Carathéodory's theorem), i.e., (x x x, t t t, ŷ y y) = e∈E (x e , te , ȳe )αe where E is a given index list of such elements of conv (S). Assume that there exists j ∈ I and i ∈ E such that xi j = xj . If xi j > xj , condition xi ∈ conv (S) implies that xj = l j . Hence, α i = 0 since xk j ≥ l j ∀k ∈ E. The same argument shows that xi j < xj implies α i = 0. Thus, for each e ∈ E such that αe > 0, we must have xe = x

x x. This implies that ( te , ȳe ) ∈ Y (x x x) and thus e∈E ( te , ȳe )αe ∈ conv Y (x x x) .

Corollary 1 (Tightness condition) Let X * be the set of optimal first-stage decisions of problem (P). Then:

X * ∩ vert ([l l l, u u u]) = ∅ ⇒ v(P) = v(2SRO-P)
Proof Let (x x x * , t t t * , y y y * ) be an optimal solution of (P) with x x x * ∈ vert ([l l l, u u u]). From Proposition 2, it is also feasible for problem (2SRO-P). Thus, Lemma 3 implies optimality for problem (2SRO-P).

This result directly implies Corollary 2 which states that, in the special case where the first-stage variables are all binary, problem (P) is always an exact reformulation of (2SRO-P).

Enumerative algorithm

We now present an exact method for solving problem (2SRO-P). Motivated by Corollary 1, the main idea of the algorithm is to determine an optimal value of the first-stage variables, and then derive the corresponding optimal values for the second-stage variables. To this aim, we developed a branch-and-bound algorithm in which we relax both the integrality of the x and requirement (10).

To ensure feasibility, we perform a spatial branching on the x variables, until each of them attains either its lower or upper bound. The algorithm stores the best feasible solution found (the incumbent solution) which is returned when the algorithm stops.

Node solution

Let p denote a generic node of the branch-and-bound tree, associated with bounds l l l p and u u u p on first-stage variables.

A lower bound on the optimal solution value of node p can be computed solving the following problem:

min x x x,t t t,y y y,(v v v i ) i∈Q ,ξ ξ ξ δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i subject to x x x ∈ X ∩ [l l l p , u u u p ] (x x x, t t t, y y y) ∈ conv (S p ) i∈Q v v v i = ξ ξ ξ v v v i ∈ R |U | ∀i ∈ Q ξ ξ ξ ∈ R |U | (LB p )
where S p = {(x x x, t t t, y y y) : l l l p ≤ x x x ≤ u u u p , x j ∈ {0, 1}, ∀j ∈ I B , (t t t, y y y) ∈ Y (x x x)}. This problem is exactly the continuous relaxation of problem (P) where the bounds l l l and u u u have been replaced by l l l p and u u u p . Note that at the root node we have l l l 0 = l l l and u u u 0 = u u u.

Let (x x x p * , t t t p * , y y y p * , (v v v i p * ) i∈Q , ξ ξ ξ p * ) be an optimal solution of problem LB p . If v(LB p ) is greater than or equal to the cost of the incumbent, the node is fathomed by bounding. Otherwise, we distinguish three cases:

• if x x x p * ∈ vert ([l l l p , u u u p ]), by Proposition 2, this solution is optimal for the current node. Hence, the node is fathomed by optimality and the incumbent is updated; • if x x x p * ∈ X \ vert ([l l l p , u u u p ]), we compute a feasible solution for (2SRO-P) by solving the following model in which the first-stage variables are fixed to x x x p * : min

t t t,y y y,(v v v i ) i∈Q ,ξ ξ ξ δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i subject to (t t t, y y y) ∈ conv (Y (x x x p * )) i∈Q v v v i = ξ ξ ξ v v v i ∈ R |U | ∀i ∈ Q ξ ξ ξ ∈ R |U | (UB p )
Note that, in this case, x x x p * corresponds to a feasible first-stage solution; hence, by Assumption 3, problem UB p is always feasible, and possibly the incumbent is updated. If v(LB p ) = v(U B p ) then node p is solved; otherwise, we perform a branching; • if x x x p * ∈ X \ X , we branch.

In the last case, before branching, one can try to round x x x p * ; if the resulting point is in X , a feasible solution for (2SRO-P) can be computed. In our experiments, every fractional value for x p * j with j ∈ I B was rounded to the closest integer while variables x p * j with j ∈ I C were not rounded.

Branching

We now describe how to select the branching variable at node p. For each firststage variable, say with index j ∈ I, we compute the minimum distance of x p * j from one of its bounds at the node, i.e., we evaluate:

θ p j = min{x p * j -l p j ; u p j -x p * j }.
For branching, we give priority to binary variables that do not attain their bound. Otherwise, we resort to spatial branching on continuous variables.

In both cases, we select the variable with maximum θ p j value, i.e., we select variable x j such that,

j ∈ argmax{θ p j : j ∈ I B } if ∃j ∈ I B , θ j > 0 argmax{θ p j : j ∈ I C } otherwise.
If j ∈ I B , then a standard binary branching is executed. Otherwise, we resort to spatial branching, and generate two descendant nodes by imposing x j ≤ x p * j for the left node and x j ≥ x p * j for the right one. We associate to each node the lower bound value of the current node v(LB p ) and insert them in a list of open nodes. At each iteration, we extract from the list one node with minimum lower bound value, halting the algorithm stops when the list is empty.

Example 5 Figure 2 illustrates the left and right child obtained by spatial branching on x ≤ β and x ≥ β from example 1 (here, β = 0.4). Clearly, the right child allows the same recourse decisions as in Y(x) for all x ≥ β. The left child, however, still allows second-stage decisions that could end up being infeasible in the original problem. In particular, (x x x, y y y) = (ε, 1 -ε, 0) with ε ∈ (0, β] is feasible for (LB p ) but not for (2SRO-P).

Single-stage heuristic

We now present a heuristic procedure that can be used at the root node to warm start the branch-and-bound algorithm. This heuristic is based on the definition of a single-stage version of (2SR-P), in which both first-and secondstage variables are simultaneously optimized. The resulting problem can be formulated using the following MINLP:

min δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i (16) subject to x x x ∈ X ∩ [l l l, u u u] ( 17
) (t t t, y y y) ∈ Y (x x x) (18) i∈Q v v v i = ξ ξ ξ (19) v v v i ∈ R |U | ∀i ∈ Q (20)
Note that solving this problem is NP-hard. Let x x x * denote its optimal firststage solution with associated (t t t * , y y y * ) second-stage solution. An improving second stage-solution can be possibly obtained by fixing x x x = x x x * in problem (2SRO-P), in the spirit of the upper bounding procedure used when solving UB p .

Convergence

Given a feasible solution of (LB p ), say (x x x, t t t, y y y, V V V , ξ ξ ξ), we introduce the following function

F (x x x, t t t, y y y, V V V , ξ ξ ξ) := δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i = F (t t t, V V V , ξ ξ ξ),
that returns the solution value in the lower bounding problem.

Proposition 3 (Convergence result) If F ∈ C 0 , our branch-and-bound algorithm either finitely terminates or enters an infinite sequence of nodes for which the optimal solutions of the associated lower bounding problems converge to an optimal solution of 2SRO-P.

Proof Let us consider the case in which the algorithm enters an infinite sequence P of nodes, indexed by p. We denote by (l l l p , u u u p ) the associated bounds for the x x x variables, and by (x x x p * , t t t p * , y y y p * , V V V p * , ξ ξ ξ p * ) the optimal optimal solutions of the corresponding lower bounding problems. Since branching always reduces the domain of the x x x variables, then (l l l p , u u u p ) will converge to some values, say (l l l * , u u u * ), and x x x p * will converge to a solution x x x * .

We first show that the sequence of optimal solutions of the lower bounding problems converges to an optimal solution of the lower bounding problem defined by bounds (l l l * , u u u * ).

By boundedness of problems (LB p ), there exists P ⊆ P and (t t t * , y y y * , V V V * , ξ ξ ξ * ), such that {(x x x p * , t t t p * , y y y p * , V V V p * , ξ ξ ξ p * )} p∈P → (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) Since (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) is the limit of a sequence of feasible points and the feasible region is closed, (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) is feasible for the lower bounding problem LB * defined by bounds (l l l * , u u u * ), and thus

F (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) ≥ v(LB * ) := F (x x x, t t t, ŷ y y, V V V , ξ ξ ξ),
where (x x x, t t t, ŷ y y, V V V , ξ ξ ξ) is an optimal solution for problem LB * . We now show that (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) is as well an optimal solution for this problem, i.e., equality holds. Assume by contradiction that F (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) > F (x x x, t t t, ŷ y y, V V V , ξ ξ ξ). For all p ∈ P , since P ⊆ P , we have [l l l * , u u u * ] ⊆ [l l l p , u u u p ] and thus (x x x, t t t, ŷ y y, V V V , ξ ξ ξ) is feasible for (LB p ). By continuity of F we now have

{F (x x x p * , t t t p * , y y y p * , V V V p * , ξ ξ ξ p * )} p∈P → F (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) > F (x x x, t t t, ŷ y y, V V V , ξ ξ ξ),
which contradicts the optimality of (x x x p * , t t t p * , y y y p * , V V V p * , ξ ξ ξ p * ) for some p.

We now show that the solution to which the sequence converges is a feasible solution for 2SRO-P. Given the infinite sequence of nodes, there exists at least one variable j ∈ I C which is infinitely selected for branching. Thus, we must have θ j → 0. Given our branching rule, this implies that all the other continuous variables attain either their lower or upper bounds. Thus x x x * ∈ vert ([l l l * , u u u * ]), which implies (t t t * , y y y * ) ∈ conv Y (x x x * ) and F (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ) = v(LB * ) ≥ v(2SRO-P). Since our node selection strategy always picks a node with minimum lower bound, for each node p of the branching sequence we have v(LB p ) ≤ v(2SRO-P) ≤ v(LB * ). As v(LB p ) converges to v(LB * ), we also have v(LB * ) = v(2SRO-P).

The previous result applies when considering infinite precision. By introducing a finite tolerance in the algorithm, we can show that an infinite branching cannot occur at any point. More specifically, given an optimal solution x x x p * of the lower bounding problem at a node p, we introduce the following function G(x x x p * ) := v(UB p ), that returns the solution value in the upper bounding problem.

Proposition 4 (Convergence in finite precision) If the branch-and-bound algorithm enters an infinite sequence of nodes, then it must be converging to a point x x x * in which function G has a discontinuity.

Proof The proof of the previous proposition shows that there exists a subsequence P ⊆ P that converges to a solution (x x x * , t t t * , y y y * , V V V * , ξ ξ ξ * ). As (t t t * , y y y

* ) ∈ conv Y (x x x * ) then v(LB * ) = G(x x x * ).
Assume now that G is continuous at x x x * . Then, we have {G(x x x p * )} p∈P → G(x x x * ) = v(LB * ), which allows us to fathom the node by optimality after a finite number of nodes for any positive tolerance.

We conclude this section by observing that, at each node of the branch-andbound algorithm, the lower bounding problem can be solved with ε-tolerance in a finite number of operations. Indeed, as shown in [START_REF] Ceria | Convex programming for disjunctive convex optimization[END_REF] and [START_REF] Grossmann | Generalized disjunctive programming: A framework for formulation and alternative algorithms for MINLP optimization[END_REF], one can reformulate a convex disjunctive program as a compact convex MINLP by introducing an exponential number of auxiliary variables that model the disjunctions. The resulting model can thus be solved in finite number of states by using any algorithm designed for convex optimization.

A convexification scheme based on column-generation

In this section, we propose a nonlinear column-generation algorithm to be used, at each node p, to solve problem (LB p ) to ε-optimality in a finite number of iterations. According to this scheme, we approximate conv (S p ) by the convex hull of a finite set of points belonging to S p . Restricted Master Problem: To determine this set, we use an iterative approach. At each iteration k, let K = {1, . . . , k} and denote by H pk = {(x pj , tpj , ȳpj ) : j ∈ K} the associated set of points. We clearly have conv H pk ⊆ conv (S p ), thus the optimal solution of the problem obtained by substituting conv (S p ) with conv H pk in (LB p ) gives an upper bound of (LB p ). The resulting problem, denoted as ( LB pk ), is called the Restricted Master, and is formulated as follows:

min x x x,t t t,y y y,V V V ,ξ ξ ξ,α α α δ * (ξ ξ ξ|Ξ) - i∈Q (t i w i ) * v v v i (22) subject to x x x ∈ X ∩ [l l l p , u u u p ] (23) x x x = j∈K α j xpj ( 24
)
t t t = j∈K α j tpj ( 25
)
y y y = j∈K α j ȳpj ( 26
) j∈K α j = 1 (27) i∈Q v v v i = ξ ξ ξ (28) v v v i ∈ R |U | ∀i ∈ Q (29) ξ ξ ξ ∈ R |U | (30) α j ≥ 0 ∀j ∈ K (31)
( LB pk ) Following the classical column-generation framework, the current approximation can be improved by means of a so-called Pricing Problem, defined as follows.

Pricing Problem: Let λ λ λ pk * , µ µ µ pk * , π π π pk * and η pk * be the values of the dual variables associated with constraints ( 24), ( 25), (26), and ( 27) in an optimal solution of problem ( LB pk ). Pricing asks to solve the following problem (x p,k+1 , tp,k+1 , ȳp,k+1 ) ∈ argmin

(x x x,t t t,y y y)∈S p -λ λ λ pk * T x x x -µ µ µ pk T t t t -π π π pk * T y y y -η pk * T (PP pk )
and generates a new point (x p,k+1 , tp,k+1 , ȳp,k+1 ) belonging to S p . If v(PP pk ) ≥ -ε, we have an ε-optimal solution to (LB p ), and hence the algorithm terminates. Otherwise, we set H k+1 = H k ∪ {(x p,k+1 , tp,k+1 , ȳp,k+1 )}, k = k + 1 and iterate. Note that, at each iteration k, a lower bound on the optimal solution value of (LB p ) is given by v( LB pk ) -v(PP pk ). This lower bound, combined with an upper bound, can allow us to early terminate the solution of problem (LB p ).

The convergence of nonlinear column generation has been established in [START_REF] García | Column generation algorithms for nonlinear optimization, I: Convergence analysis[END_REF] and implies finite ε-convergence of our method.

In this section, we report computational results of our solution algorithm when applied to two different optimization problems, a facility location problem and a capital budgeting problem, respectively. Both problems are relevant from an application viewpoint and are defined as non-trivial variants of problems already addressed in the literature.

All the experiments were run on an AMD 3960 running at 3.8 GHz, with a time limit equal to 3,600 CPU seconds per run.

Facility location problem with adjustable capacity and set-up costs

We consider a company which has to decide, among a set V 1 of possible locations, the sites where to open a facility in order to serve a set V 2 of customers, each with an associated with a known demand d j . The size of each opened facility has to be determined as well, and an upper limit q i on the capacity that can be installed on each site i ∈ V 1 is given. The objective of the problem is to minimize a cost function that includes both facility-opening costs and the transportation costs to serve the customers. More into details, transportation costs consist of a fixed component h ij to be paid if customer j is assigned to facility i, and a variable component ξ ij to be paid for each unit of good that traverses this connection. We assume that the variable transportation costs are not known precisely, i.e., ξ ij are uncertain parameters.

To model the problem, we introduce, for each location i ∈ V 1 , a binary variable x i taking the value 1 if a facility is opened in location i and 0 otherwise. In addition, we introduce a continuous variable z i ∈ [0, 1] indicating the fraction of the maximum capacity that is installed. Using these variables, the first-stage feasible space is given by X

= {(x x x, z z z) ∈ {0, 1} |V1| ×[0, 1] |V1| : z z z ≤ x x x}.
To model the second-stage feasible region, we introduce, for every connection between i ∈ V 1 and j ∈ V 2 , a binary variable y ij which takes the value 1 if and only if the connection is used, and a continuous variable w ij ∈ [0, 1] representing the fraction of demand d j served by facility i. We then have:

Y(z z z) =            (y y y, w w w) : y y y ∈ {0, 1} |V1|×|V2| w w w ∈ [0, 1] |V1|×|V2| i∈V1 w ij = 1 ∀j ∈ V 2 j∈V2 d j w ij ≤ z i q i ∀i ∈ V 1 w ij ≤ y ij ∀i ∈ V 1 , ∀j ∈ V 2            (31)
Here, the first set of constraint enforces that every customer is served, while the second set of constraint imposes that the installed capacities are not exceeded. Finally, the last set of constraints link the w and the y variables.

For each site i ∈ V , the associated opening cost depends on the activation of the facility and on the installed capacity, and is described by the following convex quadratic function

F i (x i , z i ) = f i x i + γ i z 2 i + β i z i
Our two-stage robust problem reads: min

(x x x,z z z)∈X max ξ ξ ξ∈Ξ min (y y y,w w w)∈Y(z z z) i∈V1   f i x i + γ i z 2 i + β i z i + j∈V2 (h ij y ij + d j ξ ij w ij )   (32)
We refer to problem (32) as the two-stage robust facility location problem with adjustable capacity and set-up transportation costs. This problem can be cast as (2SRO-P), where the linking constraints between the first-and secondstage variables involve purely continuous variables and exhibits convexity in the first-stage feasible space. Finally, the uncertainty has a linear impact on the second-stage objective function.

We assume that variable transportation costs are described according to a classical ellipsoidal uncertainty set

Ξ κ = (ξ ij ) i∈V1,j∈V2 : (ξ ξ ξ -ξ ξ ξ)Σ Σ Σ -1 (ξ ξ ξ -ξ ξ ξ) ≤ κ 2 , ( 33
)
where κ is a fixed sensitivity parameter, ξ ξ ξ the expected value of ξ ij and Σ Σ Σ = (σ ij ) i,j the covariance matrix. For simplicity, we will assume that Σ Σ Σ is diagonal (implying that variable costs are independent from each other), although this assumption is not strictly required by our method.

By applying Proposition 1, the following deterministic reformulation results: min x x x,z z z,y y y,w w w i∈V1

  f i x i + γ i z 2 i + β i z i + j∈V2 (h ij y ij + d j ξij w ij )   + κ i∈V1 j∈V2 d 2 j σ 2 ij w 2 ij (34) subject to (x x x, z z z) ∈ X (35) (y y y, w w w) ∈ conv (Y(x x x)) (36)
The reader is referred to Appendix B for the derivation of the robust counterpart of ellipsoidal uncertainty sets.

Instance generation

To test the proposed method, a large benchmark of random instances has been generated in the spirit of [START_REF] Cornuejols | A comparison of heuristics and relaxations for the capacitated plant location problem[END_REF]. First, we randomly generate the location of each site i ∈ V 1 and customer j ∈ V 2 using a uniform distribution in the unit square. For each site i and customer j, the fixed component of the transportation cost is obtained by multiplying the euclidean distance between i and j times a random number with uniform distribution in [20,50]. The expected value of the variable transportation cost is instead obtained by multiplying the euclidean distance times 10. Each covariance parameter is uniformly randomly generated in the interval [σ -, σ + ], where σ -and σ + are specified below. For every site i ∈ V 1 , the capacity upper limit is generated according to a uniform distribution in [10,160], and the fixed setup cost is a random number in [0, 90] multiplied by a varying adjustment factor µ. Coefficients γ i and β i are computed so that F i (1, q i ), which represents the cost for activating the full capacity on the site, equals √ q i × α, where α is randomly generated in [100,110], as in [START_REF] Cornuejols | A comparison of heuristics and relaxations for the capacitated plant location problem[END_REF]. Finally, customers' demands are obtained by defining a random vector d d d in [0, 1], and scaling its entries so that j∈V2 q j / i∈V1 d i = ν, where ν is another parameter. In all our instances the number of sites and customers are (4, 8), (6, 12), (8, 16), (9, 18), (10, 20), (11, 22) and (12, 24), and the ellipsoidal uncertainty parameter κ belongs to {1.0, 1.5, 2.0}. Covariance parameters σ - and σ + take values (0.1, 1), (0.5, 2) and (1, 4). Similar to [START_REF] Cornuejols | A comparison of heuristics and relaxations for the capacitated plant location problem[END_REF], the adjustment factor µ is set to 2.0 for instances with |V 1 ||V 2 | ≤ 500 and to 1.0 otherwise, and ν takes values in {1.5, 2.0, 3.0, 5.0, 10.0}. Finally, for each combination of the parameters we generate 4 instances, overall producing 1260 instances.

Numerical results

We now report the computational results of our branch-and-bound algorithm without and with the use, at the root node, of the single-stage heuristic (SSH) of Section 3.3.3; from now on, these versions are denoted as BB and BB H, respectively. Table 1 gives the outcome of our experiments for both variants of the algorithm. Each line refers to the 60 instances characterized by the same values of |V 1 |, |V 2 | and κ. Entries of the table give, for each variant, the following information:

• nodes is the average number of branch-and-bound nodes explored (with respect to instances solved to optimality only); • time is the average computing time (with respect to instances solved to optimality only); • # opt is the number of optimal solutions. In addition, for variant BB H, we report in column "% gap r " the average percentage gap at the root node. Letting L r and U r be the best lower and upper bound at the root node, the gap is computed as % gap r = 100 * Ur-Lr Lr . This information is omitted for algorithm BB, which never provides a feasible solution at the root node.

The table shows that the complexity of these ACFL instances increases with the size of the underlying network. In addition, for each size of the network, increasing the value of κ (i.e., allowing for more uncertainty in the realization of the profits) makes the instances consistently harder. The basic algorithm BB Adding SSH heuristic produces a considerable improvement of the results: although the average root node gap is around 20%, the algorithm solves 68 additional instances to optimality (more than 90% in total) and has an average computing time which is reduced by more than 20%.

Robust Capital Budgeting problem

Our second test-case is a variant of the Robust Capital Budgeting (RCB) problem introduced in Hanasusanto et al (2015) and considered also in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF]. Consider a company which can allocate a given budget B to a set of projects i ∈ N = {1, . . . , N }; the budget can be increased with loans. Each project i ∈ N has a fixed cost c i and an uncertain profit pi (ξ ξ ξ) which depends on M unknown factors ξ ξ ξ that belong to an uncertainty set Ξ. The company must decide which projects should be activated to maximize the expected profit. To this aim, it may activate some projects after observing the risk factors, though late investments are less effective and are discounted by a factor f ∈ [0, 1) of their value. In addition, the company has the possibility to request loans both in the first and in the second stage. The maximum amount of a loan is denoted by C 1 and C 2 , respectively, and the interest rate is denoted by λ and is increased in the second stage by a factor µ.

The problem can be modeled as the following max-min-max problem. max

(x x x,x0)∈X min ξ ξ ξ∈Ξ max (y y y,y0)∈Y(x x x,x0) i∈N pi (ξ ξ ξ)(x i + f y i ) -(1 + λ)C 1 x 0 -(1 + λµ)C 2 y 0 (37) with X = {(x x x, x 0 ) ∈ {0, 1} N × [0, 1] : i∈N c i x i ≤ B + C 1 x 0 } and Y(x x x, x 0 ) = {(y y y, y 0 ) ∈ {0, 1} N × [0, 1] : i∈N c i (x i + y i ) ≤ B + C 1 x 0 + C 2 y 0 , y i + x i ≤ 1 ∀i ∈ N }.
Here, x x x are binary variables that indicate whether a project has been activated in the first stage or not, while y y y indicate their activation in the second stage. Variable x 0 (resp. y 0 ) is a continuous variable indicating the fraction of the loan capacity which is activated in the first (resp. second) stage.

The actual profit associated with each project is given by pi (ξ ξ ξ) = pi (1 + ∆ i (ξ ξ ξ)) where pi is the nominal profit, ξ ξ ξ denotes the uncertainty belonging to set Ξ = [-1, 1] M , and

∆ i : [-1, 1] M → [-0.5, 0.5] is a quadratic convex function defined as ∆ i (ξ ξ ξ) = ξ ξ ξ T Q Q Q i ξ ξ ξ/2 + g g g i T ξ ξ ξ.

Convex reformulation

In this section, we show how one can apply Proposition 1 to reformulate (37). By convexifying the inner maximization problem and swapping the inner max and min operators, one obtains

max -(1 + λ)C 1 x 0 -(1 + λµ)C 2 y 0 + i∈N pi (x i + f y i ) + min ξ ξ ξ∈Ξ i∈N ∆ i (ξ ξ ξ)(x i + f y i )p i (38) subject to (x x x, x 0 ) ∈ X (39)
(y y y, y 0 ) ∈ conv (Y(x x x, x 0 )) .

We now reformulate the minimization subproblem as follows min ξ ξ ξ∈Ξ i∈N

∆ i (ξ ξ ξ)(x i + f y i )p i = min ξ ξ ξ∈R M i∈N ∆ i (ξ ξ ξ)(x i + f y i )p i + δ(ξ ξ ξ|Ξ) (41) = max ξ ξ ξ∈R M (-δ) * (ξ ξ ξ|Ξ) - i∈N ∆ i (ξ ξ ξ)(x i + f y i )p i * (42) = max (-δ) * (ξ ξ ξ|Ξ) - i∈N t i ∆ i (s s s i ) * subject to t i = (x i + f y i )p i ∀i ∈ N i∈N s s s i = ξ ξ ξ ξ ξ ξ ∈ R M s s s i ∈ R M ∀i ∈ N t t t ∈ R |N | + (43)
Note that (-δ) * (ξ ξ ξ|Ξ) = -δ * (-ξ ξ ξ|Ξ). In addition, by symmetry of Ξ, we have δ(-ξ ξ ξ|Ξ) = δ(ξ ξ ξ|Ξ), hence δ * (-

ξ ξ ξ|Ξ) = δ * (ξ ξ ξ|Ξ) = max ζ ζ ζ∈Ξ ξ ξ ξ T ζ ζ ζ = ||ξ ξ ξ|| 1 ,
where the last equivalence is based on strong linear duality.

By combining these two results, we have that (-δ)

* (ξ ξ ξ|Ξ) = -||ξ ξ ξ|| 1 . Moreover ∆ * i (ξ ξ ξ) = 1 2 (ξ ξ ξ -g g g i ) T Q Q Q i -1 (ξ ξ ξ -g g g i ) ( 44
)
hence expanding each conjugate that appears in the summation in (43), we get

(t i ∆ i ) * (s s s i ) =      s s s i Q Q Q i-1 s s s i 2ti -(g g g i T Q Q Q i -1 ) T s s s i + (g g g i T Q Q Q i -1 g g g i /2)t i if t i > 0 0 if t i = 0 and s s s i = 0 +∞ otherwise (45)
As these terms are minimized in the objective function, any optimal solution with t i = 0 must have s s s i = 0 as well. Note that this can be enforced by introducing, for each project i ∈ N , a non-negative variable r i and the additional constraint 2t i r i ≥ s s s i T Q Q Q i -1 s s s i . This constraint is convex since it can be modeled by means of the rotated quadratic cone.

Our final model reads max ( 46)

-(1 + λ)C 1 x 0 -(1 + λ)µC 2 y 0 + i∈N pi (x i + f y i ) -|ξ i | -r i +(g g g i T Q Q Q i -1 ) T s s s i - g g g i T Q Q Q i -1 g g g i 2 t i (47) subject to (48) (x x x, x 0 ) ∈ X (49)
(y y y, y 0 ) ∈ conv (Y(x x x, x 0 )) (50)

t i = (x i + f y i )p i ∀i ∈ N (51) 2t i r i ≥ s s s i T Q Q Q i -1 s s s i ∀i ∈ N (52) i∈N s s s i = ξ ξ ξ (53) ξ ξ ξ ∈ R |N | (54) s s s i ∈ R |N | ∀i ∈ N (55) t t t ∈ R |N | + (56) r r r ∈ R |N | + (57)

Instance generation

The instances in our testbed are generated similar to those in [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF]: for each project i ∈ N , c i is randomly generated following a uniform distribution between 1 and 100, and the nominal profit pi is defined as c i /5. We set the investment budget B = H i∈N c i where H is a given parameter. We assume that postponed investments are discounted by a factor f = 0.8. The loans limits are set to C 1 = C 2 = 0.2B while the interest rate parameters are chosen as λ = 0.025 and µ = 1.2.

Deviations of the profits are generated as follows. For each project i, we first randomly generate M coefficients g g g i taken taken from the M -dimensional unit simplex, and then each such coefficient is multiplied by -0.5 or 0.5 with equal probability. Then, we compute the value of the linear function g g g iT ξ ξ ξ in all vertices of [-1, 1] M , and compute a convex quadratic function that (i) has the same value as the linear function on each vertex, and (ii) attains its minimum (over [-1, 1] M ) in one of these points. (More details about this last step are given in the Appendix).

In our instances, parameter H takes values in {0.2, 0.4, 0.6, 0.8}, the number of projects N is in {30, 40, 50, 60} while the number of risk factors M is either 4 or 8. For each of these settings, we define 10 instances, making a total of 320 instances.

Numerical results

Table 2 gives the same information as Table 1. Since for this problem there are cases in which algorithm BB provides a feasible solution at the root node, we also give column "% gap r " (computed as % gap r = 100 * Ur-Lr Ur ) and column "# UB r " reporting the number of instances for which this happens. This latter column is omitted for algorithm BB H, as the SSH heuristic is always able to determine a feasible solution at the root node. Each entry in the table refers to the 40 instances characterized by the same value of N and M , with the exception of those in column % gap r , which account only the instances for which a valid upper bound U r is available.

The results show that algorithm BB is able to solve almost all the instances in at most 3 minutes. Algorithm BB H has slightly better performances, as it allows to solve to optimality one more instance and reduces the average computing time and number of nodes with respect to BB. Overall, BB H is able to solve all instances but 2 to proven optimality, within less than one minute, on average. Finally, observe that BB H may present a larger percentage gap at the root node as this figure is computed over the entire set of instances (as opposed to a subset of them for the other algorithm).

Problem variants

We also tested algorithm BB H on some variants of the problem, obtained combining the following features:

no loans/binary loans/continuous loans: meaning that loans are not available, can be used only at their maximum amount, or can be used at any intermediate value;

independent/dependent risk factors: meaning that risk factors may impact the profit of each project i according to a linear or to a non-linear function.

We consider two types of functions (∆ i ) i∈N : (Q) convex quadratic functions ∆ i (ξ ξ ξ) = ξ ξ ξ T Q Q Q i ξ ξ ξ/2 + g g g i T ξ ξ ξ, and (L) linear functions ∆ i (ξ ξ ξ) = g g g i T ξ ξ ξ. In the linear case, the g g g i coefficients are generated as in the quadratic case.

Table 3 reports the results of our experiments on the six variants described above. The upper part of the table refers to instances with quadratic risk functions, while the lower part addresses the linear case.

The results show that, in the quadratic case, the "no loans" and "binary loans" variants tend to be slightly easier than the "continuous loans" in terms of number of optimal solutions and average computing time.

As to the linear case, it looks much more challenging that its quadratic counterpart. This counter-intuitive behaviour is due to the way the instances are defined, in particular for what concerns functions ∆ i (ξ ξ ξ). Indeed, the impact of risk factors in the profit reduction is always larger in the linear case than in the quadratic case; since we are considering a robust (i.e., worst-case) setting, this makes the linear case farther from nominal values than the quadratic one. Nevertheless, also in this challenging case, algorithm BB H is able to solve almost 75% of the instances with an average time below 10 minutes.

Conclusion

In this work, we studied optimization problems where part of the cost parameters are not known at decision time, and the decision flow is modeled as a two-stage process. In particular, we addressed general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and involve mixed-integer variables. To the best of our knowledge, this is the first attempt to extend the existing literature to tackle this wide class of problems.

To this aim, we derive a relaxation of the problem which can be formulated as a convex optimization problem, and embed it within a branch-and-bound algorithm where branching occurs on integer and continuous variables. By combining enumeration and on-the-fly generation of the variables, we obtain a branch-and-price scheme, for which we prove convergence to ε-optimality.

In addition to the theoretical analysis, we applied our method to two optimization problems affected by objective uncertainty, namely a variant of the Capacitated Facility Location problem and a capital budgeting problem. Our computational experiments showed that the proposed method is able to solve relevant-size instances for both problems.

Horizon 2020 under the Marie Sk lodowska-Curie Actions Grant Agreement No 764759.

Appendix A Recalls of convex and concave conjugate

In this appendix we review some basic results on conjugate functions and Fenchel duality. For a detailed treatment we refer to [START_REF] Rockafellar | Convex Analysis[END_REF]. Let f : R n → R be a given function, its convex conjugate is denoted by f * : R n → R and is given by

f * (π π π) = sup x x x∈dom(f ) π π π T x x x -f (x x x)
Similarly, we denote by g * the concave conjugate of a given function g : R n → R, given by g * (π π π) = inf

x x x∈dom(g) π π π T x x xg g g(x x x)

Note that, if f is a proper convex function and g a proper concave function, we have that f * * = f and g * * = g. We now state the following Fenchel duality theorem.

Theorem 1 Let f : R n → R be a proper convex function and g : R n → R be a proper concave function, then Proof The result holds from the fact that sup{g(x x x) : x x x ∈ X } = sup{g(x x x) -δ(x x x|X )} and by application of Fenchel duality. More precisely, δ(x x x|X ) is convex and, by nonemptiness of X , is proper.

Notice that Fenchel duality allows the reformulation of an optimization problem which consists in maximizing a concave function over a convex set as an unconstrained convex problem since δ * ( • |X ) and (-g * )( • ) are convex functions and positively weighted sums preserve convexity.

h(x x x)

h * (π π π) Separable sums h(x x x 1 , x x x 2 ) = f 1 (x x x 1 ) + f 2 (x x x 2 ) h * (π π π 1 , π π π 2 ) = f * 1 (π π π 1 ) + f * 2 (π π π 2 ) Scalar multiplications (α > 0) h(x x x) = αf (x x x) h * (π π π) = αf * (π π π/α) Table A1 reports some calculus rules regarding convex conjugates. The extension to concave conjugates is straightforward.

Affine mapping composition (det

Example 4 (

 4 Hull relaxation) We consider the first-and second-stage feasible sets introduced in Example 1. In Figure (1a), we represent the convex hull of S. For a fixed first-stage decision x (here, x = 0.4), Figure (1b) reports the feasible points for constraint (15), whereas Figure (1c) describes the exact shape of conv (Y(x)). The figure shows an example in which inclusion is strict. In addition, note that, whenever x attains its bounds (i.e., x ∈ {0, 1}), {x} × conv (Y(x)) = conv (S) ∩ {(x, y y y) : x = x} holds.

  Fig. 1: Graphical representation of different sets from example 1

Corollary 2 (

 2 Tightness condition/binary case) If the first-stage decisions are all binary, i.e., I C = ∅, then v(P) = v(2SRO-P) Proof In this case, [l l l, u u u] = [0, 1], hence any optimal first-stage solution x x x * satisfies x x x * ∈ {0, 1} I B = vert ([l l l, u u u]) which, by Corollary 1, proves the result.

Fig. 2 :

 2 Fig. 2: Branching on continuous variable x from example 1

  inf x x x∈dom(f )∩dom(g) {f (x x x) -g(x x x)} = sup π π π∈dom(f * )∩dom(g * ) g * (π π π) -f * (π π π)or equivalently,sup x x x∈dom(f )∩dom(g) {g(x x x) -f (x x x)} = inf π π π∈dom(g * )∩dom(f * ) f * (π π π) -g * (π π π)Corollary 3 (Maximizing a concave function over a convex set) Let X ⊆ R n be a non-empty convex set, g : R n → R be a proper concave function, then sup

  A A A = 0) h(x x x) = f (A A Ax x x + b b b) h * (π π π) = f * (A A A -T π π π) -b b b T A A A -T π π π Sum with affine functions h(x x x) = f (x x x) + a a a T x x x + b b b h * (π π π) = f * (π π π -a a a)i = π π πTableA1: Some convex conjugate calculus rulesProposition 5 Let f be a convex function, we have(-f ) * (π π π) = -f * (-π π π). Proof (-f ) * (π π π) = inf x x x π π π T x x x -(-f )(x x x) = -sup x x x -π π π T x x x -f (x x x) = -f * (-π π π)Proposition 6 Let C be a convex set such that x x x ∈ C ⇔ -x x x ∈ C, we have δ * (π π π|C) = δ * (-π π π|C)Proof We have δ * (π π π|C) = sup x x x∈C π π π T x x x. Denoting x x x * the optimal primal solution to this optimization problem, there exists u u u ∈ C such that u u u = -x x x * and thus δ * (π π π|C) = sup u u u∈C -π π π T u u u = δ * (-π π π|C).

Table 1 :

 1 Performance of different variants of the algorithm in solving ACFL problem solves 85% of the instances, with an average computing time below 10 minutes.

	12	24	1	31.9 1325.2	33	19.1	25.2 1113.1	42
			1.5	33.2 1195.4	30	20.4	27.4 1138.3	38
			2	33.5 1208.9	27	20.3	28.0	994.9	34

Table 2 :

 2 Performance of different variants of the algorithm in solving the RCB problem.

					BB				BB H
	N	M	# UBr	% gapr	nodes	time # opt % gapr	nodes	time # opt
	30	4	32	1.7	5.5	17.5	40	3.2	3.1	10.7	40
		8	24	3.3	42.5 131.9	39	1.7	38.7 124.3	39
	40	4	28	1.2	5.7	31.1	40	5.4	2.3	15.0	40
		8	25	1.8	23.5 146.6	39	0.8	18.2 117.4	39
	50	4	31	0.6	2.7	25.4	40	5.2	1.2	13.5	40
		8	24	1.3	11.9 117.3	38	0.5	15.5 144.0	39
	60	4	27	0.5	1.8	23.7	40	5.2	1.0	16.2	40
		8	23	1.2	12.6 180.6	40	0.4	2.2	37.5	40

Table 3 :

 3 Performance of the full algorithm in solving different variants of the RCB problem.

			No loans		Binary loans	Continuous loans
	N	M	time # opt	time # opt	time	# opt
	Q 30	4	5.5	40	6.0	40	10.7	40
		8 118.4	40 135.8	40	124.3	39
	40	4	8.9	40	9.4	40	15.0	40
		8 169.0	40	97.2	39	117.4	39
	50	4	10.1	40	9.8	40	13.5	40
		8 179.5	40 190.2	40	144.0	39
	60	4	13.8	40	13.2	40	16.2	40
		8	25.1	40	25.7	40	37.5	40
	L 30	4 241.1	37 110.7	36	217.3	37
		8 580.0	32 618.9	32	480.9	31
	40	4 223.8	37 195.6	38	193.1	36
		8 447.1	28 276.3	28	247.9	28
	50	4 744.8	22 740.1	24	798.6	25
		8 523.2	39 238.3	40	251.9	40
	60	4 832.9	7	957.4	7 1238.7	8
		8 946.1	32 695.0	33	665.5	32

Funding

This research was supported by "Mixed-Integer Non Linear Optimisation: Algorithms and Application" consortium, which has received funding from the European Union's EU Framework Programme for Research and Innovation

Appendix B Robust counterpart of conic-representable uncertainty sets

We first start by recalling the following strong duality theorem for conic optimization problems.

Theorem 2 (Conic duality) If the following conic problem has a strictly feasible solution,

In the following example, we derive the robust counterpart for general ellipsoidal uncertainty sets.

Example 6 (Ellipsoidal uncertainty set) We consider the following ellipsoidal uncertainty set:

where P P P is a definite positive matrix. We consider the following robust counterpart:

Let F F F be a matrix such that P P P = F F F T F F F , we have

Applying the strong duality theorem, we obtain an equivalent minimization problem:

By inspection, we have λ λ λ = -F F F -T c c c and thus, one obtains

Note that if P P P is diagonal, i.e., P P P = diag(p 2 1 , . . . , p 2 n ), we have F F F = diag(p 1 , . . . , pn) and thus F F F -T = diag(1/p 1 , . . . , 1/pn). The resulting problem is therefore

Appendix C Generating quadratic functions for RCB-C-Q

In this appendix, we show how one can generate quadratic functions for the two-stage robust capital budgeting problem. We therefore consider an instance Ω for the RCB-C-Q. First, we generate linear functions (∆ L i ) i∈N in the same way as what was done for linear instances. Then, the goal becomes the one of finding a quadratic functions interpolating functions (∆ L i ) i∈N at the extreme points of [-1, 1] M . Thus, for each project i ∈ N , we want to find a convex quadratic function ∆ Q i such that

Moreover, we want to ensure that the global minimum of function ∆ Q i is attained at one of the extreme points of [-1, 1] M . To this end, let us introduce ξ ξ ξ

i,min such that

We then add the following constraints on ∆ Q i with ≥ 0 is a small number like 10 -4 :

Such a function may be generated by means of a semidefinite optimization solver. Finally, function ∆ Q i is shifted so that ∆ Q i (0) = 0.