Diego Cattaruzza

Martine Labbé

Matteo Petris

Marius Roland

Martin Schmidt

Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems

Keywords: Mathematics Subject Classification. 90B25, 90C11, 90C90, 90C15 . Quantile Minimization, Value-at-Risk (VaR), Mixed-Integer Optimization, Valid Inequalities, Adaptive Clustering

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Many real-world planning and investment problems face a significant amount of uncertainty since they inevitably need to incorporate aspects that lie in the future and are thus unknown at the time of decision making. Consequently, usual objective functions in this context combine the minimization of expected costs (or the maximization of expected profits) with some kind of risk minimization. In this paper, we consider general planning and investment problems in which we minimize a convex combination of expected costs and the risk's quantile. In other words, the objective function is a combination of the expected value and the Value at Risk (VaR) of some function that is linear in the problem's variables. It is well known that VaR is nothing but the τ -quantile. It is a measure of risk used in various domains. In portfolio optimization, [START_REF] Gaivoronski | Finding optimal portfolios with constraints on value at risk[END_REF][START_REF] Gaivoronski | Value-at-Risk in Portfolio Optimization: Properties and Computational Approach[END_REF] consider the problem of maximizing the VaR subject to a lower bound on the expected return while [START_REF] Alexander | A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model[END_REF][START_REF] Alexander | Economic implications of using a mean-VaR model for portfolio selection: A comparison with mean-variance analysis[END_REF][START_REF] Benati | A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF][START_REF] Lin | Comments on "A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF] maximize the expected return given a lower bound on the VaR.

Limiting the VaR of a random variable is a particular type of chance constraint since it is equivalent to setting up a lower bound on the probability that the random variable takes a value larger than the said limit. Chance-constrained formulations have been proposed for various applications such as the design of reliable networks [START_REF] Song | Branch-and-cut approaches for chance-constrained formulations of reliable network design problems[END_REF], the packing of objects with random weights [START_REF] Song | Chance-constrained binary packing problems[END_REF], or the allocation of scarce vaccines to prevent the occurrence of disease epidemics [START_REF] Tanner | IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation[END_REF]. Moreover, the VaR is also used in real-world regulatory frameworks such as Basel or Solvency.

Besides considering the quantile minimization, which already poses a computational challenge on its own, we study both continuous and mixed-integer linear settings, which are required by many real-world problems to properly model planning or investment decisions. Thus, in total, we consider the challenging class of mixed-integer linear quantile minimization problems. To this end, stochasticity is modeled via finite scenario sets, which leads to large-scale mixed-integer linear problems that can hardly be solved with state-of-the-art solvers.

Throughout the paper we use two examples for the general class of problems under consideration: A maintenance planning problem in electricity networks as it was posed in the EURO/ROADEF challenge 2020 and a variant of the classic portfolio optimization problem. The grid operation based outage maintenance planning problem (MPP) consists in determining the start time of maintenance interventions in a high-voltage transmission network over a given time horizon. Each of the interventions lasts a certain number of time units that depends on the start time of the intervention. All interventions must be planned and finished before the end of the time horizon. Further, some interventions cannot take place at the same time. Finally, each intervention consumes resources and the total amount of resources used at each time step is bounded from below and above. The objective is to minimize the risk of the maintenance plan. More precisely, a set of scenarios is given and for each such scenario, we know, at each time period, the risk value of each intervention. The goal is to minimize a combination of the expectation and the quantile of the risk.

The second problem is a variant of the well-known portfolio optimization problem. The goal in portfolio optimization is twofold: maximize the return and minimize the risk for which different measures have been proposed; see, e.g., [START_REF] Benati | A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF][START_REF] Gaivoronski | Value-at-Risk in Portfolio Optimization: Properties and Computational Approach[END_REF][START_REF] Lin | Comments on "A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF][START_REF] Mansini | LP solvable models for portfolio optimization: A classification and computational comparison[END_REF]. Among them, the VaR or τ -quantile has attracted particular attention, namely because it is used to measure market risk by regulators; see, e.g., [START_REF] Artzner | Coherent measures of risk[END_REF] and the references therein.

As we already mentioned above, the studied models lead to large-scale mixedinteger linear problems (MILPs). For these problems, we develop tailored solution techniques. In Section 2, we introduce the general problem class and the two specific examples. In Section 3, we propose problem-tailored valid inequalities. They are derived from duality theory applied to a properly chosen linear optimization problem that models the quantile. In Section 4, we present an overlapping alternating direction method that serves as a primal heuristic for quickly computing feasible points of good quality. In Section 5, we then present an adaptive scenario clustering method for which we prove that it computes an approximate global optimal solution after finitely many iterations. We illustrate the computational impact of all presented techniques in our numerical study in Section 6 before we close this paper with some concluding remarks and a brief discussion of potential future research in Section 7.

Problem Statement

In this section, we first state the general problem class that we consider in the following. Afterward, we present two specific examples for the general modeling framework to underline the importance of the studied class of problems.

We consider a discrete set of indices t ∈ T = {1, . . . , T }. With this at hand, the general problem is given by min

x α t∈T E[c t x] + (1 -α) t∈T f Q[c t x] (1a) s.t. x ∈ X ⊆ R N . ( 1b
)
The feasible set X is a non-empty and closed set that may also include integrality restrictions for all or some of the variables. For each index t, we are given a finite set S t of scenarios and for each scenario s ∈ S t , c s t is the respective cost vector and p s t ∈ [0, 1] is the associated probability with s∈St p s t = 1. The expected value is then defined as

E[c t x] = s∈St p s t (c s t ) x
and the τ -quantile is given by

Q[c t x] = min    q ∈ R : s∈N (q) p s t ≥ τ    , N (q) = s ∈ S t : (c s t ) x ≤ q .
Further, α ∈ [0, 1] is a scaling factor that either puts more emphasis on the expected value terms E[c t x] or on the τ -quantile terms f (Q[c t x]), where f is an arbitrary function depending on the τ -quantile

Q[•].
Usually, the τ -quantile Q[•] cannot be stated in closed form. However, it can be expressed by the solution of the following quantile optimization problem in an extended variable space:

Q[c t x] = arg min qt,y s t q t (2a) s.t. q t ≥ (c s t ) x + M s t (y s t -1), s ∈ S t , ( 2b
) s∈St y s t p t ≥ τ, ( 2c
)
y s t ∈ {0, 1}, s ∈ S t , (2d)
where M s t are sufficiently large numbers. We will discuss specific choices of these parameters later when we consider concrete examples. Using such a technique leads to the reformulation min

x,z α t∈T E[c t x] + (1 -α) t∈T g(z t ) (3a) s.t. x ∈ X, z t ∈ Z t (x), t ∈ T , ( 3b
)
where the (possibly mixed-integer) constraint sets Z t (x), which are required to model the quantile, depend on the original variables x. Moreover, we have z = (z t ) t∈T and g is an arbitrary function depending on the newly introduced variable vector z.

To highlight the generality of this class of optimization models, we now consider two examples in the following subsections.

2.1. The Maintenance Planning Problem. Let I denote the set of interventions to be scheduled, let T = {1, . . . , T } be the set of time indices representing the time horizon, i.e., the set of time steps at which interventions can take place, and let R be the set of resources used for the interventions. Further, for each time t ∈ T , S t represents the set of scenarios at this time, which all have the same probability, i.e., p s t = p t = 1/|S t | holds for all t ∈ T . The duration of intervention i ∈ I, if it starts at time t ∈ T , is given by ∆ i t . The amount of resource r used at time t by intervention i starting at time t is given by r i t ,t . The total amount of resource r used by all interventions in process at time t must be at least l r t and cannot be larger than u r t . Moreover, σ i,s t ,t denotes the risk in scenario s at time t of intervention i if it starts at time t . We are also given a set D of triplets (i, j, t) such that intervention i and j cannot be both in process at time t.

Intervention preemption is not allowed and each intervention must be terminated at time T . We thus denote by T (i) = {t ∈ T : t + ∆ i t ≤ T } the set of feasible starting times of intervention i. Further, we denote by T (i, t) = {t ∈ T : t ≤ t, t + ∆ i t ≥ t} the set of starting times of intervention i for which the intervention is in process at time t.

To model the maintenance planning problem (MPP), we use a set of binary variables x: for i ∈ I and t ∈ T (i), we have x i t = 1 if intervention i starts at time t. Further, for t ∈ T , q t and ε t are continuous variables representing the τ -quantile as well as the maximum of zero and the difference between the τ -quantile and the average of the risk at time t for the different scenarios in S t , respectively. We now present the MILP:

min x,ε,q α 1 T t∈T 1 |S t | s∈St i∈I t ∈T (i,t) σ i,s t ,t x i t + (1 -α) 1 T t∈T ε t (4a) s.t.
t∈T (i)

x i t = 1, i ∈ I, (4b)
l r t ≤ i∈I t ∈T (i,t) r i t ,t x i t ≤ u r t , r ∈ R, t ∈ T , ( 4c
)
t ∈T (i,t)

x i t + t ∈T (j,t) x j t ≤ 1, (i, j, t) ∈ D, ( 4d
)
ε t ≥ q t - 1 |S t | s∈St i∈I t ∈T (i,t) σ i,s t ,t x i t , t ∈ T , ( 4e
)
ε t ≥ 0, t ∈ T , ( 4f
)
x i t ∈ {0, 1}, i ∈ I, t ∈ T , ( 4g
)
q t ∈ Z t (x), t ∈ T , (4h)
with x = (x t ) t∈T and x t = (x i t ) i∈I . Analogous vector notation is used to define ε and q.

This problem is the one of the EURO/ROADEF challenge 2020. The first term of the objective function represents the average risk and the second term represents the average excess, i.e., the average of the maximum of zero and the difference between the risk's τ -quantile and the risk's average. They are weighted with coefficients α and (1 -α), α ∈ [0, 1], respectively. Constraints (4b) specify that each intervention must start in exactly one time period. Constraints (4c) indicate that the amount of each resource must be within its lower and upper bounds at each time period. Constraints (4d) forbid pairs of interventions to be in process at the same time when they are in conflict. Constraints (4e) together with the objective function define the excess, at each time t, as the difference between the τ -quantile and the average of the risks. Note that we used that all scenarios have the same probability in this setting while defining the quantile. Finally, (4f)-(4g) specify the type of the different variables.

The set Z t (x) appearing in Constraints (4h) is the set of optimal solutions of the following problem that states that the quantile denoted by q t must be the smallest value larger than or equal to at least

p t = τ |S t | risk values i∈I t ∈T (i,t) σ i,
f (Q[c t x]) = max    0, Q[c t x] - 1 |S t | s∈St i∈I t ∈T (i,t) σ i,s t ,t x i t    .
Thus, the variables ε t , t ∈ T , and Constraints (4e), (4f) and (4h) are not required anymore.

By putting this all together and by re-scaling the objective function with T , for X defined by (4b)-(4d) and (4g), we obtain

min α t∈T E[c t x] + (1 -α) t∈T f (Q[c t x]) s.t. x = (x t ) t∈T ∈ X,
which is exactly of the general form (1).

Portfolio Optimization.

In the classic portfolio optimization problem [START_REF] Markowitz | Portfolio Selection[END_REF] we are given a budget B that we need to invest in a set of n equities so that the expected return is maximized while the corresponding risk, calculated by the standard deviation, is limited to be at most of a given value.

In recent years the risk measure that has mostly been used in the financial community is the Value-at-risk (VaR) [START_REF] Benati | A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF]: to minimize the portfolio's risk, one wishes that, for a given value of the parameter τ , that the corresponding quantile (or VaR) is large.

According to [START_REF] Alexander | Economic implications of using a mean-VaR model for portfolio selection: A comparison with mean-variance analysis[END_REF], the VaR at the 100τ % confidence level of a risky portfolio is the rate of return v q such that F (-v q ) = 1 -τ and F (•) is the cumulative distribution function of the portfolio's rate of return at the end of the period.

Let r i be the return of equity i after, e.g., one year, which is a random variable. Moreover, let x ∈ R n be the vector describing the investment. This means that we invest x i B in equity i and it holds n i=1

x i = 1, x ≥ 0.
The return of the entire portfolio is then given by r x.

The resulting general model for portfolio optimization reads

max x αE[r x] + (1 -α)Q[r x] (7a) s.t. x ∈ X = x ∈ R n : n i=1 x i = 1, E[r x] ≥ ρ, x ≥ 0 (7b)
with α ∈ [0, 1] and ρ is the minimum expected return of the portfolio. This model is a particular case of Model (1) with T being a singleton and f being the identity. Furthermore, to fit into our general framework it remains to change the sign of all observed returns and minimize the objective function.

For α = 0 this problem amounts to minimize the VaR with a minimum expected return. This is the model proposed in [START_REF] Gaivoronski | Value-at-Risk in Portfolio Optimization: Properties and Computational Approach[END_REF] and we can deduct from [START_REF] Benati | A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem[END_REF] that it is strongly NP-hard. However, (7) also encompasses the possibility of a linear combination of both objectives or to relax the constraint of a minimal expected return by choosing a value for ρ that is sufficiently small.

A common approach to determine an optimal portfolio consists in using historical or simulated data. In this context, return vectors r s with their associated probability p s are given for a set S of scenarios so that

E[r x] = s∈S p s (r s ) x and Q[r x] = max    q : s∈N (q) p s ≥ 1 -τ    , N (q) = s ∈ S : (r s ) x ≥ q
holds. Finally, the portfolio optimization problem (POP) can then be formulated as the MILP max x,q,y α s∈S p s (r s ) x + (1 -α)q (8a)

s.t. x ∈ X, ( 8b
) q ≤ (r s ) x + M s y s , s ∈ S, ( 8c
) s∈S p s y s ≤ τ, ( 8d
)
y s ∈ {0, 1} , s ∈ S, (8e)
where M s is a sufficiently large constant that can be set equal to min

   q : s ∈M(q) p s ≥ τ    -min i r s i with M(q) = s ∈ S : max i r s i ≤ q .
Again, this is a special case of Model (3) in which z = (q, y) as well as g(z) = q holds and Z(x) is defined by Constraints (8c)-(8e).

Valid Inequalities

For the ease of notation, we omit the index t in this section when there is no possible ambiguity. Lower bounds on the variable q representing the τ -quantile can be obtained in two different ways. The first one uses the strong-duality property of linear optimization while the second one is based on a combinatorial argument.

In what follows, we set p( S) = s∈ S p s and c i ( S) = s∈ S c s i for S ⊆ S.

Proposition 1.

The following inequality is valid for the quantile problem (2) for all subsets S ⊆ S with p( S) < τ :

τ -p( S) q ≥ n i=1 b i -c i ( S) x i ( 9
)
with b i = min w s∈S c s i w s : s∈S w s = τ, 0 ≤ w s ≤ p s , s ∈ S .
Furthermore, it can be separated in polynomial time.

Proof. Let us consider d s := (c s ) x and p s , s ∈ S, as the realizations of a discrete random variable and its corresponding probability. It is well known, see, e.g., [START_REF] Mansini | LP solvable models for portfolio optimization: A classification and computational comparison[END_REF], that the τ -quantile q is the optimal solution of the linear optimization problem max

u,q τ q - s∈S p s u s (10a) s.t. q -u s ≤ d s , u s ≥ 0, s ∈ S, (10b)
q ∈ R. ( 10c
)
The dual of this problem reads min w s∈S

d s w s (11a) s.t. s∈S w s = τ, (11b) 0 ≤ w s ≤ p s , s ∈ S. (11c)
Using strong duality of linear optimization, the quantile q must satisfy

τ q ≥ s∈S d s w s + s∈S p s u s .
Since u s ≥ max{q -d s , 0}, the following inequality is valid for all S ⊆ S:

τ q ≥ s∈S d s w s + s∈ S p s (q -d s ). (12)
In our general framework, the realization d s is a linear function n i=1 c s i x i so that the resulting inequality ( 12) is nonlinear. However, the linear inequality ( 9) can be obtained by noticing that

s∈S d s w s = s∈S n i=1 c s i x i w s ≥ n i=1 b i x i , b i = min w s∈S c s i w s : (11b), (11c) (13)
and by rearranging terms.

The separation problem for Inequality ( 9) is easy. Given a solution x, q, it suffices to choose S = {s ∈ S : q > n i=1 c s i xi } and check whether the resulting inequality ( 9) is violated.

Note that these inequalities can be seen as a special case of the valid inequalities discussed in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] for bilevel optimization.

The second approach to derive a lower bound on the τ -quantile uses a covering argument and can be seen as a generalization of the idea proposed by [START_REF] Qiu | Covering linear programming with violations[END_REF] for the case where at most k linear inequalities among n given ones are allowed to be violated. In our context, if for a subset S of scenarios the probability satisfies p( S) < τ , then q ≥ (c s ) x holds for some scenarios s ∈ S \ S. Proposition 2. The following inequality is valid for the quantile problem (2) for all subsets S ⊆ S with p( S) < τ :

τ -p( S) q ≥ n i=1 b i ( S)x i ( 14
)
where

b i ( S) = min w    s∈S\ S c s i w s : s∈S\ S w s = τ -p( S), 0 ≤ w s ≤ p s , s ∈ S \ S   .
Proof. Since p( S) < τ holds, there exists a subset S c ⊂ S \ S such that p(S c ) > τ -p( S) and q ≥ (c s ) x holds for all s ∈ S c . Taking a weighted sum of these inequalities with coefficients v s for s ∈ S c with s∈S c v s = τ -p( S) and 0

≤ v s ≤ p s yields τ -p( S) q ≥ n i=1 s∈S c v s c s i x i . ( 15
)
Inequality ( 14) is obtained by additionally using that s∈S c v s c s i ≥ b i ( S) holds. Let us remark that the definitions of b i and b i ( S) imply that b i = b i (∅). To avoid any ambiguities in the sequel we will rather use the notation b i (∅).

The following example shows that a priori there is no dominance relation between the inequalities in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF].

Example 1. Consider four scenarios s ∈ {1, 2, 3, 4} with equal probability 1/4 and four variables x i with i ∈ {1, 2, 3, 4} and let c s i = 0, if i = s and c s i = 1 otherwise. If τ = 3/4, then the inequalities in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] are the following (after rescaling):

• q ≥ 2/3 4 i=1 x i , for S = ∅ • q ≥ i∈ S x i + 1/2 i / ∈ S x i , if | S| = 1 • q ≥ i∈ S x i , if | S| = 2.

None of them is dominated by a nonegative linear combination of the others.

As shown in the following proposition, the separation of the inequalities in ( 14) is difficult at least for a fixed value of p( S). Proposition 3. For a fixed value of p( S), the separation problem for the inequalities in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] is NP-hard even in the special case where p s = 1/|S| for all s ∈ S, τ = k/|S|, and c s i ∈ {0, 1}. Proof. Under the above conditions, the decision version (D-SEP) of the separation problem of ( 14) for a point (x * , q * ) consists in determining whether there exists a subset S such that | S| = B and

|S| n i=1 b i ( S)x * i > q * (k -B) (16)
holds. This problem clearly belongs to NP. Further, we show that CLIQUE reduces to it; see, e.g., Problem GT19 in [START_REF] Garey | Computers and intractability[END_REF]. To this end, for an instance of CLIQUE given by a graph G = (V, E) and an integer B, we define an instance of (D-SEP) as follows. We set

S = V , I = E, k = B + 1, x * i =
x * for all i, q * = x * (B(B -1)/2 -1), and c s i = 0 if edge i is incident to vertex s and c s i = 1 otherwise. Then, |S|b i ( S) = min c s i : s ∈ S \ S = 1 if both end vertices of i belong to S and 0 otherwise. Hence, (16) reads

x * |S| n i=1 b i ( S) = x * |E( S)| > q * (k -B) = x * (B(B -1)/2 -1)
and is satisfied if and only if S is a clique of size B.

The following proposition shows that the inequalities in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] are stronger than the inequalities in [START_REF] Gaivoronski | Value-at-Risk in Portfolio Optimization: Properties and Computational Approach[END_REF]. Proposition 4. For S ∈ S, Inequality [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] dominates Inequality [START_REF] Gaivoronski | Value-at-Risk in Portfolio Optimization: Properties and Computational Approach[END_REF].

Proof. The left-hand sides of both inequalities are equal. Further, we have

b i (∅) = min w s∈S c s i w s : s∈S w s = τ, 0 ≤ w s ≤ p s , s ∈ S ≤ c i ( S) + b i ( S)
Hence, the ith coefficient of ( 14) is larger than or equal to the corresponding one of (9).

The above results suggest to use the separation procedure for Inequality (9) but to add the corresponding stronger inequality (14).

3.1. Application to the Maintenance Planning Problem. First recall that, in the MPP, we have a set of scenarios S t for each time step t and p s = 1/|S t | holds for all s ∈ S t .

The following proposition shows how to adapt the valid inequalities ( 9) and ( 14) to MPP. Proposition 5. The following two inequalities are valid for the MPP (4) for all subsets S ⊆ S t with | S| < τ |S t | :

τ |S t | -| S| q t ≥ i∈I t ∈T (i,t)   b i t,t (∅) - s∈ S σ i,s t ,t x i t   ( 17
)
and τ |S t | -| S| q t ≥ i∈I t ∈T (i,t) b i t,t ( S)x i t , ( 18
)
where

b i t,t ( S) = min w    s∈S\ S σ i,s t ,t w s : s∈S\ S w s = τ |S| -| S|, 0 ≤ w s ≤ 1, s ∈ S \ S   holds.
In addition, Inequality (17) can be separated in polynomial time but is dominated by Inequality [START_REF] Mansini | LP solvable models for portfolio optimization: A classification and computational comparison[END_REF], whose separation is NP-hard.

Proof. The objective function of Problem (10) can be rewritten as

max u,q τ |S| q - s∈S u s , ( 19
)
which leads to the dual formulation min w s∈S

d s w s (20a) s.t. s∈S w s = τ |S| , (20b) 0 ≤ w s ≤ 1, s ∈ S. (20c)
Note that in the MPP, we need to select τ |S| scenarios with a risk lower than or equal to the quantile, which allows us to use the constant in the right-hand side of (20b) and in the objective function [START_REF] Markowitz | Portfolio Selection[END_REF]. Next, by strong duality, the quantile must then satisfy

τ |S| q ≥ s∈S d s w s + s∈ S(q -d s ). ( 21
)
After re-introducing the t-index and bounding the nonlinear terms as in [START_REF] Glowinski | Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[END_REF], Inequality [START_REF] Qiu | Covering linear programming with violations[END_REF] applied to the MPP reads

τ |S t | q t ≥ i∈I t ∈T (i,t) b i t,t (∅)x i t + s∈ S   q t - i∈I t ∈T (i,t) σ i,s t ,t x i t   , t ∈ T , ( 22
)
with

b i t,t (∅) = min w s∈S σ i,s t ,t w s : (20b), (20c) .
The coefficient b i t,t (∅) is the sum of the τ |S| smallest risk values σ i,s t ,t of intervention i ∈ I at time t ∈ T that has started at t ∈ T (i, t).

By grouping the terms in q in the left-hand side, Inequality ( 22) becomes ( 17) and its separation can be done in polynomial time since it suffices to include in S each scenario s ∈ S t if the value of the second term of the right-hand side of ( 22) is positive for the current solution.

The proofs of the validity of Inequality ( 17), of the NP-hardness of its separation, and the fact that it dominates Inequality [START_REF] Liu | Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning[END_REF] are similar to those of Propositions 2-4 while taking again into account that the scenarios of a set S t have equal probability.

Application to the Portfolio Optimization Problem.

In the case of the portfolio optimization problem, given that -q is the (1 -τ )-quantile of the linear functions -(r s ) x, we can directly apply Propositions 2-4 with the modified data cs = -r s , τ = 1 -τ , and variables q = -q. The following proposition summarizes these results. Proposition 6. The following two inequalities are valid for the portfolio optimization problem [START_REF] Gaivoronski | Finding optimal portfolios with constraints on value at risk[END_REF] for all subsets S ⊆ S with p( S) < 1 -τ :

(1 -τ -p( S))q ≤ i∈I (b i (∅) - s∈ S p s r s i )x i , ( 23
)
and

(1 -τ -p( S))q ≤ i∈I b i ( S)x i , ( 24
)
where

b i ( S) = max w    s∈S\ S r s i w s : s∈S\ S w s = 1 -τ -p( S), 0 ≤ w s ≤ p s , s ∈ S \ S   holds.
In addition, Inequality (23) can be separated in polynomial time but is dominated by Inequality [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF], whose separation is NP-hard.

An Overlapping Alternating Direction Method

In this section, we describe an overlapping alternating direction method to solve Problem (3). Alternating Direction Methods (ADMs) have been initially proposed in [START_REF] Gabay | A dual algorithm for the solution of nonlinear variational problems via finite element approximation[END_REF][START_REF] Glowinski | Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[END_REF] as extensions of Lagrangian methods. They are iterative procedures typically used to tackle problems defined by means of two vectors of decision variables, which are subject to some coupling constraints. Instead of solving the monolithic original problem, at each iteration of an ADM, one sequentially solves two smaller subproblems each of which determines a new value for one of the variable vectors, having fixed the value of the other one. In recent years, ADMs have been exploited to solve large-scale optimization problems in the field of gas transport [START_REF] Geißler | Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods[END_REF][START_REF] Geißler | Solving power-constrained gas transportation problems using an MIP-based alternating direction method[END_REF], machine learning [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF][START_REF] Liu | Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning[END_REF], bilevel problems [START_REF] Kleinert | Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method[END_REF], or supply chain problems [START_REF] Schewe | A decomposition heuristic for mixed-integer supply chain problem[END_REF]. In our work, we devise an overlapping ADM (OADM), which can be seen as a variant of an ADM to solve problems for which the vector of variables is partitioned into three subvectors. As in usual ADMs, two subproblems related to two variable subvectors are identified and solved sequentially. However, the remaining variable subvector is to be determined in both subproblems, since it is part of both. The idea behind OADMs can be traced back to overlapping Schwarz methods (see, e.g., [START_REF] Fischer | An Overlapping Schwarz Method for Spectral Element Solution of the Incompressible Navier-Stokes Equations[END_REF][START_REF] Na | On the Convergence of Overlapping Schwarz Decomposition for Nonlinear Optimal Control[END_REF]) used in the field of partial differential equations to solve boundary value problems defined on a domain that is a union of some intersecting subdomains. Recently, it also has been applied very successfully to graph-structured problems; see, e.g., [START_REF] Shin | Decentralized Schemes With Overlap for Solving Graph-Structured Optimization Problems[END_REF].

In the following, we present an OADM for Problem (3), which is motivated by the special structure of the problem itself and by our formulation for the quantile. We observe that Problem (3) makes use of the pair (x, z) of variable vectors, where z is introduced only to reformulate the term of the objective function (3a) that is related to the quantile. Specifically, z ∈ Z t (x), t ∈ T , encodes the formulation of the quantile. In both of our applications, sets of constraints Z t (x), t ∈ T , are defined over two vectors of variables; see Problem [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] and [START_REF] Gaivoronski | Finding optimal portfolios with constraints on value at risk[END_REF]. Hence, in this section, we generalize the setting of Problem (3) by considering it defined over the 3-tuple (x, z 1 , z 2 ) of variable vectors, where z 1 and z 2 are two subvectors of z, i.e., z = (z 1 , z 2 ). In what follows, we may still write z in lieu of (z 1 , z 2 ) if the explicit decomposition is not required. In our OADM, we identify a subproblem related to x and one related to z 1 . The variable vector z 2 is overlapping, i.e., it is part of the optimization for both subproblems. Finally, we highlight that our OADM enjoys two special features. The value of z depends only on the one of x (see, e.g., Constraints (3b)) and z has no influence on the feasible set of the problem, i.e., at each iteration, solving the two subproblems provides feasible points for Problem [START_REF] Artzner | Coherent measures of risk[END_REF].

We apply the OADM outlined in Algorithm 1 to determine a feasible point of Problem [START_REF] Artzner | Coherent measures of risk[END_REF], which improves on an initial one (x 0 , z 0 1 , z 0 2 ) in terms of the objective function value. The initial point (x 0 , z 0 1 , z 0 2 ) is defined by

x 0 ∈ arg min x α t∈T E[c t x] : x ∈ X , z 0 = (z 0 1 , z 0 2 ) ∈ z = (z t ) t∈T : z t = (z 1,t , z 2,t ) ∈ Z t (x 0
) . Specifically, x 0 is chosen among the solutions of the problem obtained by Problem (3) after removing the constraints and the objective function term involving the variable vector z. Clearly, (x 0 , z 0 ) is a feasible point of Problem [START_REF] Artzner | Coherent measures of risk[END_REF]. Now, we describe the iterative procedure outlined in Algorithm 1. In what follows, we write v(x, z)

:= α t∈T E[c t x] + (1 -α) t∈T g(z t )
to lighten the notation. In Line 1, we set the iteration counter j to zero. In iteration j + 1, the algorithm first solves Problem (3) in the direction of (x, z 2 ) while having fixed the value of z 1 to z j 1 to determine a new value (x j+1 , z j+1

2

) for (x, z 2 ); see Line 3. Then, Problem (3) is solved in the direction of (z 1 , z 2 ) while having fixed the value of x to x j+1 to determine a new value (z j+1 1 , z j+1 2 ) for (z 1 , z 2 ). Finally, the algorithm stops (Line 7) once a given stopping criterion is met such as that a time limit is reached or that the improvement of the value of the feasible points is less than a given threshold.

Algorithm 1: An Overlapping Alternating Direction Method

Input :

An initial feasible point (x 0 , z 0 = (z 0 1 , z 0 2 )) of Problem (3). Output : A feasible point (x j , z j = (z j 1 , z j 2 )) of Problem (3). 1 Set j ← 0. 2 while stopping criterion is not satisfied do 3 Compute (x j+1 , z j+1 2 ) ∈ arg min x,z2 {v(x, z j 1 , z 2,t ) : x ∈ X, (z j 1,t , z 2 ) ∈ Z t (x), t ∈ T }. 4 Compute z j+1 = (z j+1 1 , z j+1 2 ) ∈ arg min z=(z1,z2) {v(x j+1 , z) : z t ∈ Z t (x j+1 ), t ∈ T }.

5

Increment j ← j + 1. 6 end 7 return (x j , z j ) 4.1. Application to the Maintenance Planning Problem. In this section, we discuss how Algorithm 1 is applied to the MPP. Specifically, we apply our OADM to the variant of Problem (4) that makes use of Constraints [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]. This problem is defined on four vectors of variables: x = (x t ) t∈T with x t = (x i t ) i∈I , y = (y t ) t∈T with y t = (y s t ) s∈St , q = (q t ) t∈T , and ε = (ε t ) t∈T . In the OADM for the MPP, variable vectors x and y play the role of x and z 1 and variable vectors q and ε play the role of the overlapping variables z 2 in Algorithm 1. Hence, Problem (4) is solved in the direction of x and y and, in both directions, q and ε are also part of the optimization. Here, we consider the variable vector ε as part of z. This leads to a re-definition of the sets Z t (x), t ∈ T , where Constraints (4e) and (4f) are included.

An initial point (x 0 , y 0 , q 0 , ε 0 ) of Problem ( 4) is retrieved as for the general case. First, we select a planning x 0 for the interventions among the feasible solutions of the problem obtained by Problem (4) without taking into account the quantile related variables, constraints, and the objective function term, i.e.,

x 0 ∈ arg min x    α 1 T t∈T 1 |S t | s∈St i∈I t ∈T (i,t) σ i,s t ,t x i t : (4b), (4c), (4d), (4g)    .
Then, we determine values y 0 , q 0 , and ε 0 for variable vectors y, q, and ε as when solving the problem in the direction of y. We do so as follows.

In iteration j + 1, the subproblem in the x-direction corresponds to finding a maintenance planning for the interventions of I in the time horizon T while having fixed the scenarios used to calculate the quantile at each time instant. Hence, the values x j+1 for x are selected among the feasible points of Problem (4) with the values of variables in vector y fixed to y j . We observe that this subproblem is NP-hard. Indeed, it can be reduced to the resource constrained scheduling problem; see, e.g., [START_REF] Garey | Computers and intractability[END_REF]. Differently, solving the subproblem in the direction of y corresponds to computing the value of the objective function (4a) having fixed a planning for the interventions x j+1 . This can be done in a polynomial time. Specifically, given a time instant t ∈ T , we first need to compute risk values σ s t related to each scenario s ∈ S t as

σ s t = i∈I t ∈T (i,t) σ i,s t ,t (x j+1 ) i t .
Then, we sort the scenarios in S t by non-decreasing values of σ s t . The first p t scenarios appearing in this order are those for which we set (y j+1 ) s t = 1. For the others, we set (y j+1 ) s t = 0. This procedure is repeated for each time period t ∈ T . 4.2. Application to the Portfolio Optimization Problem. The OADM for the portfolio optimization problem is applied to the MILP [START_REF] Gaivoronski | Finding optimal portfolios with constraints on value at risk[END_REF], which makes use of variable vectors x ∈ X, y = (y s ) s∈S , and a variable q. It sequentially solves a subproblem in the x-direction and one in the y-direction. The variable q is part of both optimization tasks. Solving the subproblem in the x-directions corresponds to maximizing the portfolio revenue, having fixed the scenario selection. This problem is modeled as a linear program (see the MILP ( 8)) and can thus be efficiently solved. Solving the subproblem in the y-direction corresponds to computing the value of the objective function (8a) knowing the portfolio composition. This can be done in polynomial time.

The initial point computation and the iterative procedure are analogous to the one discussed for the MPP. Hence, we do not report the details here.

An Adaptive Scenario Clustering Approach

This section presents an adaptive scenario clustering algorithm (ASCA) for solving Problem (1) in the case function f is nondecreasing. Given t ∈ T , let us first denote with ct the average cost at t, i.e., ct = 1

|S t | s∈St c s t ,
which allows to rewrite the objective function (1a) as

min α t∈T ct x + (1 -α) t∈T f Q[c t x] . ( 25
)
Observe that the scenarios only have an impact on the quantile computations, i.e., on the second term in [START_REF] Song | Branch-and-cut approaches for chance-constrained formulations of reliable network design problems[END_REF]. Thus, a large number of scenarios can make the resolution of the problem computationally hard. Therefore, a way to approximate the general problem is to reduce the size of each S t by clustering its scenarios. This allows to heuristically find feasible solutions of good quality quickly.

p γ t = 1. ( 26
)
We now present two strategies to associate a cost vector to each cluster of scenarios. First, the average scenario clustering (ASC) associates with each cluster

ASC MSC v(x * ASC ) ≥ v UB v MSC (x * MSC ) ≤ v LB v MSC (x * MSC ) > v LB v(x * ASC ) < v UB Figure 1.
v MSC (x * MSC ) ≤ v(x * ) ≤ min{v(x * ASC ), v(x * MSC )} holds.
Proof. We get the first inequality by construction of the MSC, hence v MSC (x * MSC ) ≤ v MSC (x * ) ≤ v(x * ). The second inequality is due to x * being optimal for Problem (1). Thus, both ASC and MSC allow to compute a bound on v(x * ) while solving Problem (1) over clustered scenario sets. Corollary 1. Let x * be an optimal solution of Problem (1) and let x * ASC as well as x * MSC denote optimal solutions of Problem (1) solved for the scenarios set C ASC t and C MSC t , respectively. For a vector x ∈ X, let v(x) and v MSC (x) denote the objective value w.r.t. x and (1a) defined over S t and C MSC t , respectively. Then, if

v MSC (x * MSC ) = min{v(x * ASC ), v(x * MSC )} holds, x *
ASC is an optimal solution of Problem (1). Additionally, solving Problem (1) with the MSC can be improved using the valid inequality [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF]

i ( St ) with S = S t \ γ implies b i (S t \ γ) τ -p(S t \ γ) ≥ (c γ t ) i , i ∈ N, ( 27
)
so that ( 14) dominates (2b).

Proposition 8 hence tells us that given the set

B := {γ ∈ C MSC t : p γ t > 1 -τ },
we can replace the quantile constraint (2b) associated to γ ∈ B by the valid inequality [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] applied on the set S t \ γ in the MSC. Furthermore, Constraint (2c) reduces to

γ∈C MSC t y γ t p γ t ≥ τ - γ∈B p γ t .
We denote by MSC + the resulting optimization problem. By construction, we thus have that

v MSC (x * MSC ) ≤ v MSC + (x * MSC + ) ≤ v(x * ) holds.
For what follows, we define v UB and v LB as the current best upper and lower bounds on v(x * ). Additionally, C j t stands for the clustering of S t for t ∈ T in iteration j of the algorithm. We indicate with C ASC,j t and C MSC + ,j t the instance of C j t where the cost vectors are calculated using ASC and MSC + , respectively. Algorithm 2 states the pseudo-code of our adaptive algorithm and Figure 1 shows a state diagram of the inner while loop of the algorithm. The algorithm solves a sequence of problems of Type [START_REF] Alexander | A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model[END_REF]

|C j t | > |C j-1 t |, ( 28
)
for all iterations j. Then, Algorithm 2 terminates after a finite number of cluster refinements with a point

x ∈ X such that v(x) -v(x * ) v(x) ≤ ε. ( 29
)
Proof. Due to Inequality (28), each iteration of Algorithm 2 increases the size of C j t for at least one t ∈ T . Therefore, if the termination criterion (v UB -v LB )/v UB ≤ ε is never satisfied, C j t will increase in size over the iterations until being equal to S t . If C j t equals S t for all t ∈ T , then |γ| = 1 for all γ ∈ C j t . The cost vectors c γ t for each γ ∈ C j t correspond to the cost vector associated with the single scenario in γ for both ASC and MSC clustering strategies. Otherwise, if (v UB -v LB )/v UB ≤ ε is satisfied, we know that x ASC also satisfies Inequality (29) by Proposition 7.

Remark 1. We close this section with the discussion of two features of the ASCA.

• The cluster refinement step in Line 17 of Algorithm 2 is done using kernel density estimation (KDE). KDE allows to estimate the probability density function of a random variable by using a set of samples of this random variable [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF]. The local minima of the estimated probability density function then yield a splitting of the random variable samples. In our case, for a given t ∈ T and γ ∈ C t as well as a point x ∈ X, we compute the KDE of (c s t ) x using all s ∈ γ, which results in a splitting of γ. We use x * ASC or x * MSC depending on whether the previous iteration j -1 of the ASCA used C ASC,j-1

t or C MSC,j-1 t
. Additionally, only a subset of time steps T ⊆ T is selected for re-clustering after each iteration of the ASCA. Given a parameter Θ ∈ (0, 1), we compute this refinement set T to be the minimal subset of T satisfying t∈T

Q[c t x; C j-1 t ] -Q[c t x] > Θ t∈T Q[c t x; C j-1 t ] -Q[c t x] . Here, Q[•] is the original quantile, whereas Q[•; C j-1 t
] denotes the quantile's approximation based on the clustering C j-1 t . Hence, we select the subset of indices t ∈ T that have the biggest difference between their clustered and their real quantile value for a chosen x.

• The solution processes in Lines 5 and 11 of Algorithm 2 can benefit from a series of improvements. First, every valid inequality from MSC + obtained through Proposition 8 is kept in the subsequent MSC + and ASC problems even if the associated cluster is split in the refinement step. Second, the OADM discussed in Section 4 is applied first, as a heuristic, for every MILP.

Here, we use x LB and x UB (see Algorithm 2) as initial iterates for the OADM provided that we are in the corresponding clustered problem. Third, we use the valid inequalities in [START_REF] Kleinert | Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality[END_REF] to speed up the MILP solution process.

Numerical Results

In this section, we present and discuss the results obtained by testing our methods on the maintenance planning and on the portfolio optimization problem.

In what follows, we make use of the following notation. When assessing the performance of our MILP models, we consider the following three configurations. We write MILP meaning that we solve Model (4) when considering the MPP and Model (8) when considering the POP, both without valid inequalities. We write MILP VI and MILP VI * meaning that we solve Model (4) enriched with Inequalities [START_REF] Liu | Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning[END_REF] and Inequalities [START_REF] Mansini | LP solvable models for portfolio optimization: A classification and computational comparison[END_REF], when considering the MPP. In the case of the POP, MILP VI and MILP VI * stand for Model (8) enriched with Inequalities ( 23) and ( 24), respectively. Furthermore, we add the superscript OADM to the notation yet introduced, when the corresponding configuration is warm-started with an initial solution found by OADM as described in Section 4. For example, in the case of the MPP, MILP OADM VI * means that Model (4) enriched with Inequalities ( 18) is warm-started with an initial solution found by the OADM. Let M denote the set of considered methods. For m ∈ M we denote by v m LB and v m UB the best lower and upper bound values found by method m on a given problem instance. For the sake of simplicity, we will additionaly use v LB and v UB when discussing the upper or lower bound without referring to a specific method.

In the following, we make some further comments regarding the tests we will discuss in Sections 6.1 and 6.2. In configurations MILP VI and MILP VI * , we separate valid inequalities only at the root node of the branch-and-bound tree, as preliminary results showed that this is the best strategy. Indeed, separating them at each node of the tree significantly reduces the time left to explore the tree itself, leading to poor primal bounds-in particular in the case of the MPP. Moreover, the valid inequalities considered in MILP VI * dominate the ones considered in MILP VI ; see Proposition 4. In the case of the MPP, this is reflected in the results obtained by performing some preliminary tests. Hence, in Section 6.1 we only discuss the results obtained by MILP VI * . This behavior does not occur when considering the POP. Thus, in Section 6.2, we discuss the results of both configurations. Finally, we remark that the solver does not struggle to provide feasible solutions of good quality on the POP instances when solving MILP, MILP VI or MILP VI * ; see Section 6.2. Consequently, we do not consider the inclusion of OADM and ASCA in the solution procedure for this problem.

All computations have been executed on a remote server with 64 GB RAM and an AMD Opteron 6176 SE processor with 12 cores and 2.30 GHz. The techniques presented in this paper have been coded in C ++ 14 and are compiled using g ++ version 9.3.0. All MILP models are solved using Gurobi 9.1.0. The time limit is set to 90 min for which the time for reading the instance is ignored. 6.1. Numerical Results for the Maintenance Planning Problem. We first present the numerical results of the proposed methods when applied to the EURO/ROADEF 2020 challenge instances. Table 1 shows the main characteristics of the these instances. Their names start with a capital letter that, based on their alphabetical order, correspond to a different phases of the EURO/ROADEF 2020 challenge. Hence, instances with a name starting with a letter appearing later in the alphabet are more likely to be computationally challenging. Note that we omit to list those instances that are trivial due to a very small number of scenarios.

The size of some instances makes the time to complete multiple OADM iterations too large w.r.t. the total computational time allowed. Thus, we set the stopping criterion of the OADM so that only the first iteration is applied. Finally, the ASCA computational parameters are given in Table 2 and have been chosen based on our preliminary numerical tests.

Because of the large amount of EURO/ROADEF instances we use the bar plots in UB if no incumbent is found during the solution process of m . The rescaling of v LB or v UB is constant for a specific instance and therefore allows to easily visualize how they compare for two different methods.

Hence, bars close to zero mean that the corresponding method performs better compared to the other method on the respective bound. However, we would like to draw attention to the fact that the spacing between the sides of the bars is not representative of the relative gap given by (v UB -v LB )/v LB .

Figure 2 shows a comparison between the results obtained by MILP with those obtained by MILP VI * . We observe that MILP VI * systematically outperforms MILP, yielding a great improvement on both v LB and v UB , where the lower bound improves more significantly than the upper bound. However, we remark that MILP VI * fails to provide an incumbent solution for some instances within the time limit for which MILP succeeds in doing so; see, e.g., B03. Most likely, this has two reasons. First, additional time is needed to separate violated inequalities in the first node of the branch and bound tree. Second, the model's relaxations are a bit harder to solve after adding valid inequalities due their increased size.

To counteract this effect, we also tested to apply the OADM described in Section 4 to the MILP model with valid inequalities for the MPP as a primal root node heuristic. Figure 3 shows the comparison of MILP VI * and MILP OADM VI * . In the latter configuration, the point to warm-start is the result of a single iteration of the OADM. The resulting bar plot only displays the instances with a significant difference in v LB or v UB . Note that the one iteration of the OADM allows to obtain an incumbent solutions for all the instances where the resolution of MILP VI * fails to do so. For the remaining instances, we see that activating a single OADM step mostly performs worse in terms of v UB . Also, for instance X05 and C13, the time spent in one OADM iteration is rather long-hence harming the impact of the valid inequalities on v LB .

Figure 4 shows the results obtained by the ASCA presented in Section 5 when compared to the results obtained by MILP. One can observe that ASCA provides better results in terms of both v LB and v UB . However, it fails to get a strictly positive value for v LB for some of the more computationally challenging instances. As it is is the case for MILP VI * , both for v LB and v UB we see that ASCA outperforms MILP. For those instances for which ASCA fails to obtain a strictly positive value for v LB , ASCA keeps improving v UB using the ASC problem during the initial iterations of Table 1. Characteristics of all the EURO/ROADEF 2020 challenge instances. the algorithm. Since v UB keeps decreasing in every iteration, ASCA never enters the MSC + problem before reaching the given time limit. Thus, it never improves on the v LB = 0 lower bound. Similarly, MILP fails to compute incumbent solutions for some of the more computationally challenging instances and, hence, does not decrease the v UB = ∞ bound. On the contrary, ASCA always finds an improved incumbent solution since it is designed to start solving the ASC problem in order to decrease the value of v UB .

ID |I| |R| |T | t∈T |S t | |T | ∞ 1 0 1 ∞ A02 A05 A08
We close the comparison of the methods with Figure 5, which compares ASCA and MILP OADM VI * , i.e., it compares the methods that perform best in terms of v UB and v LB . Considering the values of v LB , we see that MILP OADM VI * always outperforms ASCA except for the instances C14 and X05. The opposite situation occurs when the two configurations are compared w.r.t. the values of v UB . The detailed results obtained on the EURO/ROADEF instances with our methods are reported in Tables 5 and6. 6.2. Numerical Results for the Portfolio Optimization Problem. We build a test set of 24 instances for the portfolio optimization problem following the procedure used in [START_REF] Qiu | Covering linear programming with violations[END_REF] to generate instances for the probabilistically chance-constrained portfolio optimization model. Our instances are characterized by n ∈ {20, 200} equities and |S| = 200 equiprobable scenarios with p s = 1/|S|, s ∈ S. We draw the components of return vectors r s , s ∈ S, using an independent uniform distribution law on the interval [80,150]. This means, we generate equities whose returns range between a 20 % loss and a 50 % profit on the investment. The minimum expected return ρ is set to 110, forcing an average portfolio return of 10 % w.r.t. the invested budget. We consider the VaR confidence level of 7.5 %, 15 %, and 22.5 %, i.e., τ ∈ {0.075, 0.15, 0.225} holds. Finally, the objective function weight α takes values in set {0, 0.25, 0.5, 0.75}: Smaller values of α favor risk minimization over return maximization-larger values of α favor the opposite behavior.

First, we discuss the results obtained by solving MILP, MILP VI , and MILP VI * on the entire set of 24 instances. For MILP VI * , where the separation of the inequalities in ( 24) is NP-hard (see Proposition 6), we separate them by means of the same procedure employed for the inequalities in [START_REF] Shin | Decentralized Schemes With Overlap for Solving Graph-Structured Optimization Problems[END_REF]. By doing so, the time spent to separate and build the two families of valid inequalities differs of a factor of ten. However, in both cases, this time remains negligible w.r.t. the computational time limit since it is always less than 4 s.

Table 3 reports the results obtained by solving the instances with the three configurations. Each row of the table corresponds to an instance for which its parameterization is summarized in columns two to six of the table. Then, for each approach, we include three columns. The first and second columns contain the lower and upper bounds (v LB and v UB ), respectively. The third is a mixed time/gap (t solve /gap) column reporting either the computational time if the model is solved to global optimality within the time limit or the relative optimality gap in percentage (100 (v UB -v LB )/v LB ) otherwise.

In general, all three configurations yield comparable results. The solver provides feasible points of comparable value (v LB ) on all the instances and it manages to prove the optimality of the same four instances (W1, W4, W7, W10) on average in 436, 438, and 604 seconds, respectively. The average optimality gap returned by the solver on the instances for which optimality is not proven within the time limit is 3.4 % for the plain MILP and 2.6 % for both configurations involving valid inequalities.

To assess the impact of the two families of valid inequalities, we focus on those instances that are not solved to optimality. In what follows, the upper bound improvement of a configuration against another one, e.g., MILP against MILP VI , is computed as (v

UB

are the upper bounds returned by the solver for the configurations MILP and MILP VI , respectively. The improvements regarding the optimality gap are computed analogously.

First, we observe that the introduction of either inequalities [START_REF] Shin | Decentralized Schemes With Overlap for Solving Graph-Structured Optimization Problems[END_REF] or (24) yields benefits in terms of both decreasing the upper bound and reducing the optimality gap. Indeed, the upper bound and integrality gap improvements on average are equal to 0.8 % and 18 % when comparing MILP to MILP VI and they are equal to 0.7 % and 16 % when comparing MILP to MILP VI * . The same trend emerges when analyzing the values of the upper bound and the optimality gap after the solution of the root node of the branch-and-bound tree; see Table 4.

As mentioned in the introduction of this section, although inequalities (23) are dominated by inequalities [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF] (see Proposition 6), this relation is not reflected in the computational results. Indeed, when comparing MILP VI to MILP VI * , the upper bound improvement in percent becomes negligible and the optimality gap tends to be smaller for MILP VI -on average of 3 %. Conversely, a slight dominance of configuration MILP VI * over configuration MILP VI arises from the results obtained after the solution of the root node; see Table 4. To explain this behavior, we note that the separation procedure for inequalities ( 24) is heuristic. Finally, as opposed to the MPP, the solver does not fail to provide feasible points of good quality on the instances of the portfolio optimization problem. Indeed, the average optimality gap already after the resolution of root node is rather small. It is equal to 11.5 %, 6.1 %, and 5.6 % for configurations MILP, MILP VI and MILP VI * , respectively.

Conclusion

In this paper we considered several solution techniques for mixed-integer quantile minimization problems. We stated the problem in a very general form and developed techniques to strengthen the dual bound (via tailored valid inequalities), to find good primal solutions quickly (via the overlapping ADM), and to derive provably optimal solutions using a problem-specific approach (via the adaptive clustering method). Our numerical results on the maintenance planning problem of the EURO/ROADEF challenge 2020 and on the quantile-based version of the portfolio optimization problem show that the combination of these techniques significantly outperforms the application of general-purpose MILP solvers.

We briefly touched the field of chance constraints that is highly related to the quantile minimization problems discussed in this paper. Thus, a natural topic of future research will be to investigate on how to transfer our novel techniques to improve solution methods for chance-constrained problems. Email address: roland@uni-trier.de, martin.schmidt@uni-trier.de

  Figures 2-5 to visually compare the different methods. Let M be the subset of methods of M considered in the bar plot. Then, for all m ∈ M the bar plots show the re-scaled value of v m LB (left side) and v m UB (right side) on all instances. The bars' lengths are determined as follows. The left side of the bar plots is equal to min m ∈M {v m LB : v m LB > 0}/v m LB . The numerator min m ∈M {v m LB : v m LB > 0} takes the value of the smallest lower bound obtained by the methods in M while ignoring a lower bound if the method m does not improve on v m LB = 0. We apply a similar rule for the right side of the bar plots using v m UB / max m ∈M {v m UB : v m UB < ∞}. Here, max m ∈M {v m UB : v m UB < ∞} takes the value of the largest upper bound obtained by the two compared methods without considering v m

Figure 2 .

 2 Figure 2. Bar plot for min m ∈M {v m LB : v m LB > 0}/v m LB (left side) and v m UB / max m ∈M {v m UB : v m UB < ∞} (right side), where M is composed of MILP (blue) and MILP VI * (yellow).

Θ OADM gap (Line 3 )Figure 3 .

 33 Figure 3. Bar plot for min m ∈M {v m LB : v m LB > 0}/v m LB (left side) and v m UB / max m ∈M {v m UB : v m UB < ∞} (right side), where M is composed of MILP OADM VI * (blue) and MILP VI * (yellow). Only the instances with a significant difference in the results for v LB and v UB are displayed.

Figure 4 .

 4 Figure 4. Bar plot for min m ∈M {v m LB : v m LB > 0}/v m LB (left side) and v m UB / max m ∈M {v m UB : v m UB < ∞} (right side), where M is composed of MILP (blue) and ASCA (yellow).

Figure 5 .

 5 Figure 5. Bar plot for min m ∈M {v m LB : v m LB > 0}/v m LB (left side) and v m UB / max m ∈M {v m UB : v m UB < ∞} (right side), where M is composed of MILP OADM VI *

(

  D. Cattaruzza, M. Petris) Univ. Lille, CNRS, Centrale Lille, Inria, UMR 9189 -CRIStAL Lille, France (M. Labbé) (A) Université Libre de Bruxelles, Department of Computer Science, Boulevard du Triomphe, CP212, 1050 Brussels, Belgium; (B) Inria Lille -Nord Europe, Parc scientifique de la Haute Borne, 40, av. Halley -Bât A -Park Plaza, 59650 Villeneuve d'Ascq, France Email address: martine.labbe@ulb.be (M. Roland, M. Schmidt) Trier University, Department of Mathematics, Universitätsring 15, 54296 Trier, Germany

  More precisely, let C t be a partition of S t into K t ≤ |S t | nonempty clusters. Each cluster γ ∈ C t has a cost vector c γ t and a probability p γ t . The ASCA consists in solving a sequence of instances of Problem (1)-each defined over a clustered scenario set C t instead of the original set S t . The probability p γ

		t of cluster γ ∈ C t is
	given by
	p γ t =	p s t ,
	s∈γ
	which satisfies
	γ∈Ct

  State diagram of the adaptive scenario clustering algorithm.

	γ ∈ C t a cost vector c γ t defined as follows:
		(c γ t ) i =	1 |γ| s∈γ	(c s t ) i , i ∈ N.
	Let us indicate with C ASC t	the corresponding clustering of scenarios.
	Further, the minimum scenario clustering (MSC) associates with each cluster
	γ ∈ C t a cost vector c γ t defined as
	(c γ t )

i = min {(c s t ) i : s ∈ γ} , i ∈ N. Let us indicate with C MSC t the corresponding clustering of scenarios. Proposition 7. Let x * be an optimal solution of Problem (1) and let x * ASC as well as x * MSC denote optimal solutions of Problem (1) solved on the scenarios set C ASC t and C MSC t , respectively. For a vector x ∈ X, let v(x) and v MSC (x) denote the objective value w.r.t. x and (1a) defined over S t and C MSC t , respectively. Then,

  . Set C 0 t ← {S t } for all t ∈ T , i.e., we start with a single cluster per index t. 2 Set j ← 0, v UB ← +∞, v LB ← -∞, and κ ← true.3 while (v UB -v LB )/v UB ≥ ε do

	Algorithm 2: Adaptive Scenario Clustering Algorithm.
	4	if κ then
	5	Solve Problem (1) on C ASC,j t	, let x * ASC denote the optimal solution.
	6 7	if v(x * ASC ) < v UB then set x UB ← x * ASC and v UB ← v(x * ASC )
	8	else
	9	set κ ← false.
	10	else
	11	Solve Problem (1) on C MSC + ,j t if v MSC + (x * MSC	, let x * MSC + denote the optimal solution.
	Proposition 8. Given C MSC t that p γ t > 1 -τ holds. Then, in Problem (2) defining the quantile of t, it holds that for a specific t ∈ T . Let γ be a cluster in C MSC such t
		y γ t = 1,
	and the resulting inequality (2b) is dominated by the valid inequality (14) for S =
	S t \ γ.

Input : Threshold parameter ε ∈ (0, 1). 1 + ) > v LB then 12 set x LB ← x * MSC + and v LB ← v MSC + (x * MSC + ) 13 else 14 set κ ← true. 15 if v(x * MSC + ) < v UB then 16 set x UB ← x * MSC + and v UB ← v(x * MSC + ). 17 Update j ← j + 1 and refine C j-1 t , yielding C j t . 18 end 19 return x UB Proof. Since p γ t > 1 -τ , (2c) and (2d) imply y γ t = 1. Furthermore, the definition of b

  defined over C ASC ) as shown in Proposition 7. After each resolution, the algorithm refines the previous clustering C j-1 t , yielding C j t for all t ∈ T . The resulting clustering C j t allows to have a better representation of the scenario set S t . This makes the next resolution of Problem (1) defined over C ASC However, the new clustering of scenarios will likely allow to compute a better lower or upper bound on v(x * ). The sequence of resolutions over C ASC MSC + (x * MSC + ) ≤ v LB . Finally, the algorithm terminates once we achieve a relative gap smaller than a prescribed tolerance ε, i.e., v UB -v LB v UB ≤ ε. Let x * be an optimal solution of Problem (1) and let v(x * ) be its value. Moreover, let C j t be the clustering of S t for index t ∈ T in iteration j. Suppose further that there exists an index t ∈ T such that

	t	or C MSC + t	harder
	is ASC ) ≥ v UB . to solve. t then interrupted and switched to the resolution over C MSC + t when v(x * Similarly, the sequence of resolution of Problem (1) over C MSC + is interrupted and t switched to C ASC t when v Theorem 1.

t and C MSC + t to improve the lower or upper bound on v(x *

Table 2 .

 2 OADM parameters.

Table 3 .

 3 Results obtained by solving the instances of the portfolio optimization problem with configurations MILP, MILP VI and MILP VI * within a time limit of 90 minutes.

		Parameters				MILP			MILP VI			MILP VI *
	ID	Assets |S|	α	ρ	τ	v LB	v UB t solve (s)/gap(%)	v LB	v UB t solve (s)/gap(%)	v LB	v UB t solve (s)/gap(%)
	W1	20 200	0 110 0.075	111.05	111.05	934.522s	111.05	111.05	1058.42s	111.05	111.05	885.981s
	W2	20 200	0 110	0.15 112.629 114.825	1.95% 112.629 114.772	1.90% 112.629 114.837	1.96%
	W3	20 200	0 110 0.225 113.844 119.218	4.72% 113.719 118.829	4.49%	113.82 120.508	5.88%
	W4	20 200 0.25 110 0.075 112.558 112.558	370.782s 112.558 112.558	380.56s 112.558 112.558	1226.77s
	W5	20 200 0.25 110	0.15	113.33 115.169	1.62% 113.258 115.409	1.90%	113.33	115.39	1.82%
	W6	20 200 0.25 110 0.225 115.051 119.067	3.49% 115.054 119.716	4.05% 115.007 119.544	3.95%
	W7	20 200	0.5 110 0.075 113.778 113.778	325.911s 113.778 113.778	113.778s 113.778 113.778	206.893s
	W8	20 200	0.5 110	0.15 114.345 115.705	1.19% 114.385 115.734	1.18% 114.375 116.205	1.60%
	W9	20 200	0.5 110 0.225 114.959 117.764	2.44% 114.907 118.117	2.79% 114.876	118.1	2.81%
	W10	20 200 0.75 110 0.075	114.31	114.31	113.189s	114.31	114.31	92.8553s	114.31	114.31	126.28s
	W11	20 200 0.75 110	0.15 114.642 115.362	0.63% 114.678 115.271	0.52% 114.678	115.33	0.57%
	W12	20 200 0.75 110 0.225 115.126 115.813	0.60% 115.126	115.96	0.72% 115.126 115.874	0.65%
	W13	400 200	0 110 0.075 116.551 120.701	3.56% 116.545 119.155	2.24% 116.612 119.165	2.19%
	W14	400 200	0 110	0.15 117.094 125.632	7.29% 117.219 122.351	4.38% 117.226 122.363	4.38%
	W15	400 200	0 110 0.225 117.595 130.208	10.73% 117.811 125.778	6.76% 117.812 125.736	6.73%
	W16	400 200 0.25 110 0.075 116.738	119.85	2.67% 116.762 118.696	1.66% 116.745 118.705	1.68%
	W17	400 200 0.25 110	0.15 117.203	123.38	5.27% 117.233 121.102	3.30% 117.229 121.131	3.33%
	W18	400 200 0.25 110 0.225 117.775 126.679	7.56% 117.829 123.704	4.99% 117.715 123.727	5.11%
	W19	400 200	0.5 110 0.075 116.909	118.83	1.64%	116.9 118.112	1.04% 116.907 118.122	1.04%
	W20	400 200	0.5 110	0.15 117.378 121.241	3.29% 117.332 120.073	2.34%	117.33 120.087	2.35%
	W21	400 200	0.5 110 0.225 117.583 123.293	4.86% 117.684 121.521	3.26% 117.654 121.509	3.28%
	W22	400 200 0.75 110 0.075	117.25 118.136	0.76%	117.24	117.78	0.46%	117.25 117.785	0.46%
	W23	400 200 0.75 110	0.15 117.199 119.012	1.55% 117.209 118.547	1.14% 117.222 118.517	1.10%
	W24	400 200 0.75 110 0.225 117.659 120.392	2.32% 117.677 119.695	1.71% 117.715 119.752	1.73%

Table 4 .

 4 Average upper bound and integrality gap percentage improvements after the resolution of the root node of the branchand-bound tree Comparison avg. v UB impr.(%) avg. gap impr.(%)

	MILP vs. MILP VI	1.73	34.50
	MILP vs. MILP VI *	1.77	39.15
	MILP VI vs. MILP VI *	0.05	4.85

Acknowledgments

Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique -FNRS under Grant(s) no PDR T0098.18. Marius Roland and Martin Schmidt acknowledge the support by the German Bundesministerium für Bildung und Forschung within the project "EiFer". Martin Schmidt thanks the DFG for their support within the projects A05 and B08 in CRC TRR 154.


Intercultural integration in Sino-Brazilian joint ventures

(Last author version before publication; Please see published version at https://www.eelgar.com/shop/gbp/cross-cultural-management-in-practice-9781849804073.html) Guilherme Azevedo 性相近 習相遠 "Men's natures are alike, it is their habits that carry them far apart." (Mencius in "The three character classic")

The integration dinner A friend of mine once told me a story. He had spent two years in Sweden studying mechanical engineering. There was a clear separation between the Swedes and the international students. The two groups lived in different places and, accordingly to him, the Swedes did not hang out or mixed much with the international students. There had been a polite relationship within the classrooms but a very low overall social interaction.

The courses were in English, already a second language for most of the foreign students, and they had not put much effort to learn Swedish. During the holidays the Swedes would go home, and the foreigners would stay at the university or travel in Europe. Most of the foreigners, as told my friend, had never been invited to a Swedish house or spent time with a Swedish family.

The foreign students gradually started stereotyping their local colleagues as being distant, never doing anything on impulse, and caring just about their own business. (I do not know what the Swedes thought of the international students.) After a year and a halfwith graduation approachingthe administrators of the program decided to take action and organized an integration dinner. But things did not go as planned.

Arriving at the large dinning-table, the international students flocked to one part of the table and the Swedes to the other. As the dinner started each side group engaged in a separate conversation. After a while, perhaps being uncomfortable with the lack of integration in their integration dinner and encouraged by the wine, a local student tried to start a conversation with a foreign colleague. He interrupted a nearby Italian with a friendly question: 'So, why did you decide to come to Sweden?' The Italian stopped gesticulating and talking for a second, turned to him, quipped: 'Because of the weather,' turned back to his side of the table, and continued his conversation.

It was too late to start the integration. I asked my friend if his colleague's reaction was not too rude. He reflected for a moment before answering: 'In retrospect, I think it was. But, at the time, I found it just right and very funny. We did not care about integration anymore.'

The end of the story is anticlimactic: the Swedes and foreigners finished their course and continued their lives. Perhaps they missed the opportunity of experiencing a richer intercultural exchange and forming a larger international network, but they got their degrees, and, in the end, nobody got hurt.

Organizations however are unlikely to perform well if composed of groups unable to collaborate productively. In this case, a better cultural integration certainly is needed.

Studying integration in multicultural organizations

Typical examples of multicultural organizations (i.e., whose workforce comes from different cultures) are multinational subsidiaries abroad, international joint ventures, and international mergers and acquisitions. The academic literature is replete with examples of such organizations struggling with cultural integration and conflicts.

Interestingly, these texts (e.g., [START_REF] Byun | Japanese business in the Dutch polder: The experience of cultural differences in asymmetric power relations[END_REF][START_REF] Pardi | Where did if go wrong? Hybridization and crisis of Toyota Motor Manufacturing UK, 1989-2001[END_REF] very often repeat the plot depicted in the integration dinner: different cultural groups are put together; poor preparation, inadequate structure, and contextual factors conspire to make the integration difficult; a series of microdynamics prevents integration and increases the separation; negative stereotypes are developed as indifference mounts to cultural conflict; and, one day, people realize that it seems too late or too costly to pursue the cultural integration that would allow a fruitful collaboration. This is a trap to be avoided.

In this chapter, I tackle the problem of how to integrate different cultures within an organization.

My investigation is based upon the direct observation of managers and workers that are out there, facing the issue of intercultural integration. This approach reflects Schein's (1996, p. 239) This data collection, although too short in traditional ethnographic practice, followed the principles of ethnography applied to organizations (e.g., [START_REF] Schwartzman | Ethnography in Organizations[END_REF][START_REF] Brannen | Ethnographic international management research[END_REF] and took place within the organizations and in external spaces, including employees' clubs, homes, hotel lobbies, restaurants, parks, and even a traditional Chinese bath.

Intercultural integration

Tolstoy opens his Anna Karenina with the line: 'Happy families are all alike; every unhappy family is unhappy in its own way.' Similarly, in organizations, there are many more ways to fail than to succeed.

Particularly, one path to failure for multicultural organizations is the inability of developing a minimal level of internal intercultural integration. This common groundor the path leading to this constructiongives better survival and success chances to multicultural organizations.

Based on my observations, and to state it clearly, the overall argument of this chapter is: that given a minimal set of preconditions, a discourse of proximity combined with practices of microintegration leads to the emergence of intercultural integration.

Praxis

Micro-dynamics of integration

Intercultural integration

The construction of a sense of proximity happens through the diffusion of a body of arguments indicating that the different groups are culturally close to each other. Micro-dynamics of integration are collections of practices and social norms that emerge within and around the organization to support an overarching integration. This simultaneous development of discourse and action allows the collaboration needed to reach positive tangible results (productivity, quality, innovation…).

The antithesis of this equation is the trap to be avoided: the construction of discourses of difference that feed micro-dynamics of separation and jeopardize any potential collaboration.

Construction of a sense of proximity

I call sense of proximity a certain set of discourses that, during my fieldwork, Brazilians and Chinese have put together to argue that they are closer to each other than one might usually expect. Their arguments referred mainly to individuals (the proximity and similarities between Chinese and Brazilians) and to nationalities (the proximity and similarities between China and Brazil).

Because we know Brazilians and Chinese are very different, the sense of proximity is collectively constructed as a partial selection of some objective similarities and by the approximate adaptation, exaggeration, or invention of others.

At the national level, for instance, they indicated this proximity by arguing that both countries share the same level of development: 'We are countries that are similar in development. It helps us to be together. We may have a feeling of being much from the same country (Chinese manager).' ii 'The Chinese treat you well. It is different than being in the US or in Europe. You are not going to feel discriminated by a Chinese because you are a "cucaracha" iii ' (Brazilian director).

At the individual level, the sense of proximity is built as they unveil and emphasize similarities in behavior and values: 'The Chinese is, by character, very generous to those who are visiting him.

[…]

This also makes them similar to Brazilians. In my view, the Chinese are the Brazilians of Asia. We have a lot in common: the talkativeness, the noise, the sense of humor' (Brazilian director). 'We [Chinese and Brazilians] have many things in common. We have football, we are friendly, humorous, and like jokes. We are also very diligent. We work hard and seriously. We know how to make jokes and work well too' (Chinese manager).

As they point to these similarities, they draw generalizations based on their shared personal experiences. The relative cultural proximity is also communicated by out-grouping other nationalities (i.e., by indicating that they are closer to each other when compared to other nationalities): 'I even think that we are closer to the Chinese than we are to some Europeans, as it could be the case of Germans of Englishmen' (Brazilian director).

Working with Brazilians is easier than working with North Americans, French or even people from Singapore. It's amazing because [Singaporeans] have the same cultural roots as we have. But with Brazilians, it's easier because we treat each other as being at the same level.

[…] It may be more important than having the same cultural root or speaking the same language (Chinese General-director).

This is therefore more than just a sense of closeness based on cultural proximity. In some cases, the absence of previous cultural contact can also be an asset Obviously, not all international joint ventures may count with this advantage. If a negative image already exists, managers should make all the possible to not let a bad geopolitical past, history, or preexistent stereotype play against the integration. The sooner the tendency is reversed the better, please remember the integration dinner.

Micro-dynamics of integration

The circulation of discourses of proximity allowed a close coexistence where real practices of integration could flourish. As we start to observe these practices (i.e., the other side of the construction of a sense of proximity), we enter the territory of the various micro-dynamics of integration.

Within the organizations, the close coexistence has been encouraged and, sometimes, created by

design. An example is a company policy that has made all departments deliberately mix: 'In the daily work there is really no difference because of nationality. The departments are mixed. That is very important. And both parts work very well together, compared to other programs I saw, really very well.

We had no real hard time because of conflict' (Chinese Director).

Practices of integration also developed beyond the organizational gates. As the joint ventures started, many Chinese played the roles of hosts or guides to the Brazilians who, in turn, tried to match this generosity. The Chinese would assist the Brazilians and their families in shopping, finding leisure activities, and solving a number of day-to-day problems. They would invite each other to community and family celebrations setting a regime of reciprocity that also allowed a better understanding of the others' culture.

This also created the opportunity for the Brazilians to try to live beyond the Western ghettoes we Activities beyond working hours helped reinforce the connection within the working environment. Most typically, people told me about the importance of eating, drinking (and even smoking) together to create strong bonds.

Another fine example of integration outside of work, which has occurred in both joint ventures, has been the creation of soccer teams just for fun or to play in tournaments involving other companies:

'After we put together the team the integration improved a lot. The Chinese really like it.

[…] They are playful but also take it very seriously.

[…] they 'give their blood' when playing against other factories.

Soccer became an important thing here' (Brazilian manager).

Playing together, they have reinforced a close coexistence inside and outside the organizations.

Indeed, playing and joking have become central to allowing Brazilians and Chinese to learn how to interact in a new cultural setting.

I have also observed that the progressive construction of an intercultural integration resembles a new acculturation. Children observe and play to, one could say, learn a first culture; and the freedom of playing also helps adults to learn a second culture. I comment on three particular aspects of such reacculturation.

Reserving judgment and showing respect to others' culture

A fundamental basis to sustain the intercultural integration is to respect the other culture, show respect, and recognize the differences. 'You see people smiling and respecting other culture background. It is very important (Chinese manager). 'You need to adapt. It is as hard for them as it is for us. We need respect and humbleness from both sides' (Brazilian manager).

As a micro-dynamic of integration, this positive attitude toward the other complements the construction of a discourse of proximity that never denies the existence of real cultural differences.

Proximity perhaps, but they have never expected the other part to fully understand their culture.

Recognizing this limitation is important because it grants the other an intercultural slack that facilitates the integration: 'I don't think that a foreigner would understand [our culture].

[…] The Brazilians are not Chinese so we cannot have the same requirements. Here we respect and accept the differences on both sides' (Chinese manager). 'It would be really difficult to reach a stage where we cease being 'the other.' We may get very close but it is always them and us' (Brazilian director).

Interestingly, they sometimes even developed mechanisms of social control against negative stereotyping or other behaviors that could jeopardize the integration climate:

It all depends on the guy's posture. He may be someone who complains too much. He comes and: "I don't like this food," "this thing is dirty" [...] Tomorrow he is there again "this food is not good", "stuff is not clean". Nobody can bare a person like this! […] Here people have a good attitude. They don't like this complaining thing. They tell him to stop or even give him some silent treatment (Brazilian director).

The cultural guest goes the extra mile

Both groups had to make concessions. However, in the studied cases, the Brazilians were the cultural minority within the organizations and, even more so, in the Chinese society at large:

We are the minority here. I think that this is very clear.

[…] Since the beginning here in China, we always tried to do the best to respect their way of working and be extremely careful to allow the longevity of the company here. You need to be careful when dealing with a different reality (Brazilian manager).

The Brazilians accepted to go the extra mile to adapt to the Chinese day-to-day activities. Except for those productive processes and managerial practices consciously transplanted from Brazil, all remained as Chinese as possible. A Brazilian gave me an example of what he called a policy of zeroconcession: the only changes to the factory facilities have been some Western model toilets.

Another commonly cited example was food:

The food here is Chinese. We never tried to have it done the Brazilian way […] and I think the Brazilians take it with good humor.

[…] We could perhaps have some black beans or coffee brought from Brazil. But I think nobody ever asked. Many actually started drinking tea as the Chinese do (Brazilian manager).

This approach nevertheless produced some victims since adapting to the local Chinese food was problematic for some: Overall both groups appreciated the collective effort of reserving judgment and showing respect, as they also appreciated policies to reduce separation. In one of the organizations, both Chinese and Brazilians repeatedly referred to a story that became part of their organizational mythology. Once the Brazilian partner acquired the 50 percent share that belonged to a European company, they unified the cafeteria and eliminated a number of the benefits exclusive for expatriates, including memberships in social clubs used by foreigners and reserved meeting spaces within the company.

All these micro-dynamicsbased on implicit social norms or explicit polices and managerial decisions -contributed to a progressive integration. As time elapsed and new cohorts of expatriates joined in, they also profited from the accumulated effort to build a positive image, which represented a sort of stock of goodwill: 'The Brazilian may be more integrative than other Westerns. But it is still very difficult. I think it is perhaps easier for us because of the Brazilians who came before. We profit from the good impression they've left here' (Brazilian manager).

Docking into others' cultural traditions

As Chinese and Brazilians interacted, particular cultural dispositions belonging to one side would eventually be adapted to frame the relationship between them. Here is an example:

In more like the master and the apprentice (Chinese manager).

They called him professor […].

There is something about being loyal to the one that teaches that is very important. […] So, when he went back to Brazil, I'm not kidding, there were these two tough guys from the assembling line with tears in their eyes (Brazilian manager).

A binary construction representing a hierarchical arrangement (as: master-apprentice, parentson/daughter, older-sibling-younger-sibling, boss-worker, government official-citizen…) makes more sense for the Chinese than for the Brazilians. It exemplifies how sometimes the Brazilians got docked into some of the peculiarities of the Chinese culture.

As they progressively understood the others' culture, they also found ways of intervene without trespassing some cultural limits. The importance of protecting face to the Chinese is an example:

A Chinese working in your team is going to do all the possible to not bring you information

showing that a colleague of him has made a mistake. They do everything to protect a colleague's face. He is going to tell you he doesn't know, he forgot, or even that he lost that paper or file.

[…] by the kind of smile he has in his face you realize that he knows who did it but he is not going to tell you. This is very important to them. So, […] just respect it.

Never force them do go against it and they will respect you for that (Brazilian director).

Moreover, sometimes they consciously used the others' cultural arrangement to serve a practical purpose:

Their tendency to communicate so fast among them, this gossip thing, it also helps.

[…]

For instance: there is a part that comes from the line with some small problem […], just a matter of aesthetics. You know who did the job. But you […] have to realize that if you talk directly to him the others will be paying attention and the person will be offended. Some may see it just as a manipulative stratagem. I prefer to emphasize the sensibility of finding ways to achieve certain goals without disrespecting the codes of social behavior of the other group.

Beyond intercultural integration

Overtime, the intercultural integration effort leads to the formation of a common spirit, which may be translated in terms of common goals, shared feelings about the future, and identification to the success of the organization: 'We work together very well because the two parts have the same goals. We both want to make things better. […] In both sides people want to do a better job. The feeling about the future is the same' (Chinese manager).

The differences between the two groups are always there, but the construction of a common identity is fundamental to achieve the tangible results that improve their survival and success possibilities. A Chinese General-director commented when referring to a common vision and to a spirit of cooperation:

After the production started, [a Brazilian] vice-president gave a speech and […] said that the success of the joint venture could be explained by three factors: the common vision in terms of market and strategy, the existence of a spirit of cooperation, and the complementary strength of the two companies. I think he was right (Chinese Generaldirector).

And he was proud to tell me so.

Conclusion and recommendations to practitioners

In this chapter, I have tried to examine how some Sino-Brazilian organizations in China have found their way to intercultural integration. As I observed and questioned managers and workers in these companies, they started telling me that Chinese and Brazilian were not that different. They were perhaps trying to convince meand themselves, for that matterthat they were naturally close. But do not fool yourself: they are culturally very far apart and they went through difficult adaptations to work together. iv

They have creatively combined disparate pieces from different national cultures, working cultures, national histories, and geopolitical projects to develop discourses of proximity. They have recognized the differences and have given the other side the benefit of the doubt as they granted them intercultural slacks. They have made sacrifices, left their comfort zones, and put together many different micro-dynamics of integration to reach each other. They have worked hard to bridge an entire-world of differences.

Finally, as they have allowed themselves to coexist very closely, they have discovered ways of interacting positively, acting without violating the other cultural sensibility, and have ended by creating a tradition of respect, collaboration, and common spirit.

Many indeed have adopted a posture that resembles what anthropologists call cultural relativism.

They have tried to appreciate and understand the others' cultural tradition for what it was, to reflect on their own reactions, and to not use their own cultural conventions to judge others' cultures. They have made a huge effort to create a positive climate, to empathize with the other, and to not burn the fieldwork as they have tried to leave a better stereotype behind them.

I am not saying that they were all playing the anthropologist but some were very conscious of their discoveries as they were being acculturated into the new setting.

Nevertheless, the final point here should be what may be learnt from this study.

The specific steps they have taken have helped their intercultural integration. But these are not necessarily applicable to other multicultural organizations, to other South-South combinations, or even perhaps to other case combining Chinese and Brazilians. The proposed generic argument however shows that discourse and practice can be complementary. Despite the unquestionable cultural differences, people can work on similarities to build integration while, very much at the same time, acknowledging differences but not letting these be crystallized as positions of power or arguments of cultural superiority (e.g., 'we know better' or 'our food is better'). Moreover, showing respect and sensibility toward the other, the eventual emerging hierarchical dispositions (as in teacher or boss) can be positively integrated to the local context.

I believe therefore that the main contribution of this chapter is to show that a discourse of proximity might emphasize an integration intention that might, and should, be pragmatically supported by a combination of social norms, polices, and widespread practices at the micro level.

Why going to China?

To close this chapter, I get back to where it started.

In the fieldwork, I many times asked the Brazilians the same question the Swede once asked his Italian colleague: 'So, why did you decide to come to China?' and I got all kinds of answers related to career goals, financial rewards, and personal reasons. But what I really found fascinating were the things they told they unexpectedly learned after actually getting there. Many passionately told me their discoveries about the Chinese and their reality. Even more surprisingly, they also made many discoveries about themselves and about what it means to be Brazilian.

In conclusion to this chapter, perhaps a valuable advice to an executive searching for people to work in multicultural organizations is: look for those who are willing and motivated to make sacrifices in order to learn about the others and about themselves. And, if your candidates ask you: 'So, why should I decide to go to Sweden?', you may now have a good answer.

  belief that 'organization studies will not mature as a field until we spend much more time in observing and absorbing these other [organizational] cultures [and in] learning to see them from the insider's perspective […].' The case of Sino-Brazilian joint ventures Looking for cases of combinations of culturally and geographically distant organizations, I became interested in the Brazilian joint ventures in China. China and Brazil are almost at antipodes. If you could dig a hole in a Rio de Janeiro beach to get to the exact other side of the planet, you would miss China by just seven degrees. Moreover, they also appear to be at cultural antipodes. There has been virtually no historical relation between China and Brazil, and their national cultures are defined by unrelated or opposed traditions: Sino-Tibetan versus Latin-Romance language families; Confucianism, Taoism, and Buddhism versus Catholicism and Afro-American religions; Eastern millenary civilization versus Western new-world immigration land; singleparty socialism versus multipartidary capitalism… China and Brazil are very far apart, and we should therefore expect a lot of difficultiesor plenty of spectacular cultural collisions (Hamada, 1991, p. 5)when Chinese and Brazilians try to work together. I embarked to China with this prospect in mind. But, surprisingly, the Sino-Brazilian organizations I studied there were not particularly marked by cultural conflict. I gathered the data through participant observation and interviews in China in June and July of 2006. I studied two Sino-Brazilian joint ventures, one with twelve years in China and another with four, and I collected some additional data during visits to a division of a US-Chinese joint venture managed by Brazilian expatriates and to a trade office representing a Brazilian company in China i .

Figure

  Figure 1 -Intercultural integration

  sometimes see in larger Chinese cities. A Brazilian who had lived in China for more than ten years explained me: People should go out there and be exposed to see what China is really about. […] There is the guy who lives within what I call the 'embassies ghetto.' […] He may be in China for four or five years and won't see a thing. The same is true about the companies. The guy comes as an expatriate to work for, let's say, Volkswagen. He does not even like the Germans that much. But he works with Germans. And his neighbor is a German. And at night he goes with the family to have beer with the Germans. F***, If it was about living with the Germans he should go to Germany, not to China! (Brazilian director).

Food

  for me is the problem, man. Now I have a strategy. I wake up a half-hour earlier to have time to a really reinforced breakfast. […] I get even some protein supplements. […] I think I eat three times more than in Brazil. Then, at lunch time, I just eat a little bit. I almost just pretend I eat. Some days it is ok. But others, […] the smell is already enough to make me sick. I try controlling myself but I know they can read in my face. They see I don't like the food and I feel embarrassed. […] The girls who serve are disappointed. But what can I do? […] There is some stuff that I really can't eat (Brazilian manager). It shows how important it became to try not to offend the other group cultural sensibility. Interestingly, some Chinese downplayed such problem and put them in the intercultural slack bag: 'If Brazilian person don't like Chinese food. No problem. [There are] different food. I see Brazilian person like or not like. Not need to talk. Look at the face. Different food. In Brazil good food and food I don't like. No problem' (Chinese supervisor).

  my mind, [some] Chinese saw the Brazilians […] as teachers because [their parentcompany] had strong experience and technology. And the Brazilians were happy to be the teachers because they appreciated that Chinese want[ed] to learn. You have to understand that in China the relation of teacher and student is very important. It is more like... [pause]

  So you just throw a comment in the air. You say it to anyone, […] as if you were passing by and just making a kind of generic observation: -'hey. So, do you see this part here. It is quite good don't you think? It deserves perhaps just a bit more of attention here, in the finishing' and you walk away. Don't worry. The message is going to reach the target. It works much better than trying doing it the way we do back home. You can't change the way they are (Brazilian supervisor).