Ayşe N Arslan

Boris Detienne

Decomposition-based approaches for a class of two-stage robust binary optimization problems

In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty where recourse decisions are restricted to be mixed-binary. For these problems, we present a deterministic equivalent formulation through the convexification of the recourse feasible region. We then explore this formulation under the lens of a relaxation, showing that the specific relaxation we propose can be solved using the branch-and-price algorithm. We present conditions under which this relaxation is exact, and describe alternative exact solution methods when this is not the case. Despite the two-stage nature of the problem, we provide NP-completeness results based on our reformulations. Finally, we present various applications in which the methodology we propose can be applied. We compare our exact methodology to those approximate methods recently proposed in the literature under the name K-adaptability. Our computational results show that our methodology is able to produce better solutions in less computational time compared to the K-adaptability approach, as well as to solve bigger instances than those previously managed in the literature.

Introduction and literature review

Robust optimization is an approach to handling uncertainty in optimization where the probability distributions are replaced with uncertainty sets. In robust optimization, constraints are imposed for all realizations whereas the objective function is evaluated for the worst-case realization within the uncertainty set. As such, in applications where the effects of uncertainty can be catastrophic, robust optimization presents itself as a viable modeling approach. Further, robust optimization models with polyhedral or convex uncertainty sets lead to deterministic equivalent formulations that are often in the same complexity class as their deterministic counterparts. For these reasons, robust optimization has enjoyed and continues to enjoy a growing attention from the research community. Advances in static robust optimization are presented in [START_REF] Ben-Tal | Robust optimization[END_REF], [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF] and [START_REF] Gabrel | Recent advances in robust optimization: An overview[END_REF].

On the other hand, robust optimization can sometimes be "over-conservative", especially when uncertainty does not have a row-independent structure. To remedy this problem, when the underlying application permits it, one might consider introducing recourse (adjustability/adaptability) after the realization of uncertainty. Further, some applications may naturally involve a set of "wait-and-see" decisions that are taken after the realization of uncertainty. This is the case, for instance, where strategic design decisions are undertaken by evaluating the future operational conditions of a system under uncertainty. In robust optimization with recourse, first-stage decisions are evaluated by taking the possibility to "recover" a feasible solution after the realization of uncertainty into account. The difficulty of these problems has long been established in the literature even in the simple case of two-stage adjustable robust optimization with linear programming problems in both stages, and a polyhedral uncertainty set (see [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]). We remark that another approach to deal with the over-conservativeness of static robust optimization is to consider distributionally robust uncertainty models (e.g. [START_REF] Goh | Distributionally robust optimization and its tractable approximations[END_REF]). However, its discussion is out of the scope of this paper. (3 -2.5ξ)y 1 + (-1 + 4ξ)y 2 + (4 -6ξ)y 3 s.t. y 1 + y 2 + y 3 ≤ x Its optimal solution is x = y 1 = y 2 = y 3 = 0, with objective value 0 (as when x = 1 the objective value is -0.5). Consider now the possibility to take decisions y after the realization of uncertainty. We write the adjustable robust optimization problem max In Figure 1, we present the functions (3 -2.5ξ), (-1 + 4ξ) and (4 -6ξ). The maximum of these three functions is to be minimized over ξ ∈ [0, 1] when x = 1. This is achieved at ξ = 0.61 and yields a value of 1.46. On the other hand when x = 0 the second-stage value is trivially 0. The optimal solution to the two stage problem is therefore x = 1 with value 0.46. Example 1.1 highlights the value of incorporating wait-and-see decisions into robust optimization. Strategic decisions are improved, by making a more judicious evaluation of the effects of uncertainty. It also demonstrates why doing so is not straightforward. Indeed, for each first-stage solution, evaluating its second-stage cost requires the solution of a bilevel optimization problem where the optimal solution of the outer level is not necessarily an extreme point of the corresponding feasible region.

Existing methodologies in robust adjustable optimization can be categorized as exact or approximate. Exact approaches do not pose any assumptions on the set of possible recourse actions aside from constraints imposed by the definition of the problem, whereas approximate approaches restrict possible recourse actions to either functions of the uncertain parameters or a preselected subset. On the other hand, all of the exact approaches in the literature consider two-stage models whereas approximations may extend to multiple stages.

Most approximate solution methods for adjustable robust optimization restrict the set of recourse solutions to more or less simple functions of uncertain parameters. These are referred to, in general, as "decision rules". In [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], authors study the complexity of the adjustable robust optimization problem with continuous recourse and propose a linear decision rule that they coin "affine-adjustability". In affine adjustability, continuous recourse decisions are expressed as affine functions of uncertain parameters where the parameters of this affine function are to be optimized. The authors prove that, when the recourse matrix is fixed, if the uncertainty set is tractable then the affinely adjustable robust optimization is tractable. More elaborate decision rule schemes have been explored in the context of robust optimization as well as stochastic and distributionally robust optimization. Some examples of this literature include but are not limited to, [START_REF] Chen | A linear decision-based approximation approach to stochastic programming[END_REF] where deflected and segregated linear decision rules are considered, [START_REF] Chen | Uncertain linear programs: Extended affinely adjustable robust counterparts[END_REF] where authors propose affine adaptability defined over an extended uncertainty set (extended affine adjustability), and [START_REF] Goh | Distributionally robust optimization and its tractable approximations[END_REF] where extended uncertainty sets are again used with piecewise linear decision rules (termed bi-deflected linear decision rules). In [START_REF] Kuhn | Primal and dual linear decision rules in stochastic and robust optimization[END_REF], authors apply linear decisions rules both in the primal and dual spaces to evaluate the optimality gap resulting from using linear decision rules. In [START_REF] Georghiou | Generalized decision rule approximations for stochastic programming via liftings[END_REF] this idea is further generalized to be applied in an extended probability space, encompassing piecewise linear, segregated, and nonlinear decision rules in the original space by a choice of the lifting operator while providing an a posteriori measure of the optimality gap resulting from using decision rules.

Although linear decision rules have desirable properties both from a theoretical and numerical perspective, their application is limited to adaptive problems with continuous recourse. Decision rules have therefore been extended to be able to incorporate binary and integer recourse decisions. In [START_REF] Vayanos | Decision rules for information discovery in multistage stochastic programming[END_REF], authors develop a conservative approximation for multistage robust MILPs presented in the context of information discovery in multistage stochastic programming. They partition the uncertainty set into hyperrectangles and restrict the continuous and binary recourse decisions to piecewise affine and constant functions of the uncertain parameter over each hyperrectangle, respectively. The resulting conservative approximation can be formulated as an MILP; see also [START_REF] Bram L Gorissen | A practical guide to robust optimization[END_REF]. In [START_REF] Bertsimas | Design of near optimal decision rules in multistage adaptive mixed-integer optimization[END_REF], authors propose a piecewise constant decision rule for binary recourse variables used in conjunction with a scenario generation scheme resulting in an endogenous design of the decision rule. In [START_REF] Bertsimas | Binary decision rules for multistage adaptive mixedinteger optimization[END_REF], piecewise constant functions are again used to describe linearly parameterized binary decision rules, the reformulated problem is mapped to an extended probability space to obtain a deterministic equivalent formulation through linear programming duality. Although the generic reformulation does not scale polynomially in problem data, instances where this is the case are presented.

Another line of recent research in the approximate solution methods literature is based on the idea of restricting the recourse to a preselected set of policies termed "K-adaptability" or "finite adaptability". The K-adaptability problem consists of selecting a first-stage solution along with K recourse solutions at the first stage. In the second stage, after the realization of uncertainty, the recourse problem reduces to selecting the best solution among these K solutions. As such, this approach is a restriction of the original two-stage problem where the flexibility of actions that can be taken at the second stage is reduced. We remark however that this method becomes exact for binary problems with only objective function uncertainty when K is sufficiently large. The authors of [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF] extend the idea of finite adaptability (K = 2) considered in [START_REF] Bertsimas | Finite adaptability in multistage linear optimization[END_REF], for two-stage robust optimization with pure binary recourse under objective function and right-hand-side uncertainty. They propose a direct solution as a mixed integer program after reformulation for fixed K. In [START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF], the concept of K-Adaptability is extended to problems with mixed-integer firstand second-stage feasible regions as well as uncertainty affected technology and recourse matrices. The authors propose a semi-infinite disjunctive programming formulation that imposes that at least one of the K recourse solutions be feasible for every realization of uncertainty. They then propose a branchand-bound algorithm combining ideas from semi-infinite and disjunctive programming. In [START_REF] Buchheim | Min-max-min robust combinatorial optimization[END_REF], authors study K-adaptability for combinatorial optimization problems in the special case where there are no firststage decisions, coined "min-max-min". For the same type of problems, [START_REF] Chassein | Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty[END_REF] propose faster algorithms, when K = 2 and the Bertsimas-Sim budgeted uncertainty set is used. While in these papers, a partition of the uncertainty set and an assignment of K recourse policies to subsets defined by this partition is sought concurrently, it is also possible to define the finite adaptability problem for a given partition of the uncertainty set. This partition is then iteratively improved using the information from the solution obtained. This idea is explored in [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF] and [START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF] in the context of multi-stage adjustable robust mixed-integer optimization.

Most of the exact approaches developed in the literature concern two-stage adjustable robust optimization with continuous recourse and right-hand-side uncertainty. In this case an epigraph formulation can be defined through Benders' type cuts obtained based on the linear programming dual where the subproblem used to identify violated cuts is bilinear. Decomposition-based approaches have been used in [START_REF] Jiang | Two-stage network constrained robust unit commitment problem[END_REF], [START_REF] Bertsimas | Adaptive robust optimization for the security constrained unit commitment problem[END_REF], and [START_REF] Zhao | Robust unit commitment problem with demand response and wind energy[END_REF] in the context of the well-known unit commitment problem under demand/wind uncertainty. They are presented in a generic framework based on Kelley's cutting plane algorithm in [START_REF] Thiele | Robust linear optimization with recourse[END_REF]. In [START_REF] Zhao | Robust unit commitment problem with demand response and wind energy[END_REF], authors additionally propose cutting planes expressed in the space of primal variables. They later develop this idea in [START_REF] Zhao | An exact algorithm for two-stage robust optimization with mixed integer recourse problems[END_REF], in a more general context and coin their methodology "constraint-and-column generation". This approach consists of adding a set of recourse variables and all the associated recourse constraints to the master problem for an identified uncertainty realization that is violated by the current restricted master. The subproblem in this case is a bilevel programming problem. This idea is further explored in [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF], which presents a mixed integer programming reformulation for the subproblem based on a Farkas system. Their reformulation is valid in the case where the uncertainty set can be represented as a projection of a binary set, the most important example being the Bertsimas-Sim budgeted uncertainty set. Finally, in [START_REF] Atamtürk | Two-stage robust network flow and design under demand uncertainty[END_REF], authors consider a network design problem under demand uncertainty where the flow decisions on certain arcs can be delayed until after the realization of uncertainty. As such, the recourse problem is a network flow problem with right-hand-side uncertainty. The authors give a projection of the recourse polyhedron to the space of the first-stage variables through an exponential family of inequalities. They propose a cutting-plane algorithm for the solution of this model and show that the separation problem is NP-hard except for some special cases. Ideas based on projection are explored in a more generic framework in [START_REF] Zhen | Adjustable robust optimization via Fourier-Motzkin elimination[END_REF] who show that two-stage robust optimization problems with continuous and fixed recourse can be cast as static problems via Fourier-Motzkin elimination.

There are few studies that consider exact approaches for two-stage adjustable robust optimization with integer recourse in the literature. In [START_REF] Zhao | Multi-stage robust unit commitment considering wind and demand response uncertainties[END_REF], the ideas presented in [START_REF] Zhao | An exact algorithm for two-stage robust optimization with mixed integer recourse problems[END_REF] are extended to the mixed-integer recourse case where the authors propose a nested constraint-and-column generation scheme. Unfortunately, approaches based on on-the-fly generation of uncertainty realizations are no longer finitely convergent when the uncertainty interferes in the objective function or the recourse matrix, as optimal solutions are not necessarily extreme points of the uncertainty set (see Figure 1). Further, their application seems to be restricted to the case where the optimal solution can be defined by adding a very small number of cuts. While this paper was in preparation, [START_REF] Kämmerling | Oracle-based algorithms for binary two-stage robust optimization[END_REF] proposed an oracle-based solution method for two-stage robust binary optimization problems with objective uncertainty. We provide a brief qualitative comparison of their approach to the approaches presented in this paper in Section 2.1.

As highlighted by the above review of the existing literature in the domain, there is a need for further research into exact solution methodologies for two-stage robust optimization problems with integer recourse. In this paper, we consider two-stage robust optimization problems of the form

min x∈X c x + max ξ∈Ξ min y∈Y(x) (f + Qξ) y (1)
where X ⊆ R N + , Y ⊆ R M + are bounded mixed binary sets, and Ξ ⊆ R S is a polyhedral set with c, x, ξ, f , Q, y of conforming dimensions. We assume throughout the paper that x = (x 1 , . . . , x N 1 , . . . , x N ) . We denote x 1 = (x 1 , . . . , x N 1 ) with x 1 ∈ {0, 1} N 1 , and consider

Y(x) = {y ∈ Y | Hy ≤ d -T x 1 }.
Therefore, the problems we consider in this paper are two-stage robust mixed-binary optimization problems with objective uncertainty.

Remark 1.1. We remark that both X and Y are mixed binary sets. However, the linking constraints in Y(x) involve only binary variables from the first-stage feasibility set.

The main contribution of this paper is providing an efficient algorithmic framework to solve the two-stage robust optimization problem (1) to exact optimality. This algorithmic framework is based on a relaxation of a reformulation of the original problem through the convexification of the second-stage feasible region. The necessary technical conditions for this relaxation to be exact are explored, resulting in the development of branch-and-price and branch-and-price-and-cut algorithms. The algorithmic development is supported by a comprehensive numerical study that compares the presented methodology to the related K-adaptability approaches. The results presented therein further pave the way to a theoretical complexity result that shows that the two-stage robust optimization problem (1) is N P -complete.

The remainder of this paper is organized as follows: in Section 2 we present a single-stage equivalent reformulation of (1) through convexification of the recourse feasible region, Y(x), and propose a computationally attractive relaxation of conv(Y(x)). The reformulations we obtain lead to deterministic equivalent models that can be solved using either the branch-and-price or the branch-and-price-and-cut algorithm. In Section 3, we present related complexity results. In Section 4, we illustrate two different applications of our methodology, and present a numerical evaluation of the proposed column generationbased approaches, comparing them to the direct solution of extended and K-Adaptability formulations. We conclude with future research directions and insights in Section 5.

Methodological development

In this section, we present the main results underlying our solution approach. We first present a result that allows us to write (1) as an equivalent deterministic problem. This equivalent formulation is based on the convexification of the recourse feasible region Y(x) for a given first-stage solution x ∈ X .

Proposition 2.1. Problem (1) is equivalent to min x∈X ,y∈conv(Y(x)) c x + max ξ∈Ξ (f + Qξ) y (2)
Proof. Proof For a given first-stage solution x ∈ X , and an uncertainty realization ξ ∈ Ξ, we have that min y∈Y(x)

(f + Qξ) y = min y∈conv(Y(x)) (f + Qξ) y (3)
as the inner minimization problem is a (linear) mixed integer programming problem. This observation allows for exchanging the order of optimization in max ξ∈Ξ min y∈conv(Y(x)) (f + Qξ) y using the wellknown minimax theorem (see [START_REF]Zur theorie der gesellschaftsspiele[END_REF]), as (f + Qξ) y is convex in y and concave in ξ, and the sets Ξ and conv(Y(x)) are convex by definition.

Proposition 2.1 has two important implications:

(i) When conv(Y(x)) = Y(x) for all x ∈ X , adaptability has no effect, i.e., the two-stage problem has the same optimal solution as the static robust problem. This is, for instance, the case when the recourse problem is a linear program or is an integer program with a totally unimodular constraint matrix (e.g. network flow problems).

(ii) If one can express the conditions y ∈ conv(Y(x)) for x ∈ X as mixed integer linear constraints, then a deterministic equivalent mixed integer programming formulation of (1) can be obtained.

Although point (ii) above suggests a generalized approach to reformulating (1) as a deterministic equivalent problem, expressing the conditions y ∈ conv(Y(x)) for x ∈ X remains a challenge. In general, given

x ∈ X , we may express conv(Y(x)) using its Dantzig-Wolfe reformulation, i.e., as a convex combination of its extreme points. However, as conv(Y(x)) is dependent on x, we additionally need to impose a relationship between x and conv Y(x) (in other words, a recourse solution from conv(Y(x)) can be selected only if the first-stage solution x is selected). In Figure 2, we illustrate the resulting deterministic equivalent feasible region with two possible first-stage solutions. As should be clear from this figure, the feasible region is made up of two disjunctions, each describing a recourse polyhedron based on the first-stage solution selected.

conv(Y(0)) conv(Y(1))

(x) = {y ∈ {0, 1} 3 | y 2 ≤ x, -y 1 + 2y 2 + y 3 ≥ 3x -2}, with x ∈ {0, 1}.
Based on Figure 2, it is clear that the dependence of the set Y(x) on variables x is the main difficulty prohibiting the numerically efficient use of solution methods based on Dantzig-Wolfe decomposition. In Section 2.1, we present a relaxation of (2) that overcomes this difficulty. In Section 2.2, we use this relaxation to solve [START_REF] Atamtürk | Two-stage robust network flow and design under demand uncertainty[END_REF] to optimality under an assumption on the structure of the linking constraints.

We also adapt the branch-and-price and branch-and-price-and-cut algorithms to this context. Finally, in Section 2.3, reposing on a reformulation of (1) in an extended space, we generalize the results of Section 2.2 to cases where the assumption on the structure of linking constraints does not hold.

A computationally convenient relaxation

We define, for x ∈ X , the set

Ȳ(x) = {y ∈ conv(Y) | Hy ≤ d -T x 1 } .
Figure 3 illustrates the sets conv(Y(x)) and Ȳ(x) on an example with two binary variables. As the illustration suggests, conv(Y(x)) is a subset of Ȳ(x). We formalize this result in the following proposition. conv(Y(x)) Ȳ(x) Proof. Proof Let y ∈ conv(Y(x)), we show that y ∈ Ȳ(x). Firstly, as conv(Y(x)) ⊆ conv(Y), then it trivially holds that y ∈ conv(Y). Further, we have that Hy ≤ d -T x 1 since y is a convex combination of points that satisfy this constraint. The result follows. Proposition 2.2 directly leads to a relaxation of problem (1) and its deterministic equivalent reformulation [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF]. We have:

min x∈X ,y∈conv(Y(x)) c x + max ξ∈Ξ (f + Qξ) y ≥ min x∈X ,y∈ Ȳ(x) c x + max ξ∈Ξ (f + Qξ) y.
By replacing conv(Y(x)) with Ȳ(x) in (2), we no longer perform the convexification operation on a set that is dependent on x ∈ X . We may therefore express the conditions y ∈ Ȳ(x) by directly imposing the linking constraints Hy ≤ d -T x 1 on conv(Y).

To this end, let ȳj for j ∈ L = {1, . . . , L} be the extreme point solutions of conv(Y) and denote the ndimensional simplex α ∈ [0, 1] n n j=1 α j = 1 for n ∈ N by ∆ n . Using this notation, we have that

Ȳ(x) =    j∈L α j ȳj H j∈L α j ȳj ≤ d -T x 1 , α ∈ ∆ L    .
We may therefore write the relaxation of (1) as:

(R) : min c x + max

ξ∈Ξ (f + Qξ) j∈L α j ȳj (4) s.t. H j∈L α j ȳj ≤ d -T x 1 (5) x ∈ X , α ∈ ∆ L . (6)
The computational advantage of relaxation ( 4)-( 6) is clear. After reformulating the inner maximization problem in ξ, this equivalent formulation can be solved using a branch-and-price algorithm, adding the columns ȳj ∈ Y to the master problem as needed and branching when solutions x are fractional. We remark that unlike in a typical branch-and-price framework, here the variables α are continuous, i.e., no integrality restrictions are imposed on the reformulated variables y. This is by definition of (1) where one can choose a different recourse solution y for each realization of uncertainty. For instance, for the problem of Example 1.1 the optimal recourse value is found as a convex combination of solutions y 1 = 1 and y 2 = 1.

An alternative relaxation building on Proposition 2.1 was proposed by [START_REF] Kämmerling | Oracle-based algorithms for binary two-stage robust optimization[END_REF], and used in a specialized implicit enumeration algorithm to determine optimal solutions. This relaxation can be expressed as an exponential-size LP model which is solved by a cutting plane algorithm. In this framework, each cut corresponds to a complete solution of the initial problem, i.e., a pair of first-and second-stage solutions, and expresses its cost as a linear function of uncertain parameters. The separation problem identifies the best complete solution given a fixed vector of uncertain parameters. This approach can be used for non-linear optimization problems, as long as it is possible to express the cost of a solution as a linear function of the uncertain parameters. This flexibility comes at the price of having to solve subproblems in the X × Y space (i.e. optimize over {(x, y)|x ∈ X , y ∈ Y(x)}), and an ad-hoc branching scheme.

The approach presented in this paper exploits the decomposition of the first and second stages that is naturally present in the structure of problem [START_REF] Atamtürk | Two-stage robust network flow and design under demand uncertainty[END_REF]. As many decomposition approaches, it is well-suited when optimizing a deterministic function over sets X and Y separately is significantly easier than optimizing it over X × Y. By reposing on the well-known paradigms of Dantzig-Wolfe decomposition and the branch-and-price algorithm, it is easier to implement in practice, especially with the increasing availability of automatic decomposition software. However, as the pricing of second-stage variables requires LP duality, naturally nonlinear formulations can be handled only after an appropriate linearization.

We conclude this section by presenting an equivalent deterministic MILP formulation of (R), that allows both a theoretical characterization of the complexity of the problem, and development of solution algorithms. To do so, we first dualize the inner maximization problem in (4)

max ξ∈Ξ (f + Qξ) j∈L α j ȳj (7)
which is a linear programming problem as we assume that Ξ is a polyhedral set. We write, without loss of generality, that Ξ = ξ ∈ R S Aξ ≤ b with A ∈ R S ×S and b ∈ R S . Let u ∈ R S + be the dual variables associated with the constraints of the uncertainty set. We then have that

max ξ∈Ξ (f + Qξ) j∈L α j ȳj = f j∈L α j ȳj + min u∈R S + u b (8) s.t. A u = Q j∈L α j ȳj . (9)
Therefore the deterministic equivalent of the formulation ( 4)-( 6) is expressed as:

min c x + f j∈L α j ȳj + u b (10) s.t. H j∈L α j ȳj ≤ d -T x 1 (11)
A u = Q j∈L α j ȳj ( 12
) j∈L α j = 1 (13) x ∈ X , α ∈ R L + , u ∈ R S + . (14)

Exact formulations based on relaxation (R)

In this section, we present two key results that enable the exact solution of problem (1) based on relaxation (R) and its deterministic equivalent model ( 10)-( 14). The first result establishes certain cases where the relaxation (R) is exact, whereas the second result provides a family of valid inequalities that cut off infeasible solutions when this is not the case. To present them, we need the following additional assumption.

Assumption 2.1. We let y = (y 1 , . . . , y M 1 , . . . , y M ) , and denote

y 1 = (y 1 , . . . , y M 1 ) with y 1 ∈ {0, 1} M 1 . We assume in the following that Y(x) = {y ∈ Y | Hy 1 ≤ d -T x 1 }.
Assumption 2.1 guarantees that the set of extreme points of conv(Y(x)) is a subset of the set of extreme points of conv(Y) as illustrated in the following example. (a) In Figure 4, we present the sets conv(Y(0)) and Ȳ(0) for these two variants. As is clear from this figure, the set conv(Y(0)) is described by the extreme points of conv(Y) for the first variant, whereas the additional extreme point (0.5, 1) is required in the description of conv(Y(0)) for the second variant. We remark that this new extreme point is created by the intersection of the set Y with the linking constraint y 1 + y 2 ≤ 1.5 + x. Intuitively, Assumption 2.1 guarantees that the linking constraints always intersect with a lattice free set (see e.g. [START_REF] Laurence | Integer and combinatorial optimization[END_REF]), therefore do not create additional extreme points. Let x i for i ∈ K = {1, . . . , K} be the extreme point solutions of conv(X ). Further let ȳj for j ∈ L = {1, . . . , L} be the extreme point solutions of conv(Y) as before, and define,

( 0 0 ) ( 1 0 ) ( 0 1 ) ( 1 1 ) (b)
( 0.5 1 ) ( 0 0 ) ( 1 0 ) ( 0 1 ) ( 1 1 ) conv(Y(0)) Ȳ(0) Y
L i = {j ∈ L | H ȳj 1 ≤ d-T x i 1 } for i ∈ K.
We first present an intermediary result that allows the characterization of conv(Y(x)) in terms of the extreme points of the set conv(Y).

Proposition 2.3. conv(Y(x i )) = j∈L i α j ȳj α ∈ ∆ |L i | for i ∈ K. Proof. Proof Given i ∈ K, let ext(Y(x i )) denote the set of extreme point solutions of conv(Y(x i )). Let y ∈ ext(Y(x i )) ⊆ Y(x i ) = y ∈ Y Hy 1 ≤ d -T x i 1 .
Since y ∈ Y, there exists α ∈ ∆ |L| such that y = j∈L α j ȳj . Further, for all r ∈ L such that α r > 0, we must have that ȳr 1 = y 1 , as otherwise there exists a row index such that j∈L α j ȳj

1 ∈]0, 1[. It follows that H ȳr 1 ≤ d -T x i
1 for all r ∈ L such that α r > 0, and therefore r ∈ L i following the definition of L i . This shows that ext(Y(x i ))

⊆ j∈L i α j ȳj α ∈ ∆ |L i | , and as a consequence that conv(Y(x i )) ⊆ j∈L i α j ȳj α ∈ ∆ |L i | .
Conversely, take any solution ȳj for j ∈ L i . By definition of the set L i , we have that ȳj ∈ Y, and that

H ȳj 1 ≤ d -T x i 1 . It follows that ȳj ∈ Y(x i
) and therefore can be expressed as a convex combination of points y ∈ ext(Y(x i )). Therefore

j∈L i α j ȳj α ∈ ∆ |L i | ⊆ conv(Y(x i ))
, proving the result.

We next present a result that characterizes a sufficient condition for the equivalence between conv(Y(x)) and Ȳ(x) for x ∈ X . Proof. Proof Under the given assumptions, Y(x) = {y ∈ Y | y 1 ≤ x 1 }. Assume now that there exists a solution y such that y = j∈L α j ȳj ∈ Ȳ(x) and y / ∈ conv(Y(x)). Then, we must have that j∈L α j = 1 and j∈L| ȳj 1 ≤x 1 α j < 1 by using the characterization of Proposition 2.3. This implies the existence of a linking constraint, say constraint i, and an index k ∈ L such that ȳk i > x i and α k > 0. Since x i ∈ {0, 1} and ȳk i ∈ {0, 1}, we must have that x i = 0 and ȳk i = 1. We may therefore write,

y i = j∈L ȳj i α j ≥ α k ȳk i = α k > 0 = x i
Thus y / ∈ Y(x), which contradicts the assumption that y ∈ Ȳ(x). Therefore, we have proved Ȳ(x) ⊆ conv(Y(x)). We additionally have that conv(Y(x)) ⊆ Ȳ(x) by Proposition 2.2. As a result Ȳ(x) = conv(Y(x)).

Example 2.2. Consider the second-stage feasibility set

Y(x) = y ∈ {0, 1} 2 | y i ≤ x i ∀i = 1, 2
with X = {0, 1} 2 . Let L = {1, . . . , 4} and ȳ1 = (1, 0), ȳ2 = (0, 1), ȳ3 = (0, 0), and ȳ4 = (1, 1). Associating α j ≥ 0 with ȳj for j ∈ L, it is easy to confirm that Ȳ

(x) = j∈L α j ȳj α 1 + α 4 ≤ x 1 , α 2 + α 4 ≤ x 2 , α ∈ ∆ 4 . Further, by Proposition 2.3, we have that conv(Y(x)) = j∈L ȳj α j j∈L | ȳj i ≤x i ,∀i=1,2 α j = 1, α ∈ ∆ 4 .
It can easily be verified that conv(Y(x)) = Ȳ(x) for x ∈ X . This equivalence is a direct consequence of Proposition 2.4.

Problems of form (1) that satisfy Assumption 2.1 and have the structure presented in Proposition 2.4, can be solved using the deterministic equivalent model ( 10)-( 14) based on relaxation (R), which, in this case, is exact. These include, by a substitution of variables, problems with linking constraints of type y 1 ≥ x 1 , x 1 + y 1 ≤ 1, x 1 + y 1 ≥ 1 and 1 y 1 ≤ x that cover a wide range of applications. As the number of extreme points of the set Y are in general prohibitively large, we propose to solve this relaxation using the branch-and-price algorithm generating columns from the set Y and branching when x 1 is fractional.

We next outline the main components of this branch-and-price algorithm starting with the restricted master problem. The complete branch-and-price scheme is presented in Algorithm 1 in Section 6.3 of the Appendix. Let us recall that ȳj for j ∈ L = {1, . . . , L} are the extreme point solutions of conv(Y), and let L R ⊂ L. Further, assume without loss of generality that

X = {x ∈ {0, 1} N 1 × R N -N 1 | Gx ≤ g}.
The restricted master problem is then written as:

(M P (L R )) : min c x + f j∈L R α j ȳj + u b (15) s.t. Gx ≤ g (16)
H j∈L R α j ȳj ≤ d -T x 1 (17)
A u = Q j∈L R α j ȳj ( 18
) j∈L R α j = 1 (19) x ∈ [0, 1] N 1 × R N -N 1 , α ∈ R |L R | + , u ∈ R S + . (20)
Let π * , µ * , and λ * be the optimal values of the dual variables associated with the constraints ( 17), [START_REF] Georghiou | Generalized decision rule approximations for stochastic programming via liftings[END_REF], and [START_REF] Goh | Distributionally robust optimization and its tractable approximations[END_REF], respectively. Then the pricing problem takes the form:

(P ricing(π * , µ * , λ * )) : min y∈Y -λ * + f -H π * + Q µ * y (21)
Remark 2.1. The pricing problem [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF] is free of the first-stage variables x.

Once the restricted master problem M P (L R ) is solved to optimality, generating columns ȳj for j ∈ L \ L R as needed, yielding the optimal relaxation solution (x * , α * ), one typically needs to branch in order to obtain integer solutions. As the integrality of variables y is not required in this case, we branch only on fractional x 1 variables. Let i ∈ {1, . . . , N 1 } such that x * i ∈]0, 1[. The branching constraints x * i ≤ 0 and x * i ≥ 1 are added to the restricted master problem, for the left and right children of the current node, respectively. These constraints do not affect the pricing problem.

We now turn our attention to the case where conv(Y(x)) = Ȳ(x) for some x ∈ X . We motivate our main result with the following example.

Y(x) = {y ∈ {0, 1} 2 | 1 y ≤ 1, x 1 + 2x 2 + y 1 + y 2 ≥ 1.9} with X = {x ∈ {0, 1} 2 | 1 x ≤ 1}. Let L = {1, .
. . , 3} and ȳ1 = (1, 0), ȳ2 = (0, 1) and ȳ3 = (0, 0). Let us consider x * = (1, 0) and associate α j ≥ 0 with ȳj for j ∈ L.

We have that Ȳ(x * ) = j∈L α j ȳj α 1 + α 2 ≥ 0.9, α ∈ ∆ 3 . Further we have that conv(Y(x * )) = j∈L α j ȳj

j∈L|ȳ j 1 +ȳ j 2 ≥0.9 α j = 1, α ∈ ∆ 3 = j∈L α j ȳj α 1 + α 2 = 1, α ∈ ∆ 3 by Proposition 2.3. It is clear that, conv(Y(x * )) = Ȳ(x * ). More specifically, in Ȳ(x * ), one can use the extreme point ȳ3 = (0, 0) / ∈ Y(x * ) with α 3 ≤ 0.1, whereas α 3 = 0 in conv(Y(x * )).
To establish an equivalence between conv(Y(x)) and Ȳ(x), one needs to forbid the use of extreme point ȳ3 in Ȳ(x * ). This is achieved by adding the inequality α 3 ≤ 1-x 1 +x 2 to Ȳ(x). It can be verified that, with the addition of this inequality, Ȳ(x) = conv(Y(x)) for x ∈ X .

In the following proposition, we generalize the inequality we have introduced in Example 2.3 to no-good cut type inequalities (see e.g. [START_REF] Hooker | Logic-based methods for optimization[END_REF]). To this end, let N = {1, . . . , N 1 }, and define

I(x) = {i ∈ N | x i = 1} for x ∈ X . Further, let for I ⊆ N , L(I) = j ∈ L H ȳj 1 ≤ d -T i∈I e
i where e i is the i th unit vector of conforming dimensions.

Proposition 2.5. The inequalities j∈L\L(I)

α j ≤ |I| - i∈I x i + i∈N \I x i ∀I ⊆ N (22)
are valid for conv(Y(x)) = j∈L(x) α j ȳj | α ∈ ∆ |L(x)| .
Proof. Proof Given x ∈ X , we show that, if α ∈ ∆ |L| and j∈L α j ȳj ∈ conv(Y(x)) then it satisfies inequalities [START_REF] Hooker | Logic-based methods for optimization[END_REF]. In this case, by definition of conv(Y(x)), we must have that α j = 0 for all j ∈ L\L(I(x)). Therefore, if I(x) = I then we have that 0 ≤ 0. Otherwise, we have that either i∈I x i < |I| or i∈N \I x i > 0. Therefore, we have on the left-hand-side j∈L\L(I) α j which is not greater than 1, and on the right-hand-side |I| -i∈I x i + i∈N \I x i > 0, which is greater than 1 by integrality of the terms involved, for all I ⊆ N , I = I(x).

Proposition 2.6. Let α ∈ ∆ |L| such that j∈L α j ȳj ∈ Ȳ(x) and α j > 0 for some j ∈ L \ L(I(x)), then there exists an inequality of form [START_REF] Hooker | Logic-based methods for optimization[END_REF] that is violated.

Proof. Proof Let, in this case, I = I(x). We have on the left-hand-side j∈L\L(I(x)) α j > 0 and on the right-hand-side |I(x)| -i∈I(x) x i + i / ∈I(x) x i = 0. Therefore, inequality [START_REF] Hooker | Logic-based methods for optimization[END_REF] with I = I(x) is violated.

Propositions 2.5 shows that inequalities [START_REF] Hooker | Logic-based methods for optimization[END_REF] are valid for conv(Y(x)), and Proposition 2.6 establishes that they are sufficient to describe conv(Y(x)) for x ∈ X . As a result we may write an equivalent formulation for (2) as follows:

min c x + f j∈L α j ȳj + u b (23) s.t. H j∈L α j ȳj 1 ≤ d -T x 1 (24)
A u = Q j∈L α j ȳj [START_REF] Kuhn | Primal and dual linear decision rules in stochastic and robust optimization[END_REF] j∈L\L(I)

α j ≤ |I| - i∈I x i + i∈N \I x i ∀I ⊆ N ( 22
) j∈L α j = 1 (26) x ∈ X , α ∈ ∆ L , u ∈ R S + . (27)
As this formulation has an exponential number of variables and constraints, we propose to couple column generation with cut generation within a branch-and-price-and-cut algorithm in its solution, which is described by Algorithm 1 presented in Section 6.3 of the Appendix. We next outline the main changes to the branch-and-price algorithm proposed earlier. An initial restricted master problem and the associated pricing problem are given by ( 15)-( 20) and ( 21), respectively, assuming that L R is used as the initial set of columns and no cuts are added. Compared to our previous algorithm, the identification of violated cuts [START_REF] Hooker | Logic-based methods for optimization[END_REF], and the changes to the pricing problem resulting from their addition need to be addressed.

We first discuss the identification of violated cuts of type [START_REF] Hooker | Logic-based methods for optimization[END_REF] given a candidate incumbent solution (x * , α * ) with x * 1 ∈ {0, 1} N 1 . In this case, it suffices to verify whether or not inequality [START_REF] Hooker | Logic-based methods for optimization[END_REF] with I = I(x * ) is satisfied as the proof of Proposition 2.6 suggests. If it is satisfied then (x * , α * ) is accepted as an incumbent solution and the current upper bound is updated. Otherwise, the cut

j∈L\L(I(x * )) α j ≤ |I(x * )|-i∈I(x * ) x i + i∈N \I(x * )
x i is added to the current restricted master. We remark that, identifying columns that are not feasible for a given first-stage solution x (j ∈ L \ L(I(x))) is not complicated, as it suffices to verify whether or not H ȳj 1 ≤ d-T i∈I(x) e i for current columns in the restricted master. On the other hand, handling the changes induced by the introduction of cuts [START_REF] Hooker | Logic-based methods for optimization[END_REF] in the pricing problem is more computationally demanding. Consider a subset of cuts [START_REF] Hooker | Logic-based methods for optimization[END_REF] added to the restricted master M P (L R ):

j∈L\L(I) α j ≤ |I| - i∈I x i + i∈N \I x i ∀I ∈ N R . (28)
Let η * I be the optimal value of the dual variable associated to I ∈ N R . The pricing problem (21) takes the form

min j∈L - I∈N R |j / ∈L(I) η * I -λ * + f -H π * + Q µ * ȳj . ( 29
)
Casting this problem as a mixed integer linear optimization problem over Y raises the issue of linearizing the first term in the objective function, which accounts for the dual values corresponding to added cuts [START_REF] Hooker | Logic-based methods for optimization[END_REF] in which the new column will be involved. To this end, consider the indicator variable z I for I ∈ N R that takes value 1 if and only if ȳj ∈ L \ L(I), i.e., H ȳj 1 + T i∈I e i -d > 0. The updated pricing problem then takes the form

(P ricing (π * , µ * , λ * , η * )) : min - I∈N R η * I z I -λ * + f -H π * + Q µ * y (30) s.t. M z I ≥ H ȳj 1 + T i∈I e i -d ∀I ∈ N R (31) y ∈ Y, z I ∈ {0, 1} |N R | ( 32
)
where M is a sufficiently large constant.

We conclude this section by comparing the branch-and-price-and-cut approach to the methodologies presented under the name constraint-and-column generation in the literature (see [START_REF] Zhao | Multi-stage robust unit commitment considering wind and demand response uncertainties[END_REF]). In constraintand-column generation, a deterministic equivalent formulation inspired by stochastic programming is dynamically constructed. In this scheme, a block of variables and constraints is appended to the master problem for each violated scenario. As a result, columns correspond to variables y ξ , associated to each violated scenario ξ, for which the values should be determined by the solution of the master. The constraints correspond to the set of linking constraints and constraints describing Y for each y ξ (which renders the on-the-fly generation difficult). Further, violated scenarios are identified by solving a bilinear problem, which can be very challenging. On the other hand, we propose to generate columns that correspond to the extreme points of Y, and generate at most one cut of type [START_REF] Hooker | Logic-based methods for optimization[END_REF] for each candidate solution. The difficulty of the pricing problem is the same as optimizing a linear function over the set Y.

An exact extended deterministic equivalent formulation

The results of Section 2.2 allow the exact solution of problem (1) when Assumption 2.1 is satisfied, i.e., when the linking constraints are expressed only in terms of the binary variables in the set Y. In this section, we propose a reformulation in an extended space that enables us to exploit those results even when problem (1) does not naturally present in a form that satisfies this assumption. In other words, we present an alternative formulation of the recourse feasible region Y(x), that allows transforming problem (1) into a problem that satisfies Assumption 2.1. The reformulation we propose additionally produces problems that satisfy the assumptions of Proposition 2.4. The main result of this section is therefore showing that problem (1) can be solved using the branch-and-price algorithm of Section 2.2 regardless of the structure of the linking constraints after an appropriate reformulation of the set Y(x).

To this end, let z ∈ {0, 1} N 1 , and consider the reformulation of the recourse feasible region as

Y (x) = y ∈ Y, z ∈ {0, 1} N 1 Hy ≤ d -T z, z ≤ x 1 , z ≥ x 1 ,
essentially incorporating a copy of the first-stage decision variables x 1 and the linking constraints Hy ≤ d -T x 1 to the recourse feasible region. We remark that it suffices to copy only those first-stage variables that are involved in the linking constraints. The advantage of this reformulation is that, the constraints Hy ≤ d -T z are expressed purely in terms of recourse variables and therefore can be incorporated to the subproblem. The new linking constraints z = x 1 ensure that the generated columns belong to the set conv(Y(x)) for x ∈ X . Consider now the extended formulation obtained by creating a copy of the variable x in the second-stage feasible region, we write:

Y (x) = (y, z) ∈ [0, 1] × {0, 1} 2 y 1 + y 2 ≤ 1.5 + 0.5z z = x .
In this reformulation the constraint y 1 + y 2 ≤ 1.5 + 0.5z is part of the definition of the set Y. We have that conv(Y) = {(y, z) ∈ [0, 1] 3 | y 1 + 0.5y 2 ≤ 1 + 0.5z} which is illustrated in grey in Figure 5 Let Y = y ∈ Y, z ∈ {0, 1} N 1 Hy ≤ d -T z and ( ȳ, z) j for j ∈ L = {1, . . . , L } be the extreme point solutions of conv(Y ). We may then write problem (2) as:

min c x + f j∈L α j ȳj + u b (33) s.t. x 1 = j∈L α j zj ( 34
) A u = Q j∈L α j ȳj ( 35
) j∈L α j = 1 (36) x ∈ X , α ∈ R L + , u ∈ R + . (37)
Formulation ( 33)-( 37) provides a generic formulation for problem [START_REF] Atamtürk | Two-stage robust network flow and design under demand uncertainty[END_REF], where the linking constraints [START_REF] Laurence | Integer and combinatorial optimization[END_REF] involve only binary second-stage variables, i.e., satisfy Assumption 2.1, and satisfy assumptions of Proposition 2.4 (writing z ≤ x 1 and z ≥ x 1 ). It can therefore be solved using the branch-and-price algorithm (Algorithm 1) presented in Section 6.3 of the Appendix, generating columns from the set Y , and branching when the variables x 1 are fractional.

Although formulation ( 33)-( 37) has desirable theoretical properties, its numerical efficiency depends on the dimension of the reformulation Y (x). To this end, we remark that the ideas presented in this section can be used for a subset of the x 1 variables. Indeed, it suffices to create copies of those first-stage variables that are involved in linking constraints that do not satisfy Assumption 2.1 or the conditions of Proposition 2.4. We conclude this section with an example illustrating this idea.

Example 2.5. Consider the second-stage feasibility set

Y(x, x 0 ) = y ∈ {0, 1} 2 y 1 + y 2 ≤ 1.5 + 0.5x 0 y i ≥ x i ∀i = 1, 2 with X = {0, 1} 3 .
Here the linking constraints follow Assumption 2.1. However, the linking constraint y 1 + y 2 ≤ 1.5 + 0.5x 0 does not follow the assumption of Proposition 2.4, although constraints y i ≥ x i for i = 1, 2 do. We remark that Ȳ(x) = conv(Y(x)) for x ∈ X .

Consider x * = (0, 0, 0). We have that conv

(Y(x * )) = {y ∈ [0, 1] 2 | y 1 + y 2 ≤ 1} and that Ȳ(x * ) = {y ∈ [0, 1] 2 | y 1 + y 2 ≤ 1.
5}. This is illustrated in Figure 6(a).

Consider now the extended formulation obtained by creating a copy of the variable x 0 in the second-stage feasible region, we write:

Y (x, x 0 ) =    (y, z) ∈ {0, 1} 3 y 1 + y 2 ≤ 1.5 + 0.5z y i ≥ x i ∀i = 1, 2 z = x 0    .
In this reformulation the constraint y 1 + y 2 ≤ 1.5 + 0.5z 0 is part of the definition of the set Y. We have that conv(Y ) = {(y, z) ∈ [0, 1] 3 | y 1 + y 2 ≤ 1 + z} which is illustrated in grey in Figure 5

(b). It follows that, Ȳ (x) = {(y, z) ∈ conv(Y) | y i ≥ x i ∀i = 1, 2, z = x 0 } = {(y, z) ∈ [0, 1] 3 | y 1 + y 2 ≤ 1 + z, y i ≥ x i ∀i = 1, 2, z = x 0 }.
As a result, Ȳ (x * ) is the face highlighted in red in Figure 5(b) which is also equal to conv(Y (x * )). Indeed, Ȳ (x) = conv(Y (x)) for x ∈ X by Proposition 2.4 as the new linking constraint z = x 0 , along with the linking constraints y i ≥ x i for i = 1, 2 follow its assumptions.

Reformulation through enumeration

In this section, we present an alternative formulations of (1) in certain special cases. It is based on the idea of enumerating the first-and second-stage feasible solutions and creating an uncertainty vector corresponding to each first-stage solution. Writing such a formulation in theory for pure binary sets X and Y is always possible but in practice is only viable when X and Y are easily enumerable. Although direct solution of this formulations is extremely time/memory consuming for larger instances, it provides benchmarks for evaluating the computational efficacy of the column generation-based approach proposed above. In this section, we assume that X and Y are pure binary sets. Let us denote by x i , for i ∈ K = {1, . . . , K}, the feasible solutions of X . For i = 1, . . . , K, let y i,j ∈ Y(x i ) for j ∈ L i = 1, . . . , L i be the feasible solutions of Y(x i ). We write max θ (38)

s.t. θ ≤ θ i ∀i ∈ K (39) θ i ≤ c T x i + (f + Qξ i ) T y i,j ∀i ∈ K, j ∈ L i ( 40
)
ξ i ∈ Ξ ∀i ∈ K. ( 41
)
Proposition 2.7. Linear program (38)-( 41) is a formulation of (1).

Proof. Consider a first-stage feasible solution x i ∈ X . We write the inner optimization problem corresponding to this solution:

max ξ i ∈Ξ min y∈Y(x i ) (f + Qξ i ) T y
and its corresponding epigraph formulation by enumerating the feasible solutions of Y(x i ):

max θ i ∈R,ξ i ∈Ξ θ i s.t. θ i ≤ (f + Qξ i ) T y i,j ∀j ∈ L i
As a result, we may write the objective value of the solution x i as max

θ i ∈R,ξ i ∈Ξ θ i s.t. θ i ≤ c T x i + (f + Qξ i ) T y i,j ∀j ∈ L i .
Problem (1) can then be expressed as

min i∈K θ i s.t. θ i ≤ c T x i + (f + Qξ i ) T y i,j ∀j ∈ L i ξ i ∈ Ξ or equivalently, max θ s.t. θ ≤ θ i ∀i ∈ K θ i ≤ c T x i + (f + Qξ i ) T y i,j ∀i ∈ K, ∀j ∈ K i ξ i ∈ Ξ ∀i ∈ K

Complexity results

Min-max-min problems, even with linear objective and constraints, are in general (most probably) harder than NP-complete problems (i.e., in the second or third level of the polynomial hierarchy). Falling into this category, two-stage robust problems with integer recourse are often suspected to be outside of class NP. For example, in [START_REF] Bertsimas | Robust and Adaptive Network Flows[END_REF], the authors study such a robust network flow problem which is shown to be NP-hard and yet admits a strong dual. To explain this odd situation, they conjecture that the problem and its dual are respectively Σ P 2 -and Π P 2 -complete. As a second example, [START_REF] Deineko | Pinpointing the complexity of the interval min-max regret knapsack problem[END_REF] show that a special case of the min-max regret knapsack problem with uncertain objective is Σ P 2 -complete. In this section, we show that despite the three-level structure of problem [START_REF] Atamtürk | Two-stage robust network flow and design under demand uncertainty[END_REF], it is NP-complete. First, formulation ( 10)-( 14) reveals that the problem of solving (R) actually lies inside the class NP (Proposition 3.1). Second, Section 2.3 shows that any problem of form ( 1) can be reformulated (by adding a polynomial number of variables and constraints) as a problem for which relaxation (R) is exact. Therefore, problem (1) is NP-complete (Theorem 1) as it can be solved through its (exact) relaxation (R) using model ( 10)-( 14) or model ( 33)- [START_REF] Zhao | Robust unit commitment problem with demand response and wind energy[END_REF]. In the following, we formalize these results starting with the decision problem associated to solving (R).

Problem: Relaxed Two Stage Robust MILP (R2SRMILP) Input data: Integer η, positive integers N = p + p , N , M = q + q , M , M , S, S , first-stage data Proof. The problem is trivially NP-hard, since choosing M = 0 makes the problem a general MILP. To show that it lies inside NP, let us assume that the answer of R2SRMILP is Yes. It follows that there is a solution to ( 10)-( 14), whose cost is not larger than η. Moreover, using Carathéodory's theorem, there exists such a solution ( x, û, α) where the number Θ of non-zero entries of α is bounded above by a polynomial of M and S. Let θ(j) be the j th non-zero entry in α. Then, we can build a certificate C by concatenating the significant elements of ( x, û, α) and the description of the associated columns: C = x, û, αθ(j)

G ∈ Z N ×N , g ∈ Z N , c ∈ Z N , second-stage data E ∈ Z M ×M , e ∈ Z M , f ∈ Z M , Q ∈ Z M ×S , linking constraints data H ∈ Z M ×M , d ∈ Z M , T ∈ Z M ×N , uncertainty set data A ∈ Z S ×S , b ∈ Z S , such that X = {x ∈ N p × R p + : Gx ≤ g}, Y = {y ∈ N q × R q + : Ey ≤ e},
1≤j≤Θ , ŷθ(j) 1≤j≤Θ . The description of each column ŷθ(j) requires at most M integers, so that the size of C is bounded by a polynomial of the input data.

In order to prove the existence of a solution from a certificate C, one could verify that it provides a solution to ( 10)-( 14). However, checking that ŷθ(j)

1≤j≤Θ is indeed part of the model would require solving a NP-hard problem (checking that each ŷθ(j) is indeed an extreme point of Y). In order to design a polynomial-time algorithm processing C, we therefore write the equivalent formulation of ( 10)-( 14):

min c T x + f T y + u T b : Hy ≤ d -T x, A T u = Q T y, x ∈ X , y ∈ conv(Y), u ∈ R S + . ( 42
)
From C, one can check that ẏ = Θ j=1 αθ(j) ŷθ(j) ∈ conv(Y) by verifying that ŷθ(j) ∈ Y for all j ∈ {1, . . . , Θ} and Θ j=1 αθ(j) = 1. This can trivially be done in polynomial time with help of the mathe-matical programming representation of Y provided as an input of R2SRMILP. It then suffices to check the cost and the feasibility of ( x, ẏ, û) for the rest of (42).

Remark 3.1. This NP-completeness result does not depend on the restrictions over x 1 imposed in the definition of (1).

As a result of Proposition 2.4, problems of form (1) that satisfy its assumptions are equivalent to ( 4)-( 6), i.e., problem R2SRMILP, which leads to the following complexity result. Finally, the reformulation of (1) proposed in Section 2.3 allows us to show that this problem lies inside class NP as well.

Problem: Two Stage Robust MILP (2SRMILP) with binary first-stage variables Input data: Integer η, positive integers N = N 1 + p + p , N , M = q + q , M , M , S, S , first-stage data

G ∈ Z N ×N , g ∈ Z N , c ∈ Z N , second-stage data E ∈ Z M ×M , e ∈ Z M , f ∈ Z M , Q ∈ Z M ×S , linking constraints data H ∈ Z M ×M , d ∈ Z M , T ∈ Z M ×N , uncertainty set data A ∈ Z S ×S , b ∈ Z S , such that X = {x ∈ {0, 1} N 1 × N p × R p + : Gx ≤ g}, Y = {y ∈ N q × R q + :
Ey ≤ e}, and Ξ = {ξ ∈ R S : Aξ ≤ b} are bounded polyhedral sets. Let x 1 ∈ {0, 1} N 1 be the subset of binary first-stage variables, and

Y(x) = {y ∈ Y : Hy ≤ d -T x 1 } . Question: Does min x∈X ,y∈Y(x) c T x + max ξ∈Ξ (f + Qξ) T y ≤ η? Theorem 1. Problem 2SRMILP is NP-complete.
Proof. From any instance Π of 2SRMILP, one can build an equivalent instance Π satisfying Assumption 2.1, as shown in Section 2.3, whose size is polynomial in the size of Π. Instance Π is then equivalent to the related instance of R2SRMILP. Thus, solving any instance of 2SRMILP is equivalent to solving an appropriately constructed instance of R2SRMILP, whose size is polynomial in the size of Π.

Remark 3.2. This NP-completeness result does not depend on the restrictions over variables y. However, the restrictions posed on variables x 1 in the definition of (1) are necessary.

Numerical results

In this section we demonstrate the application of the methodologies developed in Section 2 in various contexts. We present numerical results on two applications, presenting a comparison between the branchand-price (B&P) algorithm, and the approaches from the K-adaptability literature with K = 2, 3, 4: the monolithic reformulation approach presented in [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF] (2-,3-,4-AdaptM), and the semi-definite programmingbased branch-and-bound algorithm presented in [START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF] (2-,3-,4-AdaptBB). A first application is a knapsack variant that gives the possibility to reject/produce or repair items in the second stage. It involves a recourse problem with knapsack-type constraints expressed purely in terms of recourse variables along with linking constraints of type y ≤ x. In this case, we may apply directly the result of Proposition 2.4 to show that the deterministic equivalent model ( 10)-( 14) based on relaxation (R) is exact. A second application is centered around a variant of the capital budgeting problem studied previously in K-Adaptability literature (see e.g. [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF], [START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF]). In this case, it turns out that the assumptions of Proposition 2.4 are not verified. As a result, we repose on the extended formulation proposed in Section 2.3.

To obtain optimal integer solutions to our formulations based on models ( 10)-( 14) and ( 33)-( 37), we use the C++ branch-and-price library BaPCod1 . At each node of the search tree, the linear relaxation of the problem is solved using column generation. The pricing sub-problems are solved using dynamic programming algorithms, using simple array-based forward label-correcting. At most one column is added to the master program at each iteration. To improve the convergence of the column generation procedure, we use stabilization by automatic smoothing of the dual variables of the master program, as described in [START_REF] Pessoa | Automation and combination of linear-programming based stabilization techniques in column generation[END_REF]. When the optimal solution of the corresponding relaxation does not satisfy the integrality requirements of first-stage variables x, one such fractional variable is chosen and two child nodes are created in order to exclude its current value from the search space. In order to reduce the size of the search tree, the branching choices are made with help of the strong branching technique, as described in [START_REF] Sadykov | Primal heuristics for branch and price: The assets of diving methods[END_REF]. The open nodes are processed according to the best first rule. At the root node, and each tenth processed node, a diving heuristic ( [START_REF] Sadykov | Primal heuristics for branch and price: The assets of diving methods[END_REF]) is used to derive a feasible solution and try to improve the best known primal bound. The diving heuristic is used only at nodes whose depth is at most ten. The implementations of the branch-and-price and pricing sub-problem solvers are sequential.

The branch-and-bound algorithm of [START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF] is adapted to each application using the authors' implementation available online 2 . All mixed integer linear programs, including mathematical models resulting from the monolithic reformulation of [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF] and linear programs inside the column generation procedures, are solved using IBM ILOG Cplex 12.9, through the C callable library, using default parameters and four threads.

All our experiments are conducted using a 2 Dodeca-core Haswell Intel Xeon E5-2680 v3 2.5 GHz machine with 128Go RAM running Linux OS. The resources of this machine are strictly partitioned using Slurm Workload Manager 3 to run several tests in parallel. The resources available for each run (algorithminstance) are set to 4 threads and a 20 Go RAM limit (we remark that our branch-and-price algorithms do not benefit from parallel processing). This virtually creates six independent machines, each running one single instance at a time. Sections 4.1 and 4.2 introduce the applications in detail, present the details of instances generated, and the results obtained.

Two-stage robust knapsack problem

Consider a two-stage robust knapsack problem with the set of items I = {1, . . . , I}. Each item has a weight c i and an uncertain profit pi ∈ [p i -pi , pi ] for i ∈ I where pi is the expected profit and pi is its maximum deviation. In this problem, a first stage decision is to choose a subset of items to produce. After this choice, a profit degradation factor

ξ ∈ Ξ = {ξ ∈ R I + | i∈I ξ i ≤ Γ, 0 ≤ ξ i ≤ 1} is revealed. We define p i (ξ) = pi -ξ i pi for i ∈ I.
After observing the profit degradation, there are three possible recourse actions:

(i) Produce the item as is, using c i units of the knapsack capacity, with the degraded profit pi -ξ i pi .

(ii) Repair the item, using an additional t i units of the knapsack capacity, recovering the original profit pi .

(iii) Outsource the item, with associated profit pi -f i where f i is the cost of outsourcing the item.

We next give a mathematical formulation for this problem. Let, for i ∈ I, x i denote the decision to produce item i in the first-stage, and y i = 1, r i = 1 and y i = 0 denote the decisions to produce without repair, repair or outsource item i in the second-stage, respectively. We then write, min x∈{0,1} I i∈I

(f i -pi )x i + max ξ∈Ξ min y,r∈Y(x) i∈I (p i ξ i -f i )y i -pi ξ i r i (43)
where

Y(x) =    y ∈ {0, 1} I , r ∈ {0, 1} I i∈I c i y i + t i r i ≤ C y i ≤ x i ∀i ∈ I r i ≤ y i ∀i ∈ I    .
As the linking constraints y i ≤ x i for i ∈ I conform with the assumption of Proposition 2.4, we can directly solve the deterministic equivalent formulation ( 10)-( 14), generating the columns from the generalized knapsack set:

Y = y ∈ {0, 1} I , r ∈ {0, 1} I i∈I c i y i + t i r i ≤ C r i ≤ y i ∀i ∈ I .
In this case, the pricing problem takes the form

-λ + min y,r∈Y i∈I (-f i + pi π i -µ i )y i - i∈I pi π i r i
which can be solved using an extension of the pseudo-polynomial dynamic programming algorithm for the classical knapsack problem. We additionally test a K-Adaptability approach to this problem, the associated model can be found in Section 6.1 of the Appendix.

Instance generation

For our numerical tests we generate instances inspired by those presented by [START_REF] Pisinger | Where are the hard knapsack problems?[END_REF]. These instances are categorized as uncorrelated (UN), weakly correlated (WC), almost strongly correlated (ASC), and strongly correlated (SC). For given number of items I, and parameters R = 1000, H = 100, h ∈ {40, 80}, δ ∈ {0.1, 0.5, 1}, we generate c i ∈ [1, R] for i ∈ I and C = h H+1 i∈I c i . The profit pi for i ∈ I is then generated based on the category of instances as follows:

pi = [1, R] for UN, pi ∈ [c i -R 20 , c i + R 20 ] for WC, pi ∈ [c i + R 10 -R 1000 , c i + R 10 + R 1000 ]
for ASC, and pi = c i + R 10 for SC. Based on pi , the maximum degradation factor pi for i ∈ I is generated in the interval [p i (1 -δ)/2, pi (1 + δ)/2] and the penalty of rejecting an item f i for i ∈ I is generated in the interval [1.1p i , 1.5p i ]. Finally, repair capacity t i for i ∈ I is generated depending on the category of instances as follows:

t i ∈ [1, c i ] for UN, t i ∈ [0.5p i -R 40 , 0.5p i + R 40 ] for WC, t i ∈ [0.5p i + c i 10 -R 1000 , 0.5p i + c i 10 + R 1000 ]
for ASC, and t i = 0.5p i + c i 10 for SC.

Results

In this section, we present our results on instances generated as described above. We solve instances with I ∈ {20, 30, 40, 50, 60, 70, 80} and generate 72 instances for each value of I, 18 in each instance category (UN,WC,ASC,SC), corresponding to each combination of the parameters h ∈ {40, 80}, δ ∈ {0.1, 0.5, 1}, and the uncertainty budget Γ ∈ {0.1I, 0.15I, 0.2I}.

We start by presenting, in Table 1, our results for 20-item instances with all solution methods considered. For these instances the time limit was set to 1 hour. In Table 1, #Conv represents the number of instances for which each method converged within the time limit. Time* represents the solution time (when converged) divided by the solution time of the branch-and-price algorithm. ConvGap(%) represents the percentage optimality gap reported by each method, that is the gap between the best primal and dual bounds found by the corresponding algorithm. OptGap(%) represents the percentage gap between the best primal solution reported by each method versus the optimal solution of the branch-and-price algorithm. #BestSol represents the number of instances for which each method was able to find the best primal solution, and #NotBestSol represents the number of instances for which this was not the case.

# Solution time ratios are reported as an average over instances solved to convergence within the time limit. Convergence gaps are reported as an average over instances not solved to convergence within the time limit. Optimality gaps are reported as an average over 72 instances.

As can be seen in the first column of Table 1, the branch-and-price algorithm converged for all instances considered, while the monolithic approach of [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF] converged for 41 when K = 2 and 8 when K = 3. This method did not converge for any of the instances considered when K = 4. Similarly, the branchand-bound algorithm of [START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF] converged for 44, 12 and 2 instances when K = 2, 3, and 4, respectively. A comparison of the average solution time for the branch-and-price algorithm to that of the other methods reveals the numerical promise of this approach. Not only did it solve the instances considered exactly, but it did so at least two orders of magnitude faster than other methods. On the other hand, although the gaps reported (ConvGap(%)) by K-adaptability methods were large, the primal solutions provided by these methods were on average within 1% (OptGap(%)) of the optimal solution provided by the branch-and-price algorithm.

The column #BestSol provides further insight to this observation. It reveals that the optimal solution of the branch-and-price algorithm coincided with that of K-adaptability methods for a number of instances, which may happen when there exists an optimal solution which can be represented with at most K active columns. This reveals finite adaptability as a good approximation method for finding near-optimal solutions, at least for the problem, and the 20-item instances considered.

In Figure 7, we provide the performance profile for five of the methods considered, plotting the number of 20-item instances for which the method converged versus the time (expressed in logarithmic scale). We remark that the K-Adaptability approaches with K = 4 were excluded as the number of instances solved to convergence was very small. This plot further confirms the numerical promise of the branchand-price algorithm. It also shows that among the other methods considered the most promising is 2-Adaptability.

We therefore further compare these three methods (B&P, 2-AdaptM, 2-AdaptBB) on 30-item instances, with a 2-hour time limit. The results are presented in Table 2 where the headers are kept the same as Table 1. The branch-and-price approach converges for 65 of the 72 instances considered whereas 2-AdaptM Table 2: A summary of 30-item instance results with branch-and-price algorithm and 2-Adaptability, and 2-hour time limit. Solution time ratios are reported as an average over instances solved to convergence before the time limit only. Convergence gaps are reported as an average over instances not solved to convergence before the time limit. Optimality gaps are reported as an average over 72 instances.

We next explore the limits of the column generation-based approach with increasing number of items. In Table 3, we report our results for instances with I ∈ {20, 30, 40, 50, 60, 70, 80}, where starting from 40item instances the time limit was set to 3 hours. We report the number of instances solved to optimality (#Opt), the average optimality gap reported (AvgGap (%)), and the maximum optimality gap reported among the instances considered (MaxGap(%)). The results show that starting from 50-item instances the 3-hour time limit was not sufficient although the average optimality gap was below %5, with the maximum optimality gap being around %11. Moreover, the branch-and-price algorithm found a feasible solution for all the instances considered. We finally remark that, as observed by [START_REF] Pisinger | Where are the hard knapsack problems?[END_REF], introducing correlation between the parameters of the problem renders the solution more difficult. Indeed, starting from 60-item instances no correlated instances were solved to optimality within the time limit. 3: Summary of results for the branch-and-price algorithm: number of instances solved to optimality within the time limit (#Opt), average (AvgGap) and maximum (MaxGap) optimality gaps for unsolved instances.

We conclude this section with an analysis of the value gained by considering an exact solution method rather than the K-adaptability approach. In Table 4, we present the percentage difference between the objective values of the best primal solution found by the branch-and-price algorithm versus the K-Adaptability methods at the end of the time limit. This difference is calculated as 2 * z CG -z K z CG +z K , and is reported only for those instances where the optimal branch-and-price solution had at least 2 active columns. Based on these results, the average percentage gap is below %1, whereas the maximum gap is around %2 for the 2-Adaptability method. One can expect the gaps to be smaller for 3-and 4-adaptable solutions when the method is given enough time to converge. Although the gains reported in Table 4 are rather small, we would expect this number to increase as the number of items increases. Indeed, an indicator of the difference between K-adaptability and an exact approach is the number of active columns (i.e., second-stage solutions that are active for the optimal solution of the adversarial problem). In our experiments, for 20-item instances, most exact solutions used less than 9 active columns. On the other hand, for larger instances, the best primal solution of the branch-and-price algorithm mostly used between 10 and 40 active columns.

Average

Capital budgeting problem

Consider an investment planning problem where a company can allocate an investment budget of B to a subset of projects i ∈ N = {1, . . . , N } with possible extensions to the budget with loans. Each project i ∈ N has cost c i and uncertain profit pi which is modeled as a function of uncertain vector ξ ∈ Ξ of risk factors. The company can invest in a project before or after observing the risk factors ξ ∈ Ξ. We assume that it is also possible to obtain loans before or after the realization of uncertainty, however the interest rate will be higher in the latter case. Here, we suppose that there is one loan option each before and after the realization of uncertainty, for an amount of C 1 and C 2 , respectively. To model the uncertainty associated with this problem, we assume M risk factors that reside in the hyper-rectangle Ξ = [-1, 1] M with M << N . We model the project profits as affine functions of these factors, pi (ξ) = (1 + Q i ξ/2)p i .

Here pi is the nominal cost of project i and Q i represents the i th row of the factor loading matrix Q ∈ R N ×M as a column vector. Early investments enjoy a first-mover advantage whereas a postponed investment in project i generates only a fraction f ∈ [0, 1) of the profits pi . An initial formulation of the problem is given as max

(x,x 0 )∈X -λx 0 + i∈N pi (x i + f y i ) + min ξ∈Ξ max (y,y 0 )∈Y(x) i∈N   M j=1 Q i,j ξ j 2   pi (x i + f y i ) -λµy 0 (44) with µ > 1, where X = (x, x 0 ) ∈ {0, 1} N +1 | c x ≤ B + C 1 x 0 and Y(x) = (y, y 0 ) ∈ {0, 1} N +1 c y -C 2 y 0 ≤ B + C 1 x 0 -c x y i ≤ 1 -x i ∀i ∈ N .
It is easy to verify in this case that conv(Y(x)) = Ȳ(x) for x ∈ X . We alternatively describe how columns can be generated in an extended space to create a relaxation Ȳ(x) that is exact. To this end, we begin with reformulating the recourse problem above. We write

Y (x) = (y, y 0 ) ∈ {0, 1} N +1 c y ≤ B + C 1 x 0 + C 2 y 0 y i ≥ x i ∀i ∈ N .
In the set Y (x), variable y i takes value 1 if the corresponding first-stage variable x i is equal to 1, therefore implicitly counting for the budget already allocated to first-stage investments. With this redefinition of the set Y(x), we also change the objective function to replace variable y i with the difference y i -x i to differentiate between investment decisions in the first and second stage. The problem then becomes max

(x,x 0 )∈X -λx 0 + i∈N pi ((1 -f )x i + f y i ) + min ξ∈Ξ max (y,y 0 )∈Y (x) i∈N   M j=1 Q i,j ξ j 2   pi ((1 -f )x i + f y i ) -λµy 0 .
We next proceed to extending the recourse feasible region so as to include a copy of the variable x 0 reposing on the results of Section 2.3. To this end we may write

Y (x) =    (y, y 0 , z 0 ) ∈ {0, 1} N +2 c y ≤ B + C 1 z 0 + C 2 y 0 y i ≥ x i ∀i ∈ N z 0 = x 0    ,
therefore defining the budget constraint c y ≤ B + C 1 z 0 + C 2 y 0 purely in terms of recourse variables. Let the extreme point solutions of the set Y = (y, y 0 , z 0 ) ∈ {0, 1} N +2 c y ≤ B + C 1 z 0 + C 2 y 0 be denoted by ( ȳ, ȳ0 , z0 ) l for l ∈ L = {1, . . . , L}. When applying the branch-and-price algorithm to this modified problem, the budget constraint c y ≤ B + C 1 x 0 + C 2 y 0 is removed from the master problem while the constraint x 0 = l∈L α l z l 0 is added. Under this reformulation the linking constraints are x 0 = l∈L α l z l 0 and l∈L α l y l i ≥ x i for i ∈ N , and they follow the assumptions of Proposition 2.4. We may therefore obtain an optimal solution of the capital budgeting problem by directly solving a deterministic equivalent model based on the set Ȳ (x) with the branch-and-price algorithm without the need to add any cuts.

We additionally test a K-Adaptability approach to this problem, the associated model can be found in Section 6.2 of the Appendix.

Instance generation

For our numerical tests, we generate instances inspired by those presented in [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF]. For given number of items N , and parameters R = 100 and H = 100, h ∈ {20, 40, 60, 80}, we generate the costs c i for i ∈ N uniformly from the interval [1, R], and we set the nominal profits p = c/5. The components in each row of Q are generated uniformly from the unit simplex in R M , which implies that the profits of each project can deviate up to %50 from their nominal values. We set the investment budget to B = h H+1 i∈I c i and we assume that postponed investments only generate %80 of the profits, that is f = 0.8. The loans C 1 and C 2 are set to %20 of the initial budget B, and the cost parameters are chosen as λ = 0.12 5 and µ = 1.2.

Results

In this section, we present our results on instances generated as described above. We solve instances with N ∈ {10, 20, 30, 40, 50, 100} and generate 60 instances for each value of N , corresponding to 5 replications for each combination of the parameters h ∈ {20, 40, 60, 80} and M ∈ {4, 6, 8}. All instances are solved with a 1-hour time limit. We first present in Table 5 the results comparing the number of instances for which each method has converged. Similar to our results for the robust knapsack instances, our results reveal the column generationbased approach to be very effective for this problem. The exact solution method scales up very well and is able to solve more than %95 of the instances considered. It is also 3 to 4 orders of magnitude faster than the K-adaptability methods for larger instances. This can be seen from the performance profile presented in Figure 8 where the number of instances for which each method has converged is plotted over time presented in logarithmic scale. Additionally, the branch-and-price algorithm found a feasible solution for all the instances considered. Finally, similar to what was done for the knapsack instances, we investigate the number of active columns in the best primal solution reported by the branch-and-price algorithm. In all the instances we considered the number of active columns required was smaller than 10 (although for most large instances at least 5 columns were required). Additionally, for instances with smaller number of items, the percentage of instances that required 3 columns or less was high. Accordingly, one would expect the K-adaptability methods to provide very good approximations for the instances considered. Indeed, our results confirmed that the 2-Adaptability gaps were always below %1 on average (except for N = 10) although higher maximum gaps were present.

N = 10 N = 20 N = 30 N = 40 N = 50 N =

Conclusion

In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty. We propose for these problems a deterministic equivalent formulation through the convexification of the recourse feasible region. We then explore this formulation through the lens of a relaxation that makes it possible to exploit the problem structure and leads to a solution methodology by the branch-andprice algorithm. We provide sufficient conditions for this relaxation to be exact, and propose alternative modeling approaches when this is not the case. The formulations we propose lead also to complexity results on the problem class we study. More specifically, we show that the two-stage robust binary optimization problems with objective uncertainty are NP-complete. Finally, we present two applications where the methodology we propose can be utilized. We provide numerical results on these problems, comparing our methodology to the approximate solution methods known as K-adaptability. Our results show that the methodology we propose is able to find better solutions in solution times that are up to 4 orders of magnitudes smaller than other methods. We also show that our method is able to scale to instance sizes where the approximate solution methods are not able to converge within reasonable solution times.

Our results additionally evoke many research questions to be considered, first-and-foremost being the adaptation of such methods to two-stage robust binary optimization problems with right-hand-side uncertainty. Secondly, our numerical results reveal an interesting observation on finite adaptability methods, that is these methods seem to find near optimal solutions for the problems and instances considered. It is then natural to ask whether this is often the case. Finally, we believe that there is still a considerable amount of research work to be done in the finite adaptability literature. Although these methods seem to provide good solutions, their poor convergence behavior is a deterring factor in their utilization. Different formulations or solution strategies based on decomposition for these approaches should be considered to see whether this behavior can be improved. where z k i and w k i are variables introduced for the linearization of bilinear terms µ k y k i and µ k r k i resulting from the dualization of the inner minimization problem over K possible recourse solutions.

Robust capital budgeting K-adaptability model

We write the mixed integer programming reformulation for the K-Adaptability version of the robust capital budgeting problem of Section 4.2 following [START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF]: where z k i are variables introduced for the linearization of bilinear terms ρ k y k i resulting from the dualization of the inner minimization problem over K possible recourse solutions.

max -λx 0 + i∈N pi (x i + f K k=1 z k i ) -λµ K k=1 z k 0 - M j=1 (u j + v j ) s.t. u j -v j = i∈N Q i,j pi 2 (x i + f K k=1 z k i ) ∀j =

Branch-and-price and branch-and-price-and-cut algorithms

Algorithm 1: Branch-and-price-and-cut algorithm for solving problem ( 22)-( 27). In the special case where Assumption 2.1 as well as Proposition 2.4 hold, the test in line 12 is always true and lines 11-16 can be replaced by line 13 only.

1 Choose L R and (ȳ j ) j∈L R such that ( 15)-( 20 Algorithm 1 summarizes the branch-and-price-and-cut procedure proposed to solve problem (1) through its reformulation ( 23)- [START_REF] Pessoa | Automation and combination of linear-programming based stabilization techniques in column generation[END_REF]. Line 1 initializes the set of columns, L R , so that the restricted master problem is feasible. To do so, one can use any feasible solution of (1). In the relatively rare applications where no trivial feasible solutions exist, one can solve the deterministic counterpart of the problem obtained by fixing an arbitrary scenario. Alternatively, the phase 1 simplex algorithm is used in that purpose for column generation approaches in more general contexts. The best primal bound found, PrimalBound, the

Example 1 . 1 .

 11 Consider the static robust optimization problem max x∈{0,1},y∈{0,1} 3 -x + min ξ∈[0,1]

3 ( 3

 33 -2.5ξ)y 1 + (-1 + 4ξ)y 2 + (4 -6ξ)y 3 s.t. y 1 + y 2 + y 3 ≤ x

Figure 1 :

 1 Figure 1: Graphical representation of Example 1.1. The horizontal axis represents the adversarial decision, while the adversarial objective function is over the vertical axis. The colored affine functions each represent a second-stage decision that restrains this value. The bold black line shows the value of the recourse function with respect to the decision of the adversary.

Figure 2 :

 2 Figure 2: The feasible region of problem (1) after Dantzig-Wolfe reformulation. Here, Y(x) = {y ∈ {0, 1} 3 | y 2 ≤ x, -y 1 + 2y 2 + y 3 ≥ 3x -2}, with x ∈ {0, 1}.

Figure 3 :Proposition 2 . 2 .

 322 Figure 3: Sets conv(Y(x)) and Ȳ(x) illustrated on an example. Here, Y(x) = {y ∈ {0, 1} 2 | y 1 + y 2 ≤ 1.5 -x}, Ȳ(x) = {y ∈ [0, 1] 2 | y 1 + y 2 ≤ 1.5 -x} and x = 0.

Example 2 . 1 .

 21 Consider the second-stage feasibility set Y(x) = {y ∈ {0, 1} 2 | y 1 + y 2 ≤ 1.5 + 0.5x} with x ∈ {0, 1}, and its variant obtained by replacing the binary restrictions on y by y ∈ [0, 1] × {0, 1}.

Figure 4 :

 4 Figure 4: Illustration of Example 2.1 and the implications of Assumption 2.1. In case (a), Y = {0, 1} 2 and conv(Y(0)) = conv{( 0 0 ) , ( 0 1 ) , ( 1 0 )}, whose extreme points are a subset of the extreme points of conv(Y). In case (b), Y = [0, 1] × {0, 1} and conv(Y(0)) = conv{( 0 0 ) , ( 0 1 ) , ( 1 0 ) , ( 0.5 1 )}. The point ( 0.5 1 ) is not an extreme point of conv(Y).

Proposition 2 . 4 .

 24 If H = I, T = -I and d = 0, then Ȳ(x) = conv(Y(x)) for x ∈ X .

Example 2 . 3 .

 23 Consider the second-stage feasibility set

Example 2 . 4 .

 24 Consider the second-stage feasibility set Y(x) = y ∈ [0, 1] × {0, 1} y 1 + y 2 ≤ 1.5 + 0.5x with X = {0, 1}. Here the linking constraints do not follow Assumption 2.1. It turns out that Ȳ(x) = conv(Y(x)) for x ∈ X . This is illustrated in Figure 5(a) for x * = 0, where conv(Y(0)) = {y ∈ [0, 1] 2 | y 1 + 0.5y 2 ≤ 1} and Ȳ(0) = {y ∈ [0, 1] 2 | y 1 + y 2 ≤ 1.5}.

Figure 5 :

 5 Figure 5: Illustration of Example 2.4. Given the same first-stage solution x * = 0, sets Ȳ(x * ) and conv(Y(x * )) are depicted for two different formulations of the second stage. In part (a), the formulation Y(x) does not follow Assumption 2.1, whereas the reformulation Y (x) in part (b) does.

  (b). It follows that, Ȳ (x) = {(y, z) ∈ conv(Y) | z = x} = {(y, z) ∈ [0, 1] 3 | y 1 + 0.5y 2 ≤ 1 + 0.5z, z = x}.As a result, Ȳ (x * ) is the face highlighted in red in Figure5(b) which is also equal to conv(Y (x * )). Indeed, it follows that Ȳ (x) = conv(Y (x)) for x ∈ X by Proposition 2.4 as the new linking constraint z = x follows its assumptions.

Figure 6 :

 6 Figure 6: Illustration of Example 2.5. Given the same first-stage solution x * = (0, 0, 0), sets Ȳ(x * ) and conv(Y(x * )) are depicted for two different formulations of the second stage. In part (a), the formulation Y(x) does not follow Proposition 2.4, whereas the reformulation Y (x) in part (b) does.

  and Ξ = {ξ ∈ R S : Aξ ≤ b} are bounded polyhedral sets. Let Ȳ(x) = conv(Y) ∩ {y : Hy ≤ d -T x} . Question: Does min x∈X ,y∈ Ȳ(x) c T x + max ξ∈Ξ (f + Qξ) T y ≤ η? Proposition 3.1. Problem R2SRMILP is NP-complete.

Corollary 3 . 1 .

 31 If H = I, T = -I and d = 0, or if H = I, T = I and d = 1, then solving problem (1) is NP-complete.

Figure 7 :

 7 Figure 7: Performance profile comparing five methods for 20-item instances of the Robust Knapsack problem. Results for 4-Adaptability model are not shown since this method does not converge for any of the 20-item instances within the one-hour time limit.

I = 20 I

 20 = 30 I = 40 I = 50 I = 60 I = 70 I = 80 #Opt

Figure 8 :

 8 Figure 8: Performance profile comparing all three methods for all instances for the Robust Capital Budgeting problem.

6 Appendix 6 . 1 c i y k i + t i r k i ≤ C ∀k = 1 ,

 6611 Robust knapsack problem K-Adaptability modelWe write the mixed integer programming reformulation for the K-Adaptability version of the robust knapsack problem of Section 4.1 following[START_REF] Grani | K-adaptability in two-stage robust binary programming[END_REF]:min i∈I (f i -pi )x i -. . . , K r k i ≤ y k i ∀i ∈ I, ∀k = 1, . . . , K y k i ≤ x i ∀i ∈ I, ∀k = 1, . . . , K , ∀k = 1, . . . , K z k i ≥ µ k + y k i -1 w k i ≥ µ k + r k i -1 ∀i ∈ I, ∀k = 1, . . . , K x ∈ {0, 1} I , y ∈ {0, 1} K×I , r ∈ {0, 1} K×I z ∈ [0, 1] K×I , w ∈ [0, 1] K×I , µ ∈ [0, 1] K u ∈ R + , v ∈ R I +

1 ,

 1 . . . , M i∈N c i x i ≤ B + C 1 x 0 i∈N c i (x i + y k i ) ≤ B + C 1 x 0 + C 2 y k 0 ∀k = 1, . . . , K x i + y k i ≤ 1 ∀i ∈ N , ∀k = 1, . . . , K K k=1 ρ k = 1 z k i ≤ ρ k ∀i ∈ N ∪ {0}, ∀k = 1, . . . , K z k i ≤ y k i ∀i ∈ N ∪ {0}, ∀k = 1, . . . , K z k i ≥ ρ k + y k i -1 ∀i ∈ N ∪ {0}, ∀k = 1, . . . , K x ∈ {0, 1} N , x 0 ∈ {0, 1}, y ∈ {0, 1} K×N , y 0 ∈ {0, 1} K ρ ∈ [0, 1] K , z ∈ [0, 1] K×N , u ∈ R M + , v ∈ R M +

6 DualBound 7 if DualBound ≥ P rimalBound then 8 Current node is pruned by bound 9 else 10 if x * 1 ∈ {0, 1} N 1 then 11 I 13 Update 15 Add 16 Q ← Q ∪ B 17 else 18 Choose

 6789101111315161718 ) is feasible 2 P rimalBound ← ∞, S * ← ∅ , N R ← ∅, Q ← {∅} 3 while Q = ∅ do 4 Pop a node/set of branching constraints B from Q 5 (x * , u * , α * ) ← optimizeRelaxation(B, L R , N R ) ← c x * + f j∈L α * j ȳj + u * T b ← {i ∈ {1, . . . , N 1 } : x * i = 1} 12 if j∈L\L(I) α * j ≤ |I| -i∈I x * i + i∈N \Ix * i then P rimalBound and S * with DualBound and (x * , u * , α * )14 else the no good cut N R ← N R ∪ {I} i ∈ {1, . . . , N 1 } such that x * i ∈]0, 1[ 19 Add two nodes B 0 = B ∪ {x i = 0} and B 1 = B ∪ {x i = 1} to Q 20 return S *, an optimal solution of (R)

Table 1 :

 1 A summary of 20-item instance results with 7 different solution methods and 1 hour time limit.

		Conv Time* ConvGap(%) OptGap(%) #BestSol #NotBestSol
	B&P	72	1	0	0	72	0
	2-AdaptM	41	468.26	9.72	0.61	16	56
	3-AdaptM	8	5019.24	29.52	0.53	17	55
	4-AdaptM	0	-	40.32	0.66	16	56
	2-AdaptBB	44	613.21	2.87	0.61	14	58
	3-AdaptBB	12	3951.08	3.87	0.32	16	56
	4-AdaptBB	2	3145.44	4.59	0.24	19	53

Table 4 :

 4 Percentage profit gain by an exact approach when the number of active columns is at least 2.

				Max
		I = 20 I = 30 I = 20 I = 30
	2-AdaptM	0.78	0.75	1.98	2.12
	3-AdaptM	0.67	-	4.19	-
	4-AdaptM	0.79	-	4.81	-
	2-AdaptBB	0.78	0.73	1.98	2.35
	3-AdaptBB	0.41	0.54	1.39	2.29
	4-AdaptBB	0.31	0.53	1.40	2.35

Table 5 :

 5 Number of instances solved to convergence by each method.

	100

https://realopt.bordeaux.inria.fr/?page_id=2 (accessed June

2019)2 https://github.com/AnirudhSubramanyam/KAdaptabilitySolver/tree/v1.0 (accessed June 2020) 3 https://slurm.schedmd.com/ (accessed June 2019)

Acknowledgement

Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/).

best feasible solution found, S * , and the subset of no-good cuts [START_REF] Hooker | Logic-based methods for optimization[END_REF], N R , are initialized in Line 2. Each node is encoded as the set of branching constraints, B, defining the set of solutions of that node. The list of open nodes, Q, is thus initialized in Line 2 with the root node, that has no branching constraints. processes the open nodes. The solution of the relaxation at the current node is computed in Line 5. If the solution satisfies the integrality requirements (Line 10), we check whether it satisfies constraints [START_REF] Hooker | Logic-based methods for optimization[END_REF] (Line 11 -12). Note that this is always the case when Assumption 2.1 and the conditions of Proposition 2.4 hold, so that Lines 11-16 can be replaced by line 13 only, where PrimalBound and S * are updated. If the current second-stage solution y * is not compatible with the current first-stage solution x * , i.e., y * = j∈L α * j ȳj / ∈ conv Y(x * ), Line 15 adds the constraint excluding this solution. In this case, the node is put back in the list of open nodes in Line 16. When x * 1 is not integer, branching is performed in Lines 18 and 19.

Algorithm 2: optimizeRelaxation(B, L R , N R ): column generation algorithm for computing the dual bound at each node of the search tree when solving ( 22)-( 27). In the special case where Assumption 2.1 as well as Proposition 2.4 hold, the algorithm takes a simpler form. Input: B: set of branching constraints, L R : set of indices of columns, N R : set of no-good cuts 1 repeat 2 Solve (M P (L R )) with additional branching constraints B and no-good cuts N R 3 Let (x * , u * , α * ) be the optimal solution and π * , µ * , λ * and η * be the optimal dual variables associated with the constraints ( 17), ( 18), ( 19) and ( 28)

Solve (P ricing (π * , µ * , λ * , η * ))

5

Let (y * , z * ) be the optimal solution

Algorithm 2 depicts the column generation procedure used to compute the relaxation at each node of the search tree in Line 5 of Algorithm 1. The loop 1-8 adds new columns to the restricted master M P (L R ) until no negative reduced cost column is found. Model M P (L R ) is solved in Line 2, providing optimal dual variables that are used as input to the pricing problem in Line 4. Lines 6-7 add a new column to M P (L R ) if the pricing problem returns a column with a negative reduced cost. When Assumption 2.1 as well as Proposition 2.4 hold there is no need for Constraints [START_REF] Pisinger | Where are the hard knapsack problems?[END_REF], so that the pricing problem in Line 4 can be replaced with (P ricing(π * , µ * , λ * )). The left-hand-side of the tests in Lines 6 and 8 takes the simpler form -λ * + f -H π * + Q µ * y * .