Simon Thevenin
email: simon.thevenin@imt-atlantique.fr

Oussama Ben-Ammar
email: oussama.ben-ammar@mines-ales.fr

Nadjib Brahimi
email: nadjib.brahimi@rennes-sb.com

Robust optimization approaches for purchase planning with supplier selection under lead time uncertainty

Keywords:

Supplier reliability is a critical issue for manufacturing companies. Delivery delays from suppliers create backlog and firefighting on the shop floors. To avoid disruption and hedge against supplier lead time uncertainty, companies rely on diversification, multi-sourcing, and safety lead times. In multi-sourcing, the buyer might order the same product (raw material) from different suppliers. The design of a robust and cost-efficient purchasing/ordering plan in multi-sourcing is a complex task which has a strong impact on the performance of the company. In this study, we investigate the use of robust optimization for the integrated lot-sizing and supplier selection problem under lead time uncertainty. More specifically, we use polyhedral budgeted uncertainty sets. The resulting model determines the ideal lot sizes to minimize the total costs taking into consideration suppliers' reliability and prices. To solve this problem, a row and column generation approach is proposed. To alleviate scalability issues, we enhance the row and column generation through a robust counterpart formulation, and we propose an efficient fix-and-optimize approach. Our extensive computational experiments show that the fix-and-optimize approach yields good quality solutions within a reasonable amount of computational time. We provide insights into supplier diversification based on the risk profile of the decision-maker. One of the conclusions is that an extremely risk-averse decision-maker selects a single supplier, namely the most reliable one even if it does not offer the lowest price.

Introduction

This study was mostly conducted during the COVID-19 pandemic from January 2020 to October 2020. COVID-19 had a significant impact on supply chains, in particular on supply lead time lengths and uncertainties, which has led to supply disruptions [START_REF] Ivanov | Predicting the impacts of epidemic outbreaks on global supply chains: A simulation-based analysis on the coronavirus outbreak (COVID-19/SARS-CoV-2) case[END_REF][START_REF] Queiroz | Impacts of epidemic outbreaks on supply chains: Mapping a research agenda amid the COVID-19 pandemic through a structured literature review[END_REF]. One of the major recommendations to avoid disruptions is source diversification, instead of relying on single sourcing (e.g., Business Insider, 2020 ). For example, Aisin was the only supplier of brake valves for Toyota. After a fire occurred at one of its plants in 1997, Toyota lost revenue estimated at billions of US dollars [START_REF] Nishiguchi | The toyota group and the aisin fire[END_REF]. Subsequently, Toyota decided to have at least two suppliers for each part. Another advantage of multi-sourcing over single sourcing is the reduced power of the supplier over the buyer and an increase in competition between suppliers for price,

The integration of sourcing decisions with dynamic lot-sizing models is one of the highly recommended directions of research suggested in the literature (see, for example, [START_REF] Brahimi | Single-item dynamic lotsizing problems: An updated survey[END_REF]. This integration between supply processes and order-fulfillment processes [START_REF] Krajewski | Operations management: Processes and supply chains[END_REF] can lead to considerable cost reductions and other benefits [START_REF] Aissaoui | Supplier selection and order lot sizing modeling: A review[END_REF][START_REF] Lamba | Integrated decisions for supplier selection and lot-sizing considering different carbon emission regulations in big data environment[END_REF]. In the supplier selection process, tactical decisions include the selection of a pool of suppliers based on a predefined set of criteria. At the operational level, the procurement department decides the quantity to be ordered in each period and order allocation among the suppliers. Joint quantity determination and allocation leads to better decisions. For example, Motorola's suppliers bid to supply items through online auctions. Motorola determines the number of suppliers to source from and the order quantity, for each of these suppliers [START_REF] Metty | Reinventing the supplier negotiation process at Motorola[END_REF].

In this study, we investigate the case of a company that preselects a set of suppliers for a given item and must place orders based on fixed ordering costs, purchasing prices, and delivery lead times offered by the suppliers. The objective is to find a purchasing plan that minimizes total ordering and inventory-related costs. Demand for the item is dynamic in time and the buying company can buy any quantity from any of the preselected suppliers. This approach accounts for the risk of suppliers' late deliveries. Once a supplier is chosen and the order quantity is released, the delivery takes place after an uncertain lead time. As this phenomenon can lead to storage and backlogging over several periods, it increases the costs. Order crossovers are taken into consideration in our model. Order crossovers take place if an order placed in period t may be delivered after an order placed in period t with t ≤ t . It is also assumed that the demand of a period can be served from different suppliers and different time periods. In other words, order splitting is allowed.

Two major approaches are used in optimization under uncertainty in production and procurement planning [START_REF] Grossmann | Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty[END_REF]: robust optimization [START_REF] Ben-Tal | Robust optimization[END_REF] or stochastic programming [START_REF] Birge | Introduction to stochastic programming[END_REF]. Stochastic programming requires a good estimate of the probability distribution of the uncertain parameters, and it seeks to optimize the expected costs or to respect a service level. Robust optimization guarantees feasibility over an uncertainty set. The advantage of robust optimization approaches is that they do not require as much data as stochastic models; they do not need to make any assumptions on data distribution and they adapt to the risk aversion of the decision-maker by taking into consideration the worst case, given a certain budget of uncertainty [START_REF] Bertsimas | The price of robustness[END_REF][START_REF] Bertsimas | A robust optimization approach to inventory theory[END_REF].

The major contributions of this study are as follows: We provide a formulation for the robust dynamic demand lot-sizing (purchasing) and supplier selection problem under lead time uncertainty. We do not make assumptions on order crossovers, order splitting, or on the structure of the demand or lead times. We propose an exact row and column generation algorithm to solve the considered problem, along with some enhancements including a fast cut generation procedure. We develop heuristic methods (A hybrid of robust counterpart and row and column generation, fix-and-optimize, genetic algorithm) to solve large-scale instances. We provide managerial insights to show that supplier diversification does not only depend on supplier prices and inventory-related costs but also on the buyer's behavior in terms of risk aversion.

The remainder of the paper is organized as follows. In Section 2 we provide a literature review. The problem is presented and formulated in Section 3 . In Section 4 we present the optimization approaches. In Section 5 we detail our numerical experiments and analyze the numerical results from a computational point of view, and in Section 5.2 we provide some managerial insights. Fi-nally, we draw conclusions in Section 6 and suggest future research directions.

Literature review

A large body of literature explores supplier selection problems because of their critical impact on the operational costs of a firm. However, most of the literature focuses on the selection of an interesting set of suppliers [START_REF] Wetzstein | A systematic assessment of supplier selection literature-state-of-the-art and future scope[END_REF]. While the placement of orders for these pre-selected suppliers is an important decision, there is little literature on this topic [START_REF] Lamba | Integrated decisions for supplier selection and lot-sizing considering different carbon emission regulations in big data environment[END_REF]. There are two main approaches to supplier selection: single sourcing supplier selection (ss-ss) and multiple sourcing supplier selection (ms-ss). In ss-ss, a supplier meets the whole demand of the buyer for a given product (component). This is usually a more strategic decision-making problem where a long-term contract is signed with the selected supplier. The ms-ss is a rather tactical decision-making problem where no single supplier satisfies the whole demand of a given product or component. For a thorough analysis and comparison of these problems, we refer the reader to [START_REF] Burke | Single versus multiple supplier sourcing strategies[END_REF] . One of the results found by [START_REF] Burke | Single versus multiple supplier sourcing strategies[END_REF] is that the only situation where a single sourcing strategy is dominant is when supplier capacities are large relative to the product demand and when the firm does not desire diversification benefits. [START_REF] Firouz | An integrated supplier selection and inventory problem with multi-sourcing and lateral transshipments[END_REF] indicated that a company should have multiple suppliers for an item when: (i) suppliers experience capacity problems; (ii) the buyer needs a backup source to protect against supplier disruptions; and (iii) the buyers need to maintain competition among suppliers. For a survey of ms-ss models and the associated challenges, interested readers can refer to [START_REF] Minner | Multiple-supplier inventory models in supply chain management: A review[END_REF] . In this study, we analyze the impact of the buyer's risk aversion on her/his preference for ms-ss or ss-ss strategy.

To the best of our knowledge, our study is the first to consider the dynamic lot-sizing problem with supplier selection under leadtime uncertainties. Therefore, the remainder of this section reviews the literature related to the main elements considered in our study, namely, the dynamic lot-sizing problem with supplier selection, lot-sizing under lead time uncertainties, and robust optimization for lot-sizing problems.

Dynamic demand lot-sizing problems have received a lot of importance in the literature. In their survey, [START_REF] Brahimi | Single-item dynamic lotsizing problems: An updated survey[END_REF] presented several extensions of the single-item dynamic lot-sizing problem. These extensions include more general cost structures Koca, Yaman, & Aktürk (for example, 2014 ), constraints on resources Brahimi, Dauzère-Pérès, & Najid (for example, 2006 ), and integration with other supply chain management decisions such as scheduling, warehouse location, distribution, and supplier selection. Supplier selection and lot-sizing decisions are often made separately in practice, despite the benefits of integrating the two decisions. Surveys of integrated models can be found in [START_REF] Aissaoui | Supplier selection and order lot sizing modeling: A review[END_REF][START_REF] Golmohammadi | Review of supplier diversification and pricing strategies under random supply and demand[END_REF][START_REF] Svoboda | Review of multi-supplier inventory models in supply chain management: An update[END_REF]. There is limited research on the lot-sizing problem with supplier selection in an uncertain environment, and demand and yield have been the focus of most studies [START_REF] Federgruen | Infinite horizon strategies for replenishment systems with a general pool of suppliers[END_REF]. To the best of our knowledge, there are no studies on integrated supplier selection and lot-sizing under lead time uncertainty.

Nevertheless, there is a growing amount of research on classical lot-sizing problems under lead time uncertainty [START_REF] Aloulou | A bibliography of nondeterministic lot-sizing models[END_REF][START_REF] Dolgui | A state of the art on supply planning and inventory control under lead time uncertainty[END_REF]. Some studies aim to determine the optimal planned lead time through mathematical analysis (for example, Ben-Ammar, Castagliola, [START_REF] Ben-Ammar | A hybrid genetic algorithm for a multilevel assembly replenishment planning problem with stochastic lead times[END_REF]. However, to simplify the computation of the probabilities of different states, these approaches require strong assumptions (single period, constant demand, no order crossover, among others). Consequently, these approaches are not applicable in complex supply chain environments such as the multi-period lot-sizing problem with setup [START_REF] Thevenin | Material requirements planning under demand uncertainty using stochastic optimization[END_REF]. In particular, the majority of these studies assume that order crossover cannot occur ( Disney, Maltz, Wang, & Warb urton , 2016;[START_REF] Riezebos | Inventory order crossovers[END_REF]. We do not make such an assumption in this study. Some of the solution approaches for such problems include dynamic programming algorithms such as those developed by [START_REF] Liberatore | Planning horizons for a stochastic lead-time inventory model[END_REF] and [START_REF] Alp | Optimal lot-sizing/vehicle-dispatching policies under stochastic lead times and stepwise fixed costs[END_REF]. [START_REF] Nevison | The dynamic lot-size model with stochastic lead times[END_REF] proposed a multi-stage stochastic optimization approach for lot-sizing under lead time uncertainty, and Thorsen & Yao (2017) proposed robust optimization for this problem. Other studies on lead time uncertainty in lot-sizing problems include [START_REF] Ben-Ammar | Optimization of multi-period supply planning under stochastic lead times and a dynamic demand[END_REF]Rossi, Tari m, & Bollapragada, 2012 ). However, to the best of our knowledge, no study in this area considers supplier selection.

Several approaches exist to account for uncertainty in optimization problems. Stochastic programming [START_REF] Birge | Introduction to stochastic programming[END_REF] models the uncertain parameter through a probability distribution, and it minimizes the expected costs. In robust optimization [START_REF] Ben-Tal | Robust optimization[END_REF], the parameter subject to uncertainty takes value in an uncertainty set that contains possible realizations of the uncertainty. A robust optimization model will return a solution that minimizes the costs for the worst scenario realization. To overcome the over-conservatism of this approach, [START_REF] Bertsimas | The price of robustness[END_REF] proposed incorporating a budget of uncertainty into the robust optimization model to limit the number of uncertain parameters that can change at the same time. Finally, the distributionally robust optimization approach [START_REF] Wiesemann | Distributionally robust convex optimization[END_REF] describes the parameter through a set of probability distributions, and it seeks the solution minimizing the costs for the worst-case distribution. The choice of the approach depends on the decision maker's preference, on the availability of data, and on the required computation time. The present work focuses on robust optimization. In contrast with analytical models or stochastic optimization approaches, robust optimization does not require the estimation of a probability distribution. Such an approach is well-suited for contracting, as the reliability of the agent (in our case, the supplier) is known once he/she delivers to the manufacturer [START_REF] Yu | Robust contract designs: Linear contracts and moral hazard[END_REF]. In addition, robust optimization is practical for crises, where historical data are not representative of the current situation.

In comparison to the extensive amount of research on optimization for planning problems, the application of robust optimization remains scarce. Nevertheless, research on the application of robust optimization for inventory control is growing, and most works focus on the demand uncertainties. [START_REF] Bertsimas | A robust optimization approach to inventory theory[END_REF] introduced the tractable reformulation for the static problem with the budget uncertainty approach. [START_REF] Bienstock | Computing robust basestock levels[END_REF] propose an adversarial approach to compute a base stock policy. [START_REF] Ben-Tal | Retailer-supplier flexible commitments contracts: A robust optimization approach[END_REF] provide a tractable reformulation of the adjustable robust optimization to deal with the inventory management problem in a two-echelon supply chain with flexible commitments contracts. [START_REF] Wagner | Robust inventory management: An optimal control approach[END_REF] gives a closed-form solution for the infinite dimension version of the problem. [START_REF] See | Robust approximation to multiperiod inventory management[END_REF] provide a second-order conic program for truncated linear replenishment policies (that correspond to an S policy), and they characterize the uncertain demand by covariance and directional deviation in addition to the classical mean and standard deviation. In addition, there exist several studies on extensions of the inventory management problem. For instance, [START_REF] Wei | Robust optimal policies of production and inventory with uncertain returns and demand[END_REF] consider the planning problem with remanufacturing and uncertain item returns and demand, and [START_REF] Aouam | Integrated production planning and order acceptance under uncertainty: A robust optimization approach[END_REF] propose a robust optimization approach for the integrated production planning and order acceptance. Except for [START_REF] Bertsimas | A robust optimization approach to inventory theory[END_REF] , [START_REF] See | Robust approximation to multiperiod inventory management[END_REF] , all the above studies ignore the fixed ordering costs. On the contrary, Solyalı, Cordeau, & Laporte (2016) consider fixed setup cost, and the authors show that the facility location formulation of the lot-sizing problem yields a more efficient robust formulation. [START_REF] Chu | A robust optimization approach to model supply and demand uncertainties in inventory systems[END_REF] provide a reformulation for the case with demand and supply uncertainty. However, [START_REF] Chu | A robust optimization approach to model supply and demand uncertainties in inventory systems[END_REF] study the case of supply quantity uncertainty with a single supplier, whereas we consider delivery date uncertainty with supplier selection. We refer the interested reader to [START_REF] Lu | A review of robust operations management under model uncertainty[END_REF] for a recent review on the application of robust optimization to operation management problems.

To the best of our knowledge, Thorsen & Yao (2017) and [START_REF] Hnaien | Robust single-item lot-sizing problems with discrete-scenario lead time[END_REF] are the only studies proposing robust optimization approaches for lot-sizing problems under lead-time uncertainties. However, compared to our study, Thorsen & Yao (2017) consider a problem with only one supplier and ignore the fixed ordering costs in their model. [START_REF] Hnaien | Robust single-item lot-sizing problems with discrete-scenario lead time[END_REF] explored the single supplier lot-sizing problem with discrete scenarios. The authors present specific characteristics of the problem, and they show that it is NP-hard, even with only two scenarios. Note that some studies consider uncertain travel time in the inventory routing problem (e.g., [START_REF] Agra | Robust optimization for a maritime inventory routing problem[END_REF][START_REF] Liu | Two-stage distributionally robust optimization for maritime inventory routing[END_REF]. However, in the inventory routing problem, the production rate is typically given, and the uncertain transport time impacts the amount produced and consumed between two delivery/replenishment rather than the delivery dates. To the best of our knowledge, there exists no study on robust optimization for the production routing problem (the extension of the inventory routing which includes production decisions) under transport time uncertainty.

In summary, this study contributes to models integrating production planning and sourcing decisions under lead-time uncertainty. To the best of our knowledge, it is the first to investigate robust optimization for supplier selection decisions. Second, we propose optimization methods applicable to robust lot-sizing models under lead time uncertainty. The robust optimization model seeks to minimize the cost of the worst-case lead-time realization. In practice, the number of lead time realizations is too large to generate them all. Consequently, we provide a row and column generation approach. However, this approach does not converge fast enough to the optimal solution. Therefore, we develop several approximations and heuristic approaches to solve the problem, namely an approximation based on the robust counterpart reformulation, a hybrid of robust counterpart reformulation and row and column generation, a fix-and-optimize method, and a genetic algorithm. Third, we provide managerial insights that will help practitioners understand and use the models. In particular, we analyze the level of supplier diversification depending on the risk aversion profile of the buyer. We observe that risk-averse decisionmakers tend to order from multiple suppliers. However, when their aversion to risk increases, the number of selected suppliers reduces to include only the most reliable ones.

The robust lot-sizing with supplier selection problem (RLS-SS)

Below, we provide a formal description of the robust supplier selection and lot-sizing problem (RLS-SS) under lead time uncertainty. For the sake of clarity, we provide the deterministic formulation of the problem before presenting the robust version.

Deterministic model

The inputs to the problem are the demand d t for each period t in the planning horizon of length |T | ( t ∈ T ), and the set of suppliers S, where each supplier s is characterized by a per unit price p s , a fixed ordering cost o s , and a delivery lead time L s . The problem is to decide the quantity Q ts to order in period t from supplier s, to minimize the fixed ordering costs, variable purchasing costs, and inventory and backlogging costs.

A mixed-integer linear programming formulation (MILP) of the deterministic problem is presented below. In addition to the symbols introduced above, inventory holding costs and backlogging costs are denoted h and b, respectively. Similarly to Thorsen & Yao (2017) and in order to formulate Constraints (2) below, we define the parameter δ τts = 1 if the quantity Q τ s ordered in τ from supplier s arrives before period t, and 0 otherwise. This also means that the lead time L s is smaller than or equal to t -τ . Besides Q ts , the model includes decision variables to represent the inventory level I t and the backlogged quantity B t at the end of each time period t, and the binary variables Y ts = 1 if an order is placed in period t from supplier s, and 0 otherwise.

[ DET ] min

t∈T s ∈S ( o s Y ts + p s Q ts ) + t∈T ( hI t + bB t ) (1) s.t. I t -B t = t τ =1 s ∈S δ τts Q τ s - t τ =1 d τ t ∈ T (2) Q ts ≤ Y ts t∈T d t t ∈ T s ∈ S (3) Q ts ≥ 0 and Y ts ∈ { 0 , 1 } t ∈ T s ∈ S (4) I t , B t ≥ 0 t ∈ T (5)
The objective function (1) minimizes the total cost composed of fixed ordering, variable purchasing, inventory, and backlogging costs. The constraints in (2) calculate the inventory and backlog levels at the end of each time period t. Note that lead times are indicated by parameter δ τts , which is equal to 1 if an order placed with supplier s at time period τ arrives at or before time period t.

Hence, for a given supplier s with lead time L s , δ τts = 1 only when t ≥ τ + L s . The constraints in (3) link the binary variables Y ts to the continuous quantities Q ts . Note that in constraint (2) , we assume, without loss of generality, that the horizon starts with no backlog or inventories. The constraints in (4) and ( 5) are integrality and non-negativity constraints.

As mentioned earlier, we provide the deterministic model for clarity only. In fact, the problem with deterministic lead times is equivalent to a problem with no lead times. In addition, solving the deterministic model using a MILP solver is not efficient. There exist exact polynomial-time dynamic programming algorithms that can solved it in O ( |S| × |T | 2 ) (e.g., [START_REF] Toledo | Lot-sizing problem with several production centers[END_REF]. This formulation is the basis of the robust optimization model presented in Section 3.2 . We also compare the deterministic model with the robust optimization model in the numerical experiments.

In this deterministic model, to make sure that all demands are satisfied before the end of the planning horizon, Constraint (6) below should be added.

I |T | = B |T | = 0 (6)
However, when there is uncertainty on lead times, this constraint can result in over-conservative solutions. In a robust model, it would require placing all orders before |T | -L max ; where L max is the longest possible realization of the lead time. To be less conservative, Constraint (7) can be used instead.

t∈T s ∈S Q ts ≥ t∈T d t (7)
More discussion about the ending horizon effects is done in the numerical experiments section.

Robust optimization

This section describes the robust model to handle the uncertainty of lead times. The robust optimization approach seeks to minimize the costs for the worst-case realization of the delivery delays. The resulting production plan performs well for all these realizations, but protection over a wide range of lead time values is costly. In other words, a model that accounts for any possible lead time realization yields over-conservative purchasing plans. To limit the considered lead time realization to realistic values, we use budgets of uncertainty, as proposed in [START_REF] Bertsimas | The price of robustness[END_REF] . In this study, we consider a polyhedral budgeted uncertainty set. Such uncertainty sets are understandable by decision-makers, and they can be tailored for a specific problem. We aim to define the set specifically for suppliers who want to hedge against supplier's delivery delays. Given the lead time L min s displayed by supplier s , the manufacturer foresees a maximum delay, and he/she can set the lead time interval L min s , L max s for each supplier. Further constraining the uncertainty set provides less conservative decisions, and we assume the user may tighten the uncertainty set based on attributes of the delivery delays. Here, we propose three different constraints to limit the uncertainty set:

1. First, the user may assume a maximum number 1 of late deliveries per period, where an order is late if it is delivered after the displayed lead time L min s . As a result, the uncertainty set contains only lead time realizations where the number of late orders in each period is lower than 1 . 2. Second, the user may restrict the maximum number of late deliveries over the horizon. That is, over the entire planning horizon, at most 2 deliveries have a lead time larger than L min s . 3. Third, the user may limit the total lateness to 3 periods. If the order placed to supplier s in period t is delivered in period L st , its lateness is L st -L min s periods. 3 is the sum of the lateness over all the orders placed.

In practice, such an uncertainty set may be extended with userspecific constraints on the delays. More generally, the methods proposed in the rest of this work remain applicable if the lead times take values in a different polyhedral set. For instance, while our study focuses on methods to hedge against delivery delay, the model may be easily extended to hedge against early deliveries. In such a case, the nominal value corresponds to the average delivery lead time, and the uncertainty set must include additional constraints to account for a budget of early delivery.

Formally, the set of possible lead time realizations is defined as follows:

= { δ ∈ R |T | ×|T | ×|S| | (8) δ τts ≤ δ τ,t+1 ,s t, τ ∈ T s ∈ S (9) -δ τts ≤ -1 s ∈ S τ | t ≥ τ + L max s (10) δ τts ≤ 0 s ∈ S τ | t < τ + L min s (11) |S| - s ∈S δ t-L min s ,t,s ≤ 1 t ∈ T (12) s ∈S t∈T (1 -δ t-L min s ,t,s ) ≤ 2 (13) s ∈S t∈T τ ≤t-L min s (1 -δ τts ) ≤ 3 (14) 0 ≤ δ τts ≤ 1 τ, t ∈ T s ∈ S} (15)
Constraints ( 9) state that if an order has arrived at t ( δ τts = 1 ), then this order is available for subsequent time periods ( δ τt s = 1, for t > t). Constraints ( 10) and ( 11) enforce the lead times to be within the interval [ L max , L min ]. Budget constraints are ( 12), ( 13), and ( 14). Constraints ( 12) state that at most 1 orders are late in each period. Constraints in ( 13) state that at most 2 orders are late over the whole horizon. Constraints ( 14) state that the sum of lateness in the number of time periods over the horizon is smaller than 3 . We consider δ τt s as a continuous variable. In practice,

this assumption corresponds to the case where suppliers can deliver partially in a period and complete their delivery later.

The considered problem can be formulated as a two-stage model, where the first stage selects the suppliers and the ordering quantities Q T S , whereas the second stage computes the worstcase inventory and backlogging costs f (Q T S ). More precisely, the resulting robust lot-sizing with supplier selection problem formulation [RLS-SS] is: 4) , (7) , where the worst-case inventory and backlogging costs f (Q T S ) associated with the ordering quantity matrix Q T S are obtained by solving the following sub-problem [SUB]:

[ RLS -SS ] min t∈T s ∈S ( o s Y ts + p s Q ts ) + f (Q T S ) (16) s.t. (3) -(
[ SUB ] f (Q T S ) = max t∈T ( hI t + bB t ) (17) s.t. I t -B t = t τ =1 s ∈S δ τts Q τ s - t τ =1 d τ t ∈ T (18) I t ≤ α t |T | τ = t+1 d τ t ∈ T (19) B t ≤ (1 -α t ) t τ =1 d τ t ∈ T (20) α t ∈ { 0 , 1 } t ∈ T (21) δ τts ∈ τ, t ∈ T s ∈ S (22)
To find the worst-case lead time realization within the uncertainty set, the objective (17) maximizes the inventory and ordering costs. The level of inventory and backlogging in each period t is computed using ( 18) , and it is the amount of item received minus the cumulative demand up to period t. Because this is a maximization problem, if Eq. ( 18) are used alone, it can result in solutions with both I t and B t strictly positive. To avoid this situation, we introduce the binary variable α t equals to one if the inventory level is positive in period t, and 0 otherwise. Constraints (19) (resp. ( 20) )

for the inventory (resp. backlog) level to 0 if α t equals 0 (resp. 1).

Constraints ( 21) and ( 22) give the domain of the variables.

Proposition 3.1. The RLS-SS and the sub-problem SUB are NP-hard

Proof. RLS-SS is NP-hard because it is an extension of the robust single item lot-zing problem under lead time uncertainty, which is NP-Hard [START_REF] Hnaien | Robust single-item lot-sizing problems with discrete-scenario lead time[END_REF]. Besides, even the sub-problem SUB is NP-Hard, and we prove it with a reduction from the knapsack. The decision version of SUB asks if there exists an assignment of the lead times that lead to an inventory cost larger than value B. Given a bag with capacity C and a set of items where each item is associated with a weight w i and profit λ i , the decision version of the knapsack asks is there exists a subset of items with profit larger than β and that respects the capacity. Given an instance of the knapsack, we create the following instance of the SUB:

• h t = 0 and b t = 1

• 3 is set to C, whereas 1 and 2 are large enough to not be constraining. andd T is large enough (any upper bound of the optimal solution, for instance, d T can be set to the sum of profit.)

• d t = 0 ∀ t ∈ T -{ T } ,
• For each item, we create a supplier i , with L min i = 0 and L max i = w i , and we place an order

Q (T -w i ) i = λ i to supplier i in period T -w i .
• We set the time horizon large enough ( max i ∈ I w i )

• We set B to β.

For this instance of SUB, delaying an order by less than w i units is sub-optimal since it consumes the budget, but it does not increase the costs. Similarly, an order cannot be delayed by more than w i since L max i = w i . Therefore, the problem is to select the orders to delay by exactly w i units, and delaying the order of supplier i increases the costs by λ i units, and it consumes w i units of the budget. Therefore, solving SUB yields the solution to the knapsack, and the decision version of SUB is NP-complete, and the optimization version is NP-Hard.

Finally, we assume that all suppliers in the set S are nondominated since a dominated supplier would never be selected. We propose the following definition for the dominance relation between two suppliers:

Definition 3.1. A supplier s 1 is in S if and only if: ∀ s 2 ∈ S, ¬ ((o s 1 ≤ o s 2 ) ∧ (p s 1 ≤ p s 2 ) ∧ (L max s 1 -L min s 1 ≤ L max s 2 -L min s 2 ))
where ¬ and ∧ represent the logical "not" and "and" respectively.

Optimization approaches

This section presents several solution approaches to solve the robust supplier selection and lot-sizing problem under lead time uncertainty. The first procedure is a row and column generation approach ( Section 4.1 ). As this method suffers from scalability issues, we propose different heuristic approaches to solve large instances in reasonable computation time. First, we provide a robust counterpart reformulation ( Section 4.2 ). The robust counterpart formulation is based on a reformulation per constraint. Thus, this model is a slight modification of the original problem, where the worst-case cost is computed independently in each period. In other words, the worst-case scenarios might be different in two different periods. While this approach requires significantly less computation time, it yields over conservative solutions. We show how to embed this robust counterpart formulation in a hybrid of row and column generation and robust counterpart reformulation ( Section 4.3 ). Then, we study the possibility of embedding two common heuristics for lot-sizing in the row and column generation framework, namely a fix-and-optimize ( Section 4.4 ) method and a genetic algorithm ( Section 4.5 ).

Row and column generation approach

A generic approach to solve robust optimization problems relies on the set of all possible lead-time realizations within the uncertainty set. The resulting optimization problem for the RLS-SS is given below, where ω denotes a scenario, that is, a specific lead time realization, and each component of this matrix is denoted by δ ω τts . We also introduce the inventory or backlogging cost c ω t in period t for scenario ω, and the worst-case cost C. As the backlogging and the inventory costs are complementary (either the inventory or the backlog is positive in a period for a given scenario, but not both at the same time), the cost c ω t is computed with the pair of inequalities ( 24) and ( 25). The constraints in (26) compute the worst-case cost over all the scenarios.

[ RCG ] min 4) , (7) ,

t∈T s ∈S ( Y ts o s + Q ts p s ) + C (23) s.t. (3) -(
c ω t ≥ h t τ =1 s ∈S δ ω τts Q τ s - t τ =1 d τ t ∈ T ω ∈ (24) c ω t ≥ -b t τ =1 s ∈S δ ω τts Q τ s - t τ =1 d τ t ∈ T ω ∈ (25) C ≥ t∈T c ω t ω ∈ (26) c ω t ≥ 0 t ∈ T ω ∈ (27) C ≥ 0 (28)
Model [RCG] can be solved using any mixed-integer linear programming solver. However, the set of scenarios is too large for the approach to be tractable. In fact, the number of scenarios is infinite as δ τts are continuous. Therefore, a common solution approach to solve the considered problem relies on the row and column generation approach (also called adversarial formulation) [START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF]. Rather than solving the model for the entire set of scenarios , this approach iteratively builds a subset of scenarios , with only the scenarios required to prove optimality. This approach initializes the set of scenarios with a single scenario where all suppliers deliver on time, and it iteratively builds the set of scenarios. In each iteration, the row and column generation methods perform the following steps:

1. Solve model [RCG] on the current set of scenarios , to get the purchasing plan Q T S .

2. Solve model ( 17) -( 22) to get f ( Q T S ) and the scenario ω with lead time values maximizing the inventory and backlogging costs. 3. Add scenario ω to the set of scenario.

As [RCG] uses a restricted set of scenarios in each iteration, its optimal cost is a lower bound of the initial problem. In contrast, f ( Q T S ) is a valid evaluation of the trial solution Q ts , and it provides an upper bound. The method stops when the gap between the upper and lower bounds is sufficiently small, or when a time limit is reached.

To speed up the convergence of the row and column generation approach, we use the algorithmic improvement proposed in [START_REF] Mcdaniel | A modified benders' partitioning algorithm for mixed integer programming[END_REF] for Benders decomposition. We start by solving the linear relaxation of the first-stage problem. Once the optimal solution of the LP relaxation is found, the integrality constraints are enforced to solve the initial problem in a few iterations. For the considered problem, the integrality constraints on the Y ts are relaxed to quickly generate interesting scenarios. Once the approach converges, the initial model is solved.

Robust counterpart reformulation

Robust counterpart reformulation ( RCR ) [START_REF] Bertsimas | The price of robustness[END_REF] ) considers the worst case of each constraint independently, and it reformulates each constraint with dualization to yield a tractable model. For our problem, RCR considers the inventory holding and backlogging costs constraints separately before reformulating them by taking the dual. That is, the cost function sums the maximum between the worst-case inventory and worst-case backlog in each period, and not the backlogging or inventory cost in the worst-case scenario as in the original model.

This slightly modified model is faster to solve through a commercial solver than the original one, and its solution is valid (but not necessarily optimal) for the original problem. In addition, Thorsen & Yao (2017) showed that RCR yields good quality solutions for a similar problem. For the polyhedral uncertainty sets, the robust counterpart reformulation requires three steps [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF]. The first step expresses the cost constraint that must be satisfied for all scenarios with a single constraint that corresponds to the worst-case scenario. Indeed, if the constraint is valid for the worst-case scenario, it is valid for all scenarios. Consequently, this constraint includes a maximization inner problem to find the worst-case scenario. In our case, the model becomes:

min t∈T s ∈S (Y ts o s + Q ts p s ) + t∈T c t (29) s.t.
(3) , ( 4) , ( 7) ,

c t ≥ max ω∈ h t τ =1 s ∈S δ ω τts Q τ s - t τ =1 d τ t ∈ T (30) c t ≥ max ω∈ -b t τ =1 s ∈S δ ω τts Q τ s - t τ =1 d τ t ∈ T ( 31
)
where the scenario with the maximum inventory in ( 30) and ( 31) is selected independently for each time period. In contrast, the original model takes the worst case in each scenario (see constraints in (26) in the [RCG] model).

The second step is to build the dual of the maximization problem. Given fixed purchasing quantities Q ts , the right-hand side of Constraints (30) can be rewritten as follows:

max t τ =1 s ∈S hδ τts Q τ s - t τ =1 hd τ s.t. (9) -(15) . ( 32
)
The primal and dual yield the same cost, and thus the primal can be replaced by the dual. A major advantage of the dual is that it does not contain the multiplication of the variable that exists in the primal. The dualization is performed independently for each constraint (not only for the backlog and inventory cost in a period but also independently between the different periods). Therefore, the uncertainty set must be expressed based on the information available in each period t only. First, the constraints in (9) ( δ τts ≤ δ τ,t+1 ,s ) disappear because they link periods t and t + 1 . Second, Constraint (34) prevents more than 2 late orders in each period t. In contrast to Constraint (13) , Constraint (34) only accounts for the δ's that appear in each of the constraints in (30) .

As a result, Constraint (34) prevents more than 2 late deliveries among orders passed before period t. Note that in contrast to Constraint (33) , Constraint (34) counts all late orders, and not only orders late in a single period. Similarly, Constraint ( 14) is modified to account only for the δ's that appear in each of the Constraints (30) . Thus, (35) prevents the total lateness observed in period t from being larger than 3 . Finally, Constraints (11) are removed, the unnecessary variables are not defined, and the con-

stant (-h τ ∈ 0 ... t d τ ) is
t τ =1 s ∈S hδ τts Q τ s s.t. |S| - ∫∈S δ -L \ ∫ , , ∫ ≤ -∞ (ρ 1 t ) (33) s ∈S τ ≤t-L min s (1 -δ τts ) ≤ 2 (ρ 2 t ) (34) s ∈S τ ≤t-L min s (t -τ -L min s + 1)(1 -δ τts ) ≤ 3 (ρ 3 t ) (35) -δ τts ≤ -1 τ ≤ t -L max s s ∈ S (ξ τts ) (36) δ τts ≤ 0 τ > t -L min s s ∈ S (λ τts ) (37) δ τts ≤ 1 τ ≤ t s ∈ S (ψ τts ) (38) δ τts ≥ 0 τ ≤ t s ∈ S ( 39
)
The second step formulates the dual problems provided in the online supplement. In the third step, we drop the dual in Constraints ( 30) and ( 31) . As the objective of our problem is to minimize the sum of the costs c t , it seeks to minimize the right-hand side of ( 30) and ( 31) , the minimum sign can be omitted in the right-hand side of these constraints.

[ RCR ] min

t∈T c t + s ∈S (Y ts O s + Q ts p s ) s.t.
(3) -( 4) , ( 7) ,

c t ≥ ρ 1 t ( 1 -|S| ) + ρ 2 t 2 - s ∈S τ ≤t-L min s 1 + ρ 3 t 3 - s ∈S τ ≤t-L min s (t -τ -L min s ) -h t τ =1 d τ t ∈ T c t ≥ ρ 1 t ( 1 -|S| ) + ρ 2 t 2 - s ∈S τ ≤t-L min s 1 + ρ 3 t 3 - s ∈S τ ≤t-L min s (t -τ -L min s ) + b t τ =1 d τ t ∈ T

Hybrid robust counterpart reformulation with row and column generation

As explained earlier, the robust counterpart reformulation in Section 4.2 is an approximation because it considers the worst lead time realization independently for each constraint. Nevertheless, based on our experimental results, the simplification is small, and the resulting solution sol leads to a good heuristic. To further improve this solution, the hybrid robust counterpart reformulation and row and column generation takes the setup values in sol and fixes them in the row and column generation approach. The resulting linear program can be solved efficiently. Such an approach shows that the robust counterpart reformulation approach has merit even when the uncertainty set is hard to express as a convex set. Moreover, such an approach could be applied to other problems (e.g., where the uncertain parameters take discrete values).

Fix-and-optimize heuristic

We propose a fix-and-optimize heuristic [START_REF] Helber | A fix-and-optimize approach for the multi-level capacitated lot sizing problem[END_REF] to find good-quality solutions within a reasonable amount of time. The approach starts with an initial solution (Economic Order Quantity based heuristic). This solution is improved with the fixand-optimize procedure applied to the robust counterpart reformulation framework before applying the fix-and-optimize heuristics to the row and column generation framework. We successively describe the methods to generate the initial solution (Step 1), the fix-and-optimize in the robust counterpart reformulation framework (Step 2), and the fix-and-optimize in the row and column generation framework (Step 3).

Step 1: Initial solution: To produce a starting solution, the initialization step selects a single supplier. The initialization step selects the supplier s with the lowest estimated cost ( EC s ):

E C s = D p s + o s D E OQ s ( 40
)
where D is the average demand over the planning horizon and EOQ s is the approximated economic order quantity of supplier s calculated as:

EOQ s = 2 o s D h , (41)
Once the supplier s is selected, we solve the robust counterpart formulation (model RCR) for the single supplier problem within a short computation time limit (set to 30 s in our implementation) to get an initial solution. The single supplier problem corresponds to the cases where the setup variables are set to 0 for all suppliers except s .

Step 2: Fix-and-optimize for the robust counterpart reformulation . The second step aims to quickly find a good solution to the robust counterpart formulation. Fix-and-optimize solves the model iteratively. In each iteration, a large proportion of the setup variables is fixed, and only a few of them remain open for optimization. Therefore, the model is solved quickly. The approach performs two types of fix-and-optimize passes. The first seeks to improve supplier selection decisions, whereas the second improves lotsizing decisions. Fix-and-optimize iterates these two passes successively, and it stops if both passes are not able to improve the current solution.

• The supplier selection based pass opens the binary variables Y ts for all suppliers s at a given period t. The pass starts in period 0, and iterates for each period t in the horizon. • The lot-sizing based pass opens the variables Y ts for all suppliers s in S u and all periods t ∈ [ a, b ] , where S u is the set of currently-used suppliers, and [ a, b ] is a given time interval. The pass starts at period 0, and after each iteration, it shifts the interval by half of its length.

Step 3: Fix-and-optimize in the row and column generation framework. The online supplement gives the steps of the fixand-optimize approach in the row and column generation framework. In each iteration, the scenario-based model is solved with a given set of scenarios and with most of the setup variables fixed to their current values and a few open. In this context, an improvement in optimization does not mean an improvement for the global problem because the optimizer has a partial set of scenarios only. Therefore, if the optimization of the scenario-based model improves the best-known solution (evaluated with f (Q T S ) ), the method moves there, and the current solution changes. Otherwise, it adds the worst-case scenario in the current set of scenarios, and continues with the current solution. To speed up the method, the fix-and-optimize approach starts by generating an interesting subset of scenarios. These scenarios are obtained by fixing all setup variable to the value of the initial solution, and iterates until it finds the best purchasing quantities for the initial setup values.

In step (2), the approach stops when the two successive passes cannot improve the solution. In step (3), the approach stops after a given time limit. If two successive passes do not improve the solution in step (3), we increase the size of the intervals.

Genetic algorithm

In this section, a genetic algorithm is developed and coupled with the model RCR. The decision variables are the binary variables Y ts , where Y ts is equal to 1 if an order is passed to supplier s in period t, as defined before. A chromosome is encoded

( 2 o s / ( D h ) (h + b) /b
) is an estimate of the maximum time between two orders computed based on the EOQ formula extended to account for backlog [START_REF] Silver | Inventory and production management in supply chains[END_REF]. For each individual of the initial population, G setups are set to 1, and they are selected randomly with a uniform distribution. Each one is evaluated using RCR model with a fixed setup value as a fitness function.

The elitist strategy is employed to select individuals on which we apply evolutionary operators. Here, we only consider a standard single-point crossover. It is randomly performed horizontally or vertically with a probability x 1 . Therefore, we choose this point between 1 and |S| or between 1 and |T | . For the mutation operator, four types of mutations are considered: (i) if Y ts = 0 , mutate to 1 with probability m 1 , (ii) if Y ts = 1 , mutate to 0 with probability m 2 and Y lk = 1 (where k is randomly generated between 1 and |S| , and l between 1 and |T | ), (iii) if Y ts = 1 , mutate to 0 with probability m 3 ; (iv) if Y ts = 1 , mutate to 0 with probability m 4 and Y lk = 1 (where k and l are randomly generated, ∀ k, l ∈ {-1 , 1 } ).

Experiments

This section presents the numerical experiments that were run using the approaches presented above. The algorithms were implemented using C++ language, with FICO (2019) Xpress version 8.6 as the MILP solver. No changes were made to default settings. The tests were carried out on a server with an Intel(R) Xeon(R) X5650@2.67GHz processor. The generation of datasets was inspired mainly by the studies of Thorsen & Yao (2017) and Brahimi & Aouam (2016) . Two groups of instances were generated. The purpose of the first group is to analyze the performance of the solution approaches. The purpose of the second group is to provide managerial insights. The method to generate this data is presented in the online supplement. In particular, it is worth to mention here that when a planning horizons is set to 41 time periods, for example, the demand for the first 11 periods is set to zero. The 11 periods correspond to the longest lead time of suppliers. This is to allow all suppliers to deliver on time.

This section is divided into two parts. The first part summarizes the numerical experiments that were run to analyze the numerical performance of the algorithms. The second part presents managerial insights based on a large set of generated data.

Performance of the methods

This section evaluates the performance of the proposed approaches in terms of convergence towards the optimal solution and in terms of solution quality. We provide a summary of the methods below. To show the benefit of each step of the fix-and-optimize approach, three versions are considered, where the ingredients are added one by one.

• DET Min , DET Max , DET A v g : deterministic model ( 1) -( 5 ), respectively. • RC : the row and column generation approach leading to the true optimal solution of the considered problem (see Section 4.1 ). • F AO : the three steps of the fix-and-optimize approach (see Section 4.4 ), with an interval length of five periods. • F AO 1 : Step 1 of the fix-and optimize approach (see Section 4.4 ).

• F AO 2 : Steps 1 and 2 of the fix-and-optimize approach (see Section 4.4 ). • GA : Genetic Algorithm (see Section 4.5 ).

Convergence of the exact methods

The evaluation in terms of convergence to the optimal solution includes only the exact methods. To analyze the convergence of RC , RCR , and DET , Table 1 reports the average gap and computational time required to solve the instances with a given planning horizon size |T | and the number of suppliers |S| . These gaps indicate the convergence of the method. For RCR and DET , we give the integrality gap Gap Int returned by Fico Express. For RC , Gap RC corresponds to the average gap between the lower LB RC (solution of RCG on the subset of scenarios) and upper bound UB RC (obtained by solving (17) -( 22) ) as follows:

Gap RC = 100 UB RC -LB RC LB RC .
In addition, we provide the number of iterations (Nr it) performed by RC (without accounting for the warm-up phase where the linear relaxation is solved), as well as the time spent solving the master problem and the subproblem.

Table 1 shows that the considered problem is difficult to solve as even the deterministic version of the problem cannot be solved optimally within 10 min. A deeper analysis of the results showed that the linear programming relaxation of the problem is weak. Note that preliminary experiments (see Section 3 in the online supplement) show that classical improvement techniques of the lot-sizing model such as the facility location-based formulation [START_REF] Krarup | Plant location, set covering and economic lot size: An 0 (mn)-algorithm for structured problems[END_REF] did not provide better results. Therefore, while such reformulation were applied with some success in a related problem [START_REF] Attila | Robust formulations for economic lot-sizing problem with remanufacturing[END_REF], they do not apply to our study.

RCR is slightly slower than the deterministic problem (314 s on average versus 215 for DET ). However, this approach remains practical because the solver can quickly find good solutions, and it only requires time to close the gap. Indeed, Table 1 shows that RCR returns a solution with an integrality gap below 10% on average for all instance sizes. On the contrary, RC performs poorly because it does not converge even for small instances with an integrality gap of 5 . 88% on average for instances with 21 periods and 10 suppliers. While RC requires few iterations only to converge (around 5 for small size instances), solving the master problem requires too much computation time, and RC cannot perform enough iterations to converge within the given time limit. The algorithmic improvement from [START_REF] Mcdaniel | A modified benders' partitioning algorithm for mixed integer programming[END_REF] significantly reduces the number of iterations (from approximately 30 to 5 for small instances) required to converge. Reducing the time required to solve the master problem is complex. Not only, the reformulations commonly used in lot-sizing do not apply directly to the cases with multiple lead time scenarios, but they are not necessarily efficient for the case with supplier selection. For instance, Table 2 in the appendix shows that the aggregated formulation is not efficient. Therefore, we propose to solve the master problem with a fix and optimize heuristic embedded in the row and column generation framework.

Performance of the methods

This section compares the quality of the solution obtained by the proposed methods. The main document presents aggregated results only for the sake of brevity; the detailed results are available in the online supplement. In this section, we compare the worst-case total cost F (Q m ) associated with the production quantities Q m returned by each method m . F (Q m ) includes the setup costs, the variable production costs, and the worst-case inventory and backlogging costs computed by solving the linear programming model ( 17) -( 22) . We indicate the percentage Gap between the cost F (Q m ) obtained with a method m and the smallest worstcase total cost F (Q ) obtained with any method. More precisely, Gap is computed as follows:

Gap = 100 F (Q m ) -F (Q ) F (Q ) ( 42
)
For each method, Table 2 gives the average Gap over all instances with a given number of periods and a given number of suppliers, and the best average Gap is indicated in boldface. First, Table 2 shows that RC significantly outperforms RC -NW with an average Gap of 8 . 84% and 28 . 95% , respectively. Clearly, the fast-cut generation accelerates the solution process because it quickly generates interesting scenarios. Second, each step of F AO helps to improve the solution because F AO significantly outperformed F AO 2 (0.04% vs 2.11%), and F AO 2 outperforms F AO 1 ( 2 . 11% vs 3 . 76% ). Third, RCR performs relatively well with a Gap of 2 . 28% . However, the constraint decomposition leads to overly conservative solutions, and this conservatism impacts both the setup and quantity decisions. H -RCR -RC considers the setup decisions obtained with RCR , and it finds the optimal production quantities associated with these setup decisions. As H -RCR -RC does not lead to the overall optimal solution (it has a positive Gap), the setup decisions from RCR are sub-optimal, In addition, as H -RCR -RC outperforms RCR , it is able to improve the quantity decision, and RCR also finds sub-optimal quantities. Nevertheless, the impact of this conservatism on the setup decisions is relatively small because H -RCR -RC performs very well with a Gap of 1 . 53% . Fourth, GA performs poorly, with an average Gap of 32 . 98% . While GA is commonly used to deal with lead time uncertainty [START_REF] Ben-Ammar | A hybrid genetic algorithm for a multilevel assembly replenishment planning problem with stochastic lead times[END_REF]; it is not adapted for the hybridization with the MILP solver. Indeed, GA is unable to perform enough iterations in the 600 s time limit because the evaluation of a solution by solving the linear program takes too much time. Finally, F AO leads to the best result, with an average Gap of 0 . 04% . Our results show that the deterministic model should account for the maximum lead time value, since DET Max outperforms DET A v g and DET Min . This result was expected because the backlogging costs are larger than the inventory holding costs. Nevertheless, the consideration of the uncertainty in the optimization model leads to significantly better results, with a Gap of 0 . 04% for F AO versus 6 . 69% for DET Max .

Table 3 provides the average Gap over the instances with identical values for 1 , 2 , and 3 . The results indicate that F AO is robust since it performs well for all values of 1 , 2 , and 3 . On the other hand, Table 3 shows that H -RCR -RC and RCR perform better when the uncertainty set is not too tight. For instance, the average Gap of H -RCR -RC increases from 1.05 to 2.8 when 2 decreases from 20 to 10. Such behavior is expected as the robust counterpart reformulation leads to over conservative solutions.

Table 4 provides the average Gap over the instances generated with an identical Time Between Orders ( T BO ). It shows that the instances with small T BO values are harder to solve. For example, the GAP of RC reduces from 16 . 98% to 12 . 76% when the T BO increases from 4 to 10. When the T BO is large, the plan has fewer orders.

As a consequence, the uncertainty sets become more conservative (it relies on the number of orders), and there are fewer scenarios to consider. The setup decisions not only make robust optimization methods more difficult to solve, but also impact the parameterization of the uncertainty set. This observation calls for more research on robust optimization approaches for lot-sizing problems with setups.

Finally, to study the stability of the proposed approach, Table 5 presents the maximum Gap obtained by each method for each instance size. F AO is the best method, since it leads to the smallest maximum Gap on all instance sizes.

Discussion about ending backlog level

To investigate the impact of considering the restriction that no backlog is allowed at the end of the time horizon, we provide additional experimental results by comparing different constraints. The three experiments (cases) that were run are the following. In Case a , Constraint (7) is used. In Case b , this constraint is replaced by Constraint (6) . Finally, Case c does not contain any of the two constraints.

The numerical experiments show that solving Case b takes on average 13.80 s of CPU time, and this is about three times faster than Case a (41.02 s) and two times faster than Case c (24.47 s). In Cases b and c , all decision variables are considered for t = 1 , . . . , |T | -L max . The solver solves Case b faster because it exploits Constraint (6) to reduce the search space. In terms of total costs, there is no noticeable difference. In Case c , under certain condi-tions, the buyer does not order enough to fulfill the demand over the planning horizon. This happens when the backlogging and inventory holding costs are relatively small. In Case c , for some instance, up to 4% of the total demand was not satisfied (703 instead of 732 units).

Managerial insights

This section provides certain managerial insights related to supplier diversification, order splitting, and link with suppliers' lead times and prices, based on the instances presented in Section 2.2 in the online supplement. Supplier diversification in an uncertain environment is a topic that has been presented in the literature (for example, [START_REF] Anupindi | Diversification under supply uncertainty[END_REF]. However, we do not find any study that analyzes the level of diversification with respect to the risk aversion of buyers. To the best of our knowledge, the only study related to this topic is from [START_REF] Adelman | Supply disruption with a risk-averse buyer[END_REF] , who analyze the quantities that should be ordered from two unreliable suppliers when the buyer is risk-averse or risk-neutral.

Fig. 1 (a) shows the selection rate of each supplier when 3 is varied from 0 to M . M is a very large number set at 10 5 in the experiments. Large values of 3 correspond to a more risk-averse buyer because the resulting solution "covers" a larger set of possible disruptions. We include the case with 3 = 0 to show that in the case without uncertainty, the buyer will order only from the supplier who has the best compromise between its unit purchasing price and its setup cost. Risk aversion is proportional to the value of 3 , where the most risk-averse buyer is assigned the value of 3 = M. We notice that the number of suppliers first increases as 3 increases and then drops slowly until it reaches 1 supplier for the extreme values of 3 ≥ 7 . An extremely risk-averse (large 3 ) buyer orders only from the most reliable supplier (supplier 2 in this case) because he/she considers that any order placed will be delivered as late as possible. When the buyer is less risk-averse, he/she will rely on the cheapest suppliers (Suppliers 2, 4, and 5). Risk aversion will push the buyer to include more suppliers to mitigate risks. Diversification is a well-known tool to mitigate risk and is useful in the case of market-responsive supply chains [START_REF] Chopra | Supply chain management: Strategy, planning and operation[END_REF]. This is further supported by Fig. 1 (b), which shows the number of orders as a function of the value of 3 . As expected, the number of orders and source diversification increases as 3 increases from 1 to 3. For larger values of 3 , the number of orders decreases and stabilizes at 6 orders for 3 ≥ 10 . Another very important observation from Fig. 1 (b) is the fact that the number of orders can exceed the number of periods with a positive demand over the horizon. This means that order splitting becomes interesting in the case of lead time uncertainty, and it is impacted by the profile of the buyer. Note that the optimal solution in the deterministic case ( 3 = 0 ) does not require any order splitting [START_REF] Toledo | Lot-sizing problem with several production centers[END_REF]. We carried out six more experiments to understand the behavior of the buyer in terms of diversification of suppliers as a function of the buyer's risk aversion ( 3 ), lead time value, lead time variability, and prices of the suppliers. Experiment #1 consists in decreasing the maximum lead time of each supplier. Its results are presented in the matrix of charts in Fig. 2. Each chart shows the selection rates ( SR s ) of each supplier s when the maximum lead time ( L s max ) of one supplier varies. In each row, the lead time of a single supplier is changed (for suppliers s = 1, . . . , 5 ), and each column of Fig. 2 corresponds to a different level of risk aversion of the buyer through the value of 3 = 2, 5, and M. In the upper left corner chart (s = 1 and 3 = 2 ), for example, the maximum lead time of supplier 1 ( L max 1 ) is varied from 0 ( L min 1 ) to its default value of 7 time periods, while the lead times of the other suppliers are set to their default values ( L max s = 3 , 5 , 7 , 9 , for s = 2 , . . . , 5 ). This chart suggests that supplier 1 is selected only if his/her maximum lead time is reduced to zero with a selection probability of approximately 22%. In the next figure to the right ( s = 1 , 3 = 5 ), where the buyer is more risk-averse, again supplier 1 is selected only if its L max is set to zero, but with a selection rate of approximately 33%. Note that supplier 1 has the highest selling price, which explains the extra effort s on lead times he/she has to make to be selected.

Fig. 2 shows that the diversification of suppliers depends on risk aversion, as discussed before, and also that it depends on supplier lead times. Diversification can even lead to the choice of very expensive suppliers if their lead times are low in variability and magnitude. For a given level of risk aversion of the buyer, Fig. 2 also indicates at which lead time level it becomes more interesting to target a single supplier. For example, in the case of supplier 2 with 3 = 5 (second row and second column) supplier 2 is selected even when the buyer is not extremely risk-averse and the lead time of supplier 2 is not at its minimum value. Note that while supplier 2 is not the cheapest in terms of the selling price, it shows a good balance between price and lead time. However, this experiment and Fig. 2 might simply indicate that the only reason for increasing the selection is rate is actually the variability and not the magnitude of the lead time.

To check the impact of variability alone, Experiment #2 was run. It consists in reducing the variability (the range of values for the lead time) while keeping the same average (default) lead time. The results are shown in Fig. 3 . For example, the aver- = 4 ). This selection rate becomes even higher when 3 increases.

To further confirm the above findings, the following experiments were run. Experiment #3 consists in increasing the minimum lead time of each supplier. Experiment #4 keeps the same level of variability (the same value of L max ). We limit the presentation of these results to supplier 5 on Figs. 4 , 5 , and 6 , which correspond to experiments #3, #4, and #5, respectively. We notice that increasing L min 5 results in higher selection rate for supplier 5. This looks counter intuitive though it confirms the previous finding related to the importance of variability. As L min 5 increases it gets closer to L max 5 which reduces the lead time variability of supplier 5. Fig. 5 shows that when both L min 5 and L max 5 are decreased simultaneously (keeping a constant variability for s = 5 ), the selection rate of supplier 5 does not necessarily increase. Fig. 6 further confirms this. It can be seen that selection rate of supplier 5 (very small here) does not change when both L min 5 and L max 5 decrease while all suppliers have the same level of lead time variability.

Figure 7 provides further managerial insights. This figure is similar to Fig. 2 , but each chart illustrates the impact of reducing the selling price of a given supplier from its default value down to 30% of its value. For example, the default selling price of supplier 1 on the upper-left corner chart is $1.9 and we show the selection rate of each of the five suppliers if supplier 1 reduces its selling price down to $0.57 with steps of 10%. Fig. 7 shows that the most riskaverse buyer 3 = M (third column of charts) will mostly choose supplier 2 because of its lead time reliability.

Conclusion

This study contributes to integrating production planning and sourcing decisions under lead-time uncertainty and is the first to investigate robust optimization for supplier selection decisions under these considerations. The objectives of this study were to develop solution approaches to this problem and to provide managerial insights.

We formulated a robust optimization model, which was solved using a row and column generation algorithm and three heuristic approaches (a fix-and-optimize, a genetic algorithm, and a hybrid robust counterpart). First, numerical experiments showed that the problem is difficult to solve. The commercial MILP solver that was used to solve the robust counterpart gave an average integrality gap of 17% even with instances of 21 time periods and 10 suppliers. Among all the presented approaches, two were particularly efficient: the row and column generation approach applied to the hybrid robust counterpart formulation ( H -RCR -RC ), and the fix-and-optimize heuristic. These two approaches obtained the best solutions in most cases, although the fix-and-optimize heuristic outperformed the H -RCR -RC heuristic on average.

From a managerial point of view, if there is no uncertainty, a buyer selects only one supplier with a lower total cost (fixed and variable). On the contrary, if there is uncertainty, diversification takes place. This is a well-known result in the literature. However, we show that the number of selected suppliers (level of diversification) depends on the buyer's risk aversion. A buyer with low-risk aversion will select a limited number of suppliers. As risk aversion increases, the buyer orders from a larger number of suppliers. However, with extremely risk averse buyers, the number of selected suppliers decreases until it reaches one supplier, namely the most reliable one, even if it has the highest costs.

Despite the interesting results we obtained in this paper, it can be improved and extended in different directions to consider more generic environments. For instance, interesting and useful extensions could consider uncertainties on the supplied quantities and the demand levels. Another direction of research could be to solve multi-item problems with or without supplier capacities. Such problems are computationally more challenging. Thus, more efficient solution approaches could be developed. Finally, recent works on robust optimization for inventory management under demand uncertainty have shown adjustable recourse variables leads to less conservative solutions ( Yanıko glu, Gorissen, & den Hertog, 2019 ), and this approach may be investigated for lead-time uncertainty.

Supplementary Materials to Robust Optimization Approaches for Purchase Planning with Supplier Selection under Lead Time Uncertainty

This online supplement provides algorithmic details, additional experiments, and detailed results.

Section 1 provides the detailed step of the dualization for the robust counterpart reformulation and the pseudo-code of the fix-and-optimize approach. Section 2 gives the data generation approach.

Section 3 reports the computational performance of the aggregated formulation for the deterministic model. Section 4 gives the detailed results of our experiments. Finally, Section 5 analyses the quality of the robust counterpart reformulation depending on the setup values.

Algorithmic details

Duals of the worst case reformulation of each constraints

The dual of problem ( 33) -(39) in the main document is:

min ρ 1 t (Γ 1 -|S |) + ρ 2 t (Γ 2 -∑ s∈S ∑ τ≤t-L min s 1) + ρ 3 t (Γ 3 -∑ s∈S ∑ τ≤t-L min s (t -τ -L min s + 1)) + ∑ s∈S t-L max s ∑ τ=1 -ξ τts + ∑ τ≤t ψ τts (1) s.t. ψ τts -ρ 2 t -(t -τ -L min s + 1)ρ 3 t ≥ hQ τs t -L max s < τ < t -L min s s ∈ S (2) ψ τts -ρ 1 t -ρ 2 t -(t -τ -L min s + 1)ρ 3 t ≥ hQ τs τ = t -L min s s ∈ S (3) ψ τts + λ τts ≥ hQ τs τ > t -L min s s ∈ S (4) ψ τts -ξ τts ≥ hQ τs τ ≤ t -L max s s ∈ S (5) ψ τts , ξ τts , ρ 1 t , ρ 2 t , ρ 3 t ≥ 0 τ ≤ t -L max s s ∈ S (6)
For the backorder constraint, the dual is identical but h is replaced by -b.

Preprint submitted to European Journal of Operational Research June 1, 2022

min ρ ′1 t (Γ -|S |) + ρ ′2 t (Γ 2 -∑ s∈S ∑ τ≤t-L min s 1) + ρ ′3 t (Γ 3 -∑ s∈S ∑ τ≤t-L min s (t -τ -L min s + 1)) + ∑ s∈S t-L max s ∑ τ=1 -ξ τts + ∑ τ≤t ψ τts (7) s.t. ψ ′ τts -ρ ′ 2 t -(t -τ -L min s )ρ ′ 3 t ≥ -bQ τs t -L max s < τ < t -L min s s ∈ S (8) ψ ′ τts -ρ ′ 1 t -ρ ′ 2 t -(t -τ -L min s )ρ ′ 3 t ≥ -bQ τs τ = t -L min s s ∈ S (9)
ψ τts + λ τts ≥ -bQ τs τ > t -L min s s ∈ S (10) ψ ′ τts -ξ ′ τts ≥ -bQ τs τ ≤ t -L max s s ∈ S (11) ψ ′ τts ξ ′ τts , ρ ′ 1 t , ρ ′ 2 t , ρ ′ 3 t ≥ 0 τ ≤ t -L max s s ∈ S (12)
1.2. Pseudo code of fix-and-optimize in the row and column generation framework Algorithm 1: Fix and optimize in the row and column generation framework Input: An initial setup matrix Y T S

1 Generate an initial set of scenarios: Fix the setup values in model ( 23)-( 28) in the main document to Y T S , and run the row and column generation method to generate a set of scenarios and the optimal quantities Q ⋆ T S associated with the initial setups. ;

2 Set the current setup value ȲT S to Y T S ;

3 while A stopping condition is not met do 4

Fix the setup values in model ( 23)-( 28) to ȲT S , but open a subset of the setup variables ;

5 Solve the resulting model to get the purchasing plan QT S with setups Y ′ T S . ;

6 Compute the cost f ( QT S ) for the worst-case scenario ω with model ( 9)-( 14)in the main document ; To generate relevant data and avoid instances with trivial solutions where the same supplier is always selected, we only accept instances where no supplier dominates all others (see Definition 1).

7 if f ( QT S ) < f (Q ⋆ T S )
For the genetic algorithm (see section 4.5), the following parameters were empirically chosen after preliminary tests: (i) a population of size 120 chromosomes; (ii) a cross-over probability x 1 = 0.9, and (iii) mutation probabilities for each gene of m 1 = 0.02, m 2 = 0.001, m 3 = 0.001, and m 4 = 0.018. The stopping criteria were 10000 iterations or 10 minutes.

Data for managerial insights

For managerial insights, one single instance with |S | = 5 and |T | = 21 was arbitrarily chosen from previously-described datasets and considered as the reference case (see Table 1). Then, 100 instances were obtained by varying the demand values in the range [0,200] in each time period.

Managerial insights are drawn by varying the instance characteristics in this reference case. To analyze decisions based on lead time variability, we decrease the value of L max s for each supplier one unit at a time from default L max s until default L min s . For example, for supplier 1, we consider eight instances with the following lead time range: [0, 0], [0, 1], ..., [0,7]. To analyze the impact of suppliers' discounts, we reduce the default purchasing cost by 5%, 10%, ..., 70% (with a step of 5% each time). Hence, we generate instances with p s = 0.95 × p s , ..., 0.5 × ((default)p s ). To analyze the impact of inventory, back-ordering, and fixed ordering costs, we generated instances where these costs are multiplied by 2 or 4. Finally, to analyze the impact of the buyer's risk aversion, Γ 3 was varied in {0, . . . , 10, M}, where M is a very large value (set to 10 5 in our experiments). Γ 1 and Γ 2 were set to M in this experiment.

Aggregated formulation for the deterministic problem

Table 2 shows that the aggregated formulation is not efficient for the production planning problem with supplier selection since the classical formulation is on average twice as fast to solve.

Detailed Results

Tables 3, 4, 5 and 6 provide the average gaps (as defined in the main document) of DET , RC, RCR, H -RCR-RC, FAO, and GA for each instance. As described in the main document, each instance has a single restrictive budget (Γ 1 , Γ 2 , or Γ 3 ), and the others are set to a large enough value (indicated with a "-" in Tables 3,4, 5, and 6). show that the quality of the robust counterpart approximation (when compared to the exact row and column generation approach) decreases when setup costs increase. On the contrary, our results suggest that the robust counterpart approximation provides good decisions for the setups. Therefore, in this section, we further analyze the impact of the setup costs on the solution resulting from RC and RCR for the LSP under lead time uncertainty. We perform a similar experiment to Rodrigues et al.

(2021) with similar instances. More precisely, we generate ten instances with a single supplier. The demand is randomly generated in [0, 50], the unit production cost is set to 1, the holding cost is set to 4, the backlog cost is set to 6. The minimum lead time is set to 1 and the maximum to 5. To avoid generating an initial inventory, we set the demand to 0 during the first 5 periods.

Figure 1 and 2 provide the total cost (evaluated with the rows and columns generation framework) and the number of setups depending on the setup cost. These figures show that the difference between the total costs of the two methods remains stable when the setup costs increase. However, RCR provides solutions with more setups, and the difference between the number of setups resulting from the two methods decreases when the setup cost increases. RCR tends to place the orders to meet the demand in each period independently to minimize the inventory and backlog cost. In other words, RCR seeks to balance the worst-case inventory with the worst-case backlog in each period, and it leads to frequent orders when the setup costs are small. On the contrary, in the adversarial approach, as the lead time is unknown, an order does not correspond to a specific demand. The order placed in a period t will meet the demand between in the interval [t + L min ,t + L max ] depending on the worst-case scenario. In this case, it is convenient to aggregate the demand between several

  dropped from the objective. The resulting model is given below (the dual variables are shown between parentheses).

  max

  as a matrix of binary values whose dimensions are |S| × |T |. Each gene of a chromosome contains the value of Y ts . The proposed GA starts with an initial population of N individuals that are randomly generated. The sum of Y ts , denoted by G , is the number of orders. G is randomly generated in the interval T s / ( D h ) is an estimate of the minimum time between two orders computed based on the EOQ formula without backlog given in (41) and g 2 = max s ∈S

)

  ) where the lead time is set to the minimum ( L min s

Fig. 1 .

 1 Fig. 1. Supplier selection rates and number of suppliers selected as a function of 3 .

Fig. 2 .

 2 Fig. 2. Supplier selection rates for Experiment #1: Decreasing the maximum lead time of each supplier.

Fig. 3 .

 3 Fig. 3. Supplier selection rates for Experiment #2: Reducing variability while keeping the same average lead time.

Fig. 4 .

 4 Fig. 4. Suppliers' selection rates as function of lead time (by increasing the minimal lead times) (Experiment #3).

Fig. 5 .

 5 Fig. 5. Supplier selection rates for Experiment #4: For all suppliers, setting the same costs and the same lead time variability ( L max s -L min s is constant), and simultaneously increasing both L min s and L max s for each supplier individually.

Fig. 6 .

 6 Fig. 6. Supplier selection rates for Experiment #5: Similar to Experiment #4 but setting the same variability for all other suppliers.

Fig. 7 .

 7 Fig. 7. Supplier selection rates Experiment #2: SR s vs the purchasing prices.

  age lead time of supplier s = 1 is equal to (L max 1 -L min 1 ) / 2= 3.5 time periods and the lead time range is (L max 1 amount. It is clear from these figures that suppliers with low lead time variability are more likely to be selected. In the fifth row, for example, supplier5 s selection rate increases considerably and is the only one which is selected when L

  we increase both values of L max s and L min s one period at a time. Experiment #5 is similar to the previous one, but all suppliers have the same variability (the same value of L max s -L min s ) but not necessarily the same values of L min s and L max s

For

  each supplier, the purchasing cost was drawn from a uniform distribution in [5, 20]. To generate fixed ordering costs, we set the time between orders (TBO) to different values as follows: For instances with |T | = 21, TBO was set to 4 periods. For instances with |T | = 41 and |T | = 61, TBO was set to 4, 10, and 20 periods. Hence for a TBO of 2, 4, 10, and 20, ordering costs o s are randomly generated in the intervals [12, 14], [38, 58], [240, 360], and [960, 1440], respectively. Each supplier s can deliver a lead time within [L min s , L max s ], where L min s = [max(0, L -L -)] and L max s = L + L + . The values of L, L -, and L + are randomly drawn from sets {2, 4, 6}, {1, 3, 5}, and {1, 3, 5}, respectively.

5.

  Impact of the setup costs on the quality of the robust counterpart approximation Rodrigues et al. (2021) consider the lot-sizing problem under demand uncertainty, and they

Figure 1 :

 1 Figure 1: Number of setups in the solution obtained with Exact, RCR, and Det Min depending on the setup costs

Figure 2 :

 2 Figure 2: Worst case cost for the solution obtained with Exact, RCR, and Det Min depending on the setup costs.

Table 1

 1 Solution gaps and computational time for the column and row generation approach and robust counterpart reformulation.

		RC					RC -NW				RCR		DET Max
	|T | |S|	Gap RC (%) CPU (s) Nr it CPU Sub. (s) CPU Mas. (s) Gap RC (%) CPU (s) Nr it	CPU Sub. (s) CPU Mas. (s) Gap Int (%) CPU (s) Gap Int (%) CPU (s)
	21 5	0.81	84.99	5.33 0.32	84.66	26.58	518.22 30.89 1.05	517.14	0	2.58	0	1.18
	10	5.88	264.32 5.11 0.43	263.88	41.51	594.51 24.39 1.47	593	0	17.16	0	2.22
	15	9.98	251.26 4.39 0.5	250.75	64.44	597.01 21.72 1.74	595.21	0	15.14	0	3.17
	41 5	6.21	487.51 2.2	0.2	487.3	48.8	502.66 6.77	0.52	502.12	1.29	294.37 0.13	126.41
	10	14.73	490.17 1.53 0.3	489.86	76.09	501.81 6.37	0.94	500.83	2.9	407.87 0.01	62.48
	15	12.88	503.57 1.87 0.93	502.63	76.72	529.31 5.07	1.05	528.22	2.16	363.06 0.25	153.77
	61 5	7.56	591.73 2.2	0.47	591.24	98.91	601.79 2.53	0.38	601.4	2.73	525.27 0.73	482.46
	10	14.93	601.13 1.07 0.5	600.62	119.36	601.65 1.5	0.47	601.16	5.39	600.2	0.83	502.42
	15	20.39	603.33 1	2.03	601.27	128.78	600.65 1	0.6	600.02	8	600.34 3.02	600.58
	Average 10.37	430.89 2.74 0.63	430.25	75.69	560.85 11.14 0.91	559.9	2.5	314	0.55	214.97

Table 2

 2 Gap from best solution for each approach depending on the number of suppliers and number of periods (maximum CPU time equals to 600 s).

	|T |	|S|	DET Min	DET Max	DET A v g	RC	RC -NW	RCR	H -RCR -RC	F AO	F AO 1	F AO 2	GA
	21 5	53.77	11.20	41.29	0.70	17.38	3.23	1.63	0.02	3.27	3.23	32.50
		10	53.41	10.44	40.85	4.05	24.73	2.74	1.24	0.06	4.32	2.74	29.61
		15	56.63	12.39	45.00	6.32	33.65	3.15	1.12	0.04	5.15	3.13	55.3
	41 5	33.75	3.67	20.65	5.06	22.24	1.51	3.54	0	2.69	1.42	19.98
		10	38.86	5.25	26.18	10.42	30.96	1.90	0.94	0.06	3.14	1.74	27.48
		15	36.48	4.72	22.40	10.36	29.67	1.54	0.70	0.02	3.52	1.39	33.03
	61 5	32.41	2.86	21.98	5.94	32.24	2.03	2.82	0.01	3.36	1.86	26.44
		10	34.77	5.01	22.72	11.60	33.25	2.05	0.79	0.03	4.53	1.76	35.78
		15	38.07	4.71	24.99	25.08	36.47	2.38	0.95	0.08	3.90	1.71	36.69
	Average	40.08	5.98	27.59	9.63	29.52	2.16	1.56	0.04	3.69	1.97	32.03

Table 3

 3 Gap from best solution for each approach depending on the uncertainty set.

	1	2	3	DET Min	DET Max	DET A v g	RC	RC -NW	RCR	H -RCR -RC	F AO	F AO 1	F AO 2	GA
	2	-	-	49.97	4.63	34.82	7.40	39.74	1.81	1.04	0.03	3.63	1.79	31.00
	4	-	-	49.96	4.61	34.81	7.36	37.61	1.73	1.00	0.06	3.57	1.70	31.41
	-	10	-	46.14	4.68	32.60	13.55	34.61	2.04	2.80	0.02	3.73	1.77	31.65
	-	20	-	49.67	4.64	34.82	9.92	39.28	1.83	1.05	0.02	3.69	1.75	31.77
	-	-	10	16.65	9.88	10.61	6.75	7.60	2.99	1.60	0.07	3.64	2.51	33.78
	-	-	20	28.10	7.43	17.89	12.79	18.30	2.58	1.84	0.02	3.87	2.27	32.59
		Average		40.08	5.98	27.59	9.63	29.52	2.16	1.56	0.04	3.69	1.97	32.03

Table 4

 4 Gap from best solution for each approach depending on the T BO .

	T BO	DET Min	DET Max	DET A v g	RC	RC -NW	RCR	H -RCR -RC	F AO	F AO 1	F AO 2	GA
	1	50.70	10.53	41.22	6.60	37.60	2.60	1.01	0.07	2.90	2.46	37.22
	2	51.39	10.69	40.67	6.34	37.55	2.72	2.07	0.02	3.08	2.59	42.82
	4	44.58	4.38	28.98	16.98	34.53	2.54	1.58	0.01	4.87	2.05	28.04
	10	22.27	0.31	9.91	12.76	18.12	1.55	2.72	0.07	3.44	1.49	24.26
	20	18.23	0.14	3.12	4.94	9.25	0.74	0.40	0.02	4.29	0.65	21.83
	Average	40.08	5.98	27.59	9.63	29.52	2.16	1.56	0.04	3.69	1.97	32.03

Table 5

 5 Maximum Gap from best solution.

	|T |	|S|	DET Min	DET Max	DET A v g	RC	H -RCR -RC	F AO	GA
	21 5	63.20	20.50	50.26	12.62	2.68	0.19	40.93
		10	61.50	22.46	51.98	31.58	1.78	1.00	51.79
		15	62.13	21.64	52.55	38.41	2.64	0.16	67.14
	41 5	71.52	21.76	57.07	24.44	21.92	0	29.87
		10	71.54	21.58	57.26	37.71	3.22	0.39	47.08
		15	71.93	21.71	56.67	37.66	2.78	0.39	56.18
	61 5	72.74	19.13	57.36	23.14	59.45	0.09	47.77
		10	72.70	22.62	57.57	36.01	2.26	0.38	43.53
		15	72.87	21.83	57.96	86.06	2.78	1.08	56.42
	Average	68.90	21.47	55.41	36.40	11.06	0.41	48.97

  We generate two groups of instances based on the generators presented inThorsen & Yao (2017) andBrahimi & Aouam (2016). The first group contains a large set of instances to analyze the performance of the solution approaches. The second group is designed to generate managerial Time horizons were set to 21, 41, and 61 time periods, where the demand for the first 11 periods is set to zero in each case. As setting the initial inventory is complex, we set the demand of the first 11 periods to zero (i.e., the maximum lead time), so that all suppliers can deliver on time. Demands in periods from t = 12 to t = |T | were drawn from a uniform distribution in[20, 40]. The number of suppliers was set to |S | = 2, 5, and 10. The inventory holding cost was set to 0.2, while the back-ordering cost was equal to 2.4 (12 times the holding cost).

	2. Data generation
	insights.
	2.1. Data for performance analysis
		then
	8	Move there: the current solution ȲT S = Y ′ T S , and record the best known
		production plan Q ⋆ T S ;
	11	end if
	12 end while
		2

9 else 10 Add scenario ω to the set Ω ;

  Table2provides the integrality gap and the computation time required to solve the deterministic problem or the facility location-based reformulation:[DET Ref ] min ∑ Y ts + p s Q ts ) + ∑

					(hI t + bB t )	(13)
					t∈T
	s.t.
	I t -B t	=		d τ t ∈ T	(14)
					τ∈1...t
	q tτs		≤ d τ Y ts	t ∈ T s ∈ S	(15)
	∑	q tτs	= Q ts		t ∈ T s ∈ S	(16)
	τ∈T
	∑	q tτs	= d τ		τ ∈ T s ∈ S	(17)
	t∈T
	∑	∑	Q ts ≥ ∑	d t		(18)
	t∈T	s∈S	t∈T
	Q ts		≥ 0	and	Y ts ∈ {0, 1} t ∈ T s ∈ S	(19)
	q tτs		≥ 0		t ∈ T s ∈ S	(20)
	I t , B t	≥ 0		t ∈ T

t∈T ∑ s∈S (o s t ∑ τ=1 ∑ s∈S δ τts Q τs -∑

Table 1 :

 1 Details of the reference case

	h	b	Supplier 1	2	3	4	5
			o s	12 14 13 14 13
	0.2 1.6	p s L max s L min s	1.9 1.0 1.6 0.8 1.2 7 3 5 7 9 0 1 3 1 0

Table 2 :

 2 Solution gaps and computational time for the classical lot sizing formulation and the aggregated formulation

			DET Max		DET Re f
	|T |	|S |	Gap Int (%)	CPU (s)	Gap Int (%)	CPU (s)
		5	0	1.2	0	6.1
	21	10	0	2.2	0	8.2
		15	0	3.2	0	18.6
		5	0.1	126.4	0.2	570.9
	41	10	0	62.5	0.4	600.3
		15	0.3	153.8	0.3	600.4
		5	0.7	482.5	1	600.4
	61	10	0.8	502.4	0.6	600.7
		15	3	600.6	0.5	601.2
	Average		0.5	215	0.3	400.8

Table 4 :

 4 GAP of DET Min , DET Max , DET Avg , RC, RCR, H-RCR-RC, FAO and GA on instance with 41 time periods

	|T |	|S |	TBO	Γ 1	Γ 2	Γ 3	Min	DET Min	DET Max	DET Avg	RC	RCR	H-RCR-RC	FAO	GA

Acknowledgement

The authors of this paper would like to thank their respective institutions in addition to the Region Pays de la Loire, France (www.paysdelaloire.fr) for their financial support.

Supplementary material

Supplementary material associated with this article can be found, in the online version, at Doi: 10.1016/j.ejor.2022.03