N Benyahia

A Menad

A Zaoui
email: azaoui@polytech-lille.fr

M Ferhat

Crystal phase induced direct band-gap modifications in bulk GaP and GaAsP

Keywords: GaAsP, DFT, structural stability, thermodynamic stability, band structure

Wurtzite III-phosphide GaP and GaAsP compounds have shown tunable direct band-gap making them promising candidates in a variety of future optoelectronic and photonic devices.

We explore here, through DFT their corresponding electronic structure properties of bulk cubic and wurtzite polytypes. It is shown that the calculated weak positive formation enthalpy of GaAsP crystal-phases suggest slight thermodynamical instability. In addition, from accurate quasiparticle (local density approximation-1/2) we predict a direct band-gap for WZ 2H, 4H, and 6H polytypes of GaP and GaAsP. The emitted wavelength can be then tuned across an important range of the visible light yellow-green spectrum for GaP (2.13eV(2H)-2.33eV(4H)) and the visible light red spectrum for GaAsP (1.64eV(6H) to 1.82eV(4H)).

2

III-V semiconductors nanowires (Nws) [START_REF] Lu | [END_REF][2], the emerging of ideal building components of novel nanoscale devices, have recently attracted important attention due to the fascinating fundamental investigations and unprecedented potential technological application that these Nws enable. III-V Nws typically show polytypism that is the intermixing of cubic zinc-blende (ZB) and hexagonal wurtzite (WZ) crystal phases. Indeed, the WZ structure is often absent in bulk nonnitrides III-V compounds; while it can be obtained in NWs. Interestingly, Nws can be easily switched between these phases by varying the temperature and growth conditions.

The resulting change of atomic stacking sequence (i.e., WZ vs ZB crystal phases) impacts considerably the transport and the optical properties, which creates strong opportunities for designing modulate nanowire structures with new electronic properties, and to extend band structure engineering.

Of particular interest is gallium phosphide (GaP) with an indirect gap of 2.3eV, in spite of the fact that GaP has the smallest lattice mismatch to Si, and it is therefore one of the best candidates for integration of optoelectronic and photonic based on III-V materials. However cubic-GaP has indirect band gap, which results in a low radiative efficiency and requires a relatively large absorption depth.

Recently, GaP nanowire with WZ structure has been successfully grown by vapor-liquid-solid (VLS) mechanism [3][4][5][6], Au chemical beam epitaxy (CBE) [7], and molecular-beam epitaxy (MBE) [8]. Photoluminescence excitation spectroscopy (PLE) demonstrates the conversion of the indirect nature of the band-gap of bulk-ZB-GaP to a NWs-WZ direct band-gap of 2.09-2.11eV [4] and ∼ 2.19eV [6]; whereas resonance Raman (RR) spectroscopy measurements give a higher direct band-gap of 2.47eV [7]. In addition, it was demonstrated experimentally that by the incorporation of arsenic (As) in GaP Nws, the emitted wavelength is tuned across an important range of the visible light spectrum [9], since its band-gap can be tuned from the near-infrared (Eg = 1.42eV, λ = 873.12 nm) to visible region (Eg = 2.3eV, λ = 539.06nm). Moreover, GaAsP NWs systems have great potential for light emitting diodes, optoelectronic and photovoltaics applications.

In view of the above, and despite the numerous above-mentioned advantages of GaP, many questions remain unaddressed regarding the doping effects of As on the electronic-structure properties of WZ GaP. Knowledge on the material properties of the bulk phase of GaAs/GaP materials is the first step towards the optimization of device performances and the design of new Nws-based devices. Moreover, the knowledge about the electronic structure properties of WZ-GaAsP systems is quite limited in the literature.

Herein, we explore the structure, and electronic properties of cubic and wurtzite 2H, 4H and 6H bulk form of GaAs/GaP systems by applying the state-of-the-art first-principles pseudopotential calculations.

Calculations have been performed within the framework of the density functional theory (DFT) [10], as implemented in the ab initio plane-wave pseudopotential Quantum ESPRESSO code [11]. The projector-augmented wave pseudopotential (PAW) [12] was used to represent the ion-electron interaction. The local density approximation (LDA) [13] is used to describe the exchange and correlation potentials. Single-particle Kohn-Sham wave function was extended using the plane wave with cutoff energy of 60Ry along a cutoff of 500Ry for the augmentation charges. A convergence test was done before handling the main parts of the work. It confirms the value used is widely enough to ensure the convergence. For GaAsP systems we used cubic supercell of GaP (8 atoms), and WZ supercells of GaP 2H (8 atoms), 4H(8 atoms) and 6H (24 atoms) by replacing one As atom with one P atom. A Monkhorst-Pack [MP] [14] k-points sampling of: 4×4×4(cubic), 4×4×3(2H), 4×4×2(4H), and 4×4×2(6H) were employed to sample the Brillouin zone. A convergence test was achieved in order to confirm the number of k-points necessary to accomplish each study. These settings ensure energy convergence within 10 -4 eV/cell. Atomic degrees of freedom are relaxed until the maximum forces on all atoms had fallen below 10 -5 eV/Å. The energy equilibrium structural parameters of the 3C(ZB-phase), 2H, 4H and 6H polytypes of GaP, GaAs and the cubic, 2H, 4H and 6H polytypes of GaAsP systems are obtained by minimizing the total energy with respect to the lattice constants (a, and c) and the structural parameter u. The minimum of the total energy E=E(a,c) (Fig. 1, for GaAsP systems) is then derived for the equilibrium aeq, ceq together with the corresponding internal-cell parameters.

For the cubic phase (GaAsP) and 3C (GaP and GaAs) phase only the lattice constant a has to be optimized.

The results of the structural optimization for GaAs, GaP and GaAsP compounds are given in Table I for the four polytypes. The polytypes are ordered according to their hexagonality H defined as the fraction of the number of the hexagonal bilayers to the total number of bilayers per unit cell: =

where h and c are the number of hexagonal and cubic stacking respectively. Between the most extreme polytype 2H with H=100 % and 3C (Only for GaP and GaAs) with H=0, one finds the intermediate hexagonal polytypes 4H (H=50%) and 6H (H=33 %).

Experimental data of the structure properties of WZ polytypes of GaP and GaAs are generally not available. However, recently, structural characterization of WZ GaP and GaAs Nws was obtained [15]. The present calculated equilibrium lattice parameters a and c of 2H-GaP are in excellent agreement with X-ray diffraction data [15], the deviation do not exceed ∼ 1% for a and ∼ 0.1% for c. Moreover, the X-ray diffraction measurements [16] of the ratio interplanar spacing ~1.60 of GaAs nanowires agree perfectly with our calculated value of 1.60.

The c/a ratio increases with increasing hexagonality H, for GaP, GaAs and GaAsP systems, which corresponds to an increasing deformation of the bonding tetrahedra that are stretched along the c axis. The lattice constant a decreases with rising hexagonality and exhibits a minimum for 4H polytype only for GaAsP systems. In contrast, the bulk modulus of GaP, GaAs and GaAsP materials show a very weak dependence on the polytype.

The physical properties as indicator of the possibility of synthesis of GaAsP systems is the formation energy ∆H, which describes the energy required to from the GaP-GaAs systems with respect to the ZB binary GaP and GaAs. The calculated ∆H for the cubic and WZ 6H, 4H and 2H polytypes are respectively 8.54meV/pair, 35.87meV/pair, 46.22 meV/pair and 95.06 meV/pair. The calculated enthalpy of formation for the four phases is in the order:

E(2H) > E(4H) > E(6H) > E(cubic).
The WZ polytypes are found energetically less stable than the cubic crystal. In all cases we found ∆H > 0, which suggests phase separation into the binary GaAs and GaP. However, ∆H is found extremely small, suggesting that the GaAsP crystals are thermodynamically slightly unstable.

To gain better insight into the physical factors controlling ∆H, we decompose the total formation energy ∆H = ∆H (Chem) + ∆H (Elast) into 'chemical' (Chem) and 'elastic' (Elast) parts. For the cubic crystal for example, the calculated ∆H (Chem) and ∆H (Elast) are respectively 7.64meV/pair and 0.90 meV/pair. The calculated ∆H (Chem) and ∆H (Elast)

show that chemical energy part is the main contribution to ∆H. Moreover, the excessively small ∆H (Chem) and ∆H (Elast) can be correlated to the small lattice parameter mismatch ( ∆ ~4%) between the binary GaAs and GaP and with the low electronegativity mismatch between As and P (i.e., χ(P)-χ(As) ∼0.01 within the Pauling scale [17]).

Indeed, various GaAsP Nws have been successfully synthesized recently. Cubic Nws have been synthesized by molecular beam epitaxy (MBE) [18], WZ-Nws of GaAsP compounds were grown by Aerotaxy technique [19], by MBE [20][21][22], by Au-assisted vapor-liquid-solid (VLS) [3] growth mode, and by vapor transport method [23].

The four studied cubic-wurtzite polytypes of GaAs/GaP systems considered here can be reasonably described by one-dimensional Ising-type model, more precisely the axial nextnearest-neighbor Ising (ANNNI) model [24]. Within the ANNNI model we can compute the parameters Ji, which describe the interaction energy between neighbor layers. We restrict the Ji up to the third-neighbor bilayers (i.e., J1, J2, and J3). The ANNNI Ji parameters have been computed according to Ref. [25] as:

= ∆ (2 ) 2 + ∆ (4 ) 2 -3 ∆ (6 ) 4 = - ∆ (2 ) 4 + ∆ (4 ) 2 = - ∆ (4 ) 2 + 3 ∆ (6 ) 4
Where ∆E is the total energy difference of polytype with respect to the cubic phase. The resulting layer-layer interaction energies (meV/pair) are J1=10.40, J2=0.69 and J3=0.41. The nearest-neighbor interaction leads to the dominant parameter J1. The value of J1 has the correct order of magnitude of III-V compounds. The J1 parameter is positive, which correlates with the cubic-wurtzite phase-preference (i.e., J1>0 (J1˂0) favors cubic (wurtzite) crystal).

The second and third-nearest neighbor interaction J2 and J3 are found much smaller than J1, and valid the assumption that the long-range interaction in the polytypes considered here are small.

Important information can also be deduced from the ANNNI model in relation with the twodimensional planar defects that can occur in crystalline materials. Given the layer-layer interaction energies one can estimate the stacking faults (SF) formation energies. The most common stacking faults are the intrinsic stacking fault (ISF), and the extrinsic stacking fault (ESF). The predicted stacking fault energies (per unit area) are γ(ESF)=50.45mJ/m 2 , and γ(ISF)=49mJ/m 2 . The calculated SF energies indicate that both intrinsic and extrinsic stacking faults energies are unstable.

It is well known that very often DFT-GGA seriously underestimates quasiparticles (QP) bandgap energies from the experimental ones of semiconductors and insulators, typically Kohn-Sham gap underestimates excited-states of solids by 50%-100%. Hence, we apply the LDA-1/2 technique [26] which leads to more accurate excited states, and rivals well with the results of the expensive many-body GW quasiparticle approach [27]. The QP self-energy effects are simulated by a hole excitation whose extent is derived by maximizing the fundamental energy gap of ZB GaAs and GaP.

The quasiparticle LDA-1/2 band structures of 3C and WZ polytypes (2H, 4H and 6H) of GaP are displayed in Fig. 2. We found that all WZ GaP-polytypes show a semiconductor character with a direct band gap (Γ→Γ) of 2.33eV, 2.285eV and 2.138eV for 6H, 4H and 2H polytypes respectively; while the cubic phase shows indirect band-gap of ∼2.39 eV at X point. The calculated 2H band gap of GaP is in excellent agreement with the measured values of 2.09-2.11eV [4] and 2.19eV [6]. Whereas the directness nature of the band gap of GaP is found rather independent with WZ-polytypes, the strength of the direct gap is found dependent of the crystal phase that can adopt GaP.

  Fig.5ashows the calculated direct energy gap as function of hexagonality H. Eg exhibits relatively strong dependence versus H, a fit of the curve give a band gap bowing of ∼0.64eV. Our results agree with the screened exchange polytypes are found energetically less stable than in the cubic phase. Moreover, the calculated weak positive formation energy of cubic-WZ polytypes of GaAsP compounds suggests relative weak thermodynamic instability. The results show excellent agreement with the available experimental measurements for structural parameters and band gaps for WZ polytypes of GaP and GaAs. Using the one-dimensional Ising-type (ANNNI) model we have also determined the layer-layer interaction and stacking fault energies of GaAsP materials.Most importantly, QP(LDA-1/2) band structure of WZ GaAsP systems evidence direct band semiconductor behavior with gap energies of 1.64eV(6H), 1.82eV(4H), and 1.7eV(2H), which are promising candidates for light emission across an important range of visible light spectrum.

Figure 1 :

 1 Figure 1: Isoenergies lines of the total energy E(c, a) of crystal phases of GaAsP.

Figure 2 :

 2 Figure 2: Quasiparticle (LDA-1/2) band structures of GaP polytypes.

Figure 3 :

 3 Figure 3: Quasiparticle (LDA-1/2) band structures of GaAs polytypes.

Figure 4 :

 4 Figure 4: Quasiparticle (LDA-1/2) band structures of GaAsP polytypes.

Figure 5 :

 5 Figure 5: Direct band-gap evolution as function of the hexagonality H of: a) GaP, b) GaAsP and c) GaAs.

Table Captions Table I :

 CaptionsI Structural (a, c), and Bulk modulus (B0) of crystal structures for cubic and WZ polytypes (2H, 4H and 6H) of GaAs, GaP and GaAsP. The lattice constants are given referred to the corresponding hexagonal unit cell, i.e., = /√2 and # = /√3. p is the number of bilayers per unit cell p (p=2(2H), p=4(4H), and p=6(6H)).

	Table I
	Material Polytype a(Å) 2c/(Pa) $ % (&'()
	GaAs	2H	3.955 1.649	73.80
		4H	3.962 1.640	73.91
		6H	3.963 1.638	73.93
		3C	3.969 1.633	74.06
	GaP	2H	3.801 1.649	89.45
		4H	3.807 1.641	89.54
		6H	3.809 1.638	89.58
		3C	3.816 1.633	89.78
	GaPAs	2H	3.839 1.650	85.12
		4H	3.845 1.641	85.18
		6H	3.844 1.639	86.62
		Cubic	3.853 1.633	85.6


Xavier Schepler
email: xavier.schepler@gmail.com

André Rossi

Evgeny Gurevsky

Alexandre Dolgui

Solving robust bin-packing problems with a branch-and-price approach

Keywords: Packing, Robustness, Sensitivity analysis, Uncertainty, Stability radius, Relative resiliency, Dantzig-Wolfe decomposition, Column generation, Branch-and-price

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

Introduction

For the standard bin-packing (BP ) problem, one-dimensional items of different sizes have to be assigned to a minimum number of identical one-dimensional bins. The size of each item and the capacity of a bin are assumed to be known in advance. Nevertheless, in real-life applications of BP , the sizes of items often have random deviations from the nominal values. For example, in hospital administration (see [START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF][START_REF] Lamiri | A stochastic model for operating room planning with elective and emergency demand for surgery[END_REF], one of the most important optimization issues which can be modeled as BP problems, is the daily planning of surgeries. The surgery durations are likely to change. A smaller number of operating rooms used per day reduces the cost of dealing with their preparation. The context of BP under uncertainty appears also in the domain of supply-chain management. For example, for the problem of logistics capacity planning (see [START_REF] Crainic | Logistics capacity planning: A stochastic bin packing formulation and a progressive hedging meta-heuristic[END_REF], where it is necessary to predict four to six months in advance the allocation of goods to a minimum number of containers of different capacities. The volumes of delivered goods have random deviations around the planned values. BP models are also used in the design of paced assembly lines. The problem is known in the literature as an assembly balancing problem of type 1 (see [START_REF] Boysen | A classification of assembly line balancing problems[END_REF][START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF], where a given set of production tasks, some involving issues of precedence, has to be assigned to a minimum number of identical workstations.

The so-called cycle time constraint expresses a limit on a station capacity. In the case of non-fully automated lines, there is a subset of manual tasks, whose processing times may vary depending on operator skills and random performances. The assembly line balancing problem of type 1 is a BP problem with precedence constraints. Another case of BP problems under uncertainty is the one dimensional cutting stock problem, as in [START_REF] Alem | On the cutting stock problem under stochastic demand[END_REF], where the demand or item sizes can be uncertain. A robust machine availability problem in a parallel machine environment with uncertain task durations in [START_REF] Song | The robust machine availability problem -bin packing under uncertainty[END_REF] is another example. The latter two articles are discussed in more detail in Section 3, dedicated to the literature review.

Probabilistic models are often used to consider uncertainty. Nevertheless, this approach is not always possible because of the absence of reliable historical data in order to establish adequate probability distributions as, for example, in the case of the initial design of the aforementioned assembly lines. Only a subset of tasks with uncertain processing times can be identified by decision makers at the line design stage. In order to overcome this difficulty, [START_REF] Rossi | Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations[END_REF], motivated by the work of [START_REF] Sotskov | Stability analysis of an optimal balance for an assembly line with fixed cycle time[END_REF], proposed a new approach, based on the stability radius optimization. For any given solution, its stability radius is obtained as the maximal magnitude of variations from their nominal values of the uncertain task times for which the solution feasibility (or optimality) is preserved. In other words, studying the simple assembly line balancing problem with a fixed number of workstations, the authors search for solutions which maximize the stability radius. The well-known norms 1 and ∞ are used to calculate the stability radius. First, the authors show that if the 1 norm is used, then the minimum idle time1 among all the workstations having at least one uncertain task, has to be maximized. Second, they also show that if the ∞ norm is employed, a duration equal to the stability radius, added to the duration of each uncertain task, has to be maximized. Thus, from a managerial point of view, it is necessary to search for a feasible task assignment having the maximal value of the mentioned above indicators, since this leads to the greatest protection against uncertainty.

In this paper, we develop a branch-and-price method applied to the problems, which are inverse to those addressed in [START_REF] Rossi | Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations[END_REF]. By considering a BP problem, therefore excluding precedence constraints, the problem consists of allocating a given set of items to a minimum number of bins so that the stability radius of the solution is not less than a specified threshold, which determines a desired level of robustness. Then, to overcome a possible limitation of the previous approach, in which the variation of an uncertain size is not related to its nominal value, another robust approach based on the concept of relative resiliency proposed by [START_REF] Pirogov | Robust balancing of production lines: MILP models and pre-processing rules[END_REF], is developed. The relative resiliency of a solution is the proportion by which each uncertain size can be increased without losing solution feasibility.

Hereafter, the robust BP problem ensuring that the stability radius calculated for the 1 norm (resp. the ∞ norm) is not less than r is denoted as RBP 1 (r) (resp. RBP ∞ (r)), and the robust BP problem ensuring the relative resiliency is not less than α is denoted as RBP rr (α). These three problems can be simply stated as follows.

We want to pack a given set of one-dimensional items whose nominal sizes are known into a minimum number of one-dimensional identical bins of the same given capacity. A known subset of these items have uncertain sizes, which can vary after the allocation of items to bins. The solution must remain feasible for real item sizes, provided that the variations of uncertain sizes are bounded as follows:

• with RBP ∞ (r), each uncertain size can be increased by a maximum of r,

• with RBP rr (α), each uncertain size w i can be increased by a maximum of αw i ,

• with RBP 1 (r), in any bin with at least one uncertain-size item, the sum of all uncertain sizes' variations is at most r.

Given these conditions, a solution to any instance of RBP ∞ (r) (resp. RBP rr (α)) can be obtained by solving an instance of BP , in which each uncertain size w i is increased by r (resp. αw i ), to reserve free space. Therefore, RBP ∞ (r) and RBP rr (α) can both be straightforwardly reduced to BP . However, this is not the case with RBP 1 (r), as it requires a quantity of free space not lesser than r in each bin containing at least one item of uncertain size.

Note that, a solution to BP has a stability radius (resp. relative resiliency) at least equal to r (resp. α) if and only if a quantity r (resp. αw i ) of free space is reserved for each item i of uncertain size w i in its assigned bin. Similarly, a solution to BP has a stability radius at least equal to r if and only if a quantity r of free space is reserved in each bin containing at least one uncertain item.

Formal definitions of stability radius, relative resiliency, and proofs of the properties stated above are provided in Appendix A.

The remainder of this paper is organized as follows. Section 2 provides a literature review about column-generation based approaches for variants of BP under uncertainty and branch-and-price algorithms for BP . Section 3 presents the details of the adapted branch-and-price method for the proposed set-cover formulation valid for RBP 1 (r), RBP ∞ (r), RBP rr (α) and BP . Section 4 is devoted to numerical experiments, in which we evaluate the performance of the proposed branch-andprice algorithm and we investigate what protection against uncertainty is offered by each approach and at which cost of robustness. Section 5 concludes the paper and gives some perspectives for future work.

Literature review

We first consider two papers introducing column-generation based algorithms to tackle variants of BP under uncertainty, then the literature about branch-and-price algorithms designed to solve the set-cover formulation of BP provided in Section 3.2. [START_REF] Song | The robust machine availability problem -bin packing under uncertainty[END_REF] address the robust machine availability problem in a parallel machine environment, which in its deterministic version coincides with BP . Using the methodology proposed by [START_REF] Bertsimas | The price of robustness[END_REF], they introduce a robust version with budgeted uncertainty, where at most Γ jobs can deviate from their nominal processing times, which are assumed to belong to symmetric and bounded intervals. They propose a set-cover formulation with an exponential number of columns. The formulation is solved by a branch-and-price algorithm, with the Ryan and Foster branching scheme, and zero-suppressed binary decision diagrams to handle a pricing problem more complicated than the one occuring with BP . They perform numerical experiments on a new set of randomly generated instances. Results show that their algorithm can handle instances with up to 180 items within a time limit of 1200 seconds, provided that either the value of Γ is small, or the size of each item is in the range {1, . . . , 20}. [START_REF] Alem | On the cutting stock problem under stochastic demand[END_REF] address a stochastic variant of the one dimensional cutting stock problem, where demand is a random variable. The authors propose a two stage stochastic non-linear program, where the first stage decisions are the numbers of objects to be cut according to a cutting pattern, and the second stage decisions are the numbers of holding or backordering items. The objective is to minimize the expected costs due to waste and holding or backordering penalties. A columngeneration based algorithm is introduced to solve the linear relaxation of the formulation, and heuristics allow integer solutions to be obtained. Numerical experiments are performed to investigate the value of the stochastic solution and the expected value with perfect information. The results show that the two-stage stochastic approach represents a better modeling framework than the alternative wait-and-see and expected value frameworks, even under small variations in the parameters of the problem.

There is abundant literature about branch-and-price algorithms, including general studies, for example by [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF][START_REF] Vanderbeck | On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm[END_REF], and [START_REF] Desrosiers | Branch-price-and-cut algorithms[END_REF], as well as many other application-related studies, in various domains, such as cutting and packing [START_REF] Delorme | Bin packing and cutting stock problems: Mathematical models and exact algorithms[END_REF]), vehicle routing [START_REF] Fukasawa | Robust branch-and-cut-and-price for the capacitated vehicle routing problem[END_REF]), production planning [START_REF] Alfandari | A branch-and-price-and-cut approach for sustainable crop rotation planning[END_REF]), etc. The theories and concepts behind branch-and-price algorithms are covered in the Ph.D. thesis by [START_REF] Gamrath | Generic branch-cut-and-price[END_REF].

We focus on two branch-and-price algorithms similar to the one proposed in Section 3 designed to solve the set-cover formulation of BP , which corresponds to the set-cover formulation proposed in this paper, when there is either no uncertain item or all items are uncertain, or r is equal to zero. These are the ones by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] and by [START_REF] Gamrath | The SCIP Optimization Suite 3.2[END_REF].

The first branch-and-price algorithm for the set-cover formulation of BP was proposed by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF]. The first-fit decreasing heuristic initializes the solving process with a primal solution.

The branch-and-price algorithm relies on the Ryan and Foster branching scheme, which selects one of the fractionally packed pairs of items for branching, and performs branching so that either the items are packed in the same bin, or in two different bins. In the first case, when items have to be packed in the same bin, the structure of the subproblem is preserved, as it suffices to merge the items. In the second case, the structure of the subproblem is altered, with the presence of a conflict constraint, forbidding the items in conflict to be packed together. When considering pairs of items for branching, the one with the largest total size is selected. Nodes of the search tree without any conflict constraint are explored first, as their subproblem can be solved by a more efficient algorithm. [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] proposed solving the subproblem without conflict constraint, that is, the pseudopolynomial 0-1 knapsack problem, with the [START_REF] Horowitz | Computing partitions with applications to the knapsack problem[END_REF] algorithm, having a worst case temporal complexity in O(min{2 n/2 , n • W }), potentially better than the one of the classical dynamic programming algorithms, in O(n • W ), described by [START_REF] Kellerer | Knapsack problems[END_REF]. When each item is in conflict with at most one other item, [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] use an adapted version of the algorithm by [START_REF] Horowitz | Computing partitions with applications to the knapsack problem[END_REF]. Otherwise, in the presence of conflict constraints, the subproblem becomes strongly NP-hard, and it is addressed with an integer linear program solver.

The branch-and-price algorithm proposed by [START_REF] Gamrath | The SCIP Optimization Suite 3.2[END_REF] also uses a branching scheme based on the Ryan and Foster branching scheme. Nevertheless, it differs from the one by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] on several points. First, one of the most unfeasible pairs of items is selected for branching, that is, the one which provides a sum value closest to 0.5. Second, the node which is selected for exploration is the one which provides the best estimation value of the progress toward integer feasibility, relative to its degradation of the objective function. Third, since this branch-and-price algorithm is provided as an example with the SCIP Optimization Suite, it relies on its integer linear program solver to address the subproblem. Last, for the same reason, it uses primal heuristics of the SCIP Optimization Suite, described in [START_REF] Berthold | Heuristics of the branch-cut-and-price-framework SCIP[END_REF] and [START_REF] Achterberg | Rounding and propagation heuristics for mixed integer programming[END_REF]. This includes more than forty very fast heuristics, generally requiring only a few milliseconds, even with the largest BP instances. They are called repetitively during the exploration of the search tree.

The branch-and-price algorithm that we propose is presented in the next section, and some of the concepts involved, such as dynamic column generation, are covered in more detail.

A branch-and-price algorithm

We are given a set K of one-dimensional identical bins of capacity W , a set V = {1, 2, . . . , n} of one-dimensional items, a nominal size w i for each item i ∈ V , and a set V ⊆ V of items of uncertain size. An allocation of the set of items to the set of bins is called a feasible solution to BP if each item is assigned to exactly one bin such that the capacity constraints are satisfied. We use the following decision variables: x ik is set to one if item i is assigned to bin k, and zero otherwise, and y k is set to one if bin k is used and zero otherwise.

We introduce a branch-and-price algorithm for RBP 1 (r) derived from the ones proposed by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] and by [START_REF] Gamrath | The SCIP Optimization Suite 3.2[END_REF] for BP . This algorithm can also be used for BP , which corresponds to RBP 1 (r) when there is no uncertain items, and, therefore, for RBP ∞ (r) and RBP rr (α), as explained below.

RBP ∞ (r) can be formulated as follows.

min k∈K y k (1a) s.t. k∈K x ik ≥ 1, ∀i ∈ V, (1b) i∈ V (w i + r)x ik + i∈V \ V w i x ik ≤ W y k , ∀k ∈ K, (1c)
y k ∈ {0, 1}, ∀k ∈ K, (1d)
x ik ∈ {0, 1}, ∀i ∈ V, ∀k ∈ K. ( 1e
)
Where (1a) minimizes the number of open bins, (1b) assigns each item to at least one bin, (1c) enforces the bin capacity. Here, the size of all the uncertain items has been increased by the positive constant r, as per Property 4 presented in Appendix A, and (1d)-(1e) are domain constraints.

RBP rr (α) can be formulated using the same BP model, but where constraints (1c) should be replaced with:

i∈ V w i (1 + α)x ik + i∈V \ V w i x ik ≤ W y k , ∀k ∈ K.
In this constraint, the size of all the uncertain items is multiplied by 1 + α, where α is a positive constant, as per Property 5 presented in Appendix A.

Compact formulation of RBP 1 (r)

The compact formulation of RBP 1 (r) uses an additional decision variable: a k is set to one if bin k contains at least one uncertain-size item, and zero otherwise.

RBP 1 (r) can be formulated as follows.

min k∈K y k (2a) s.t. k∈K x ik ≥ 1, ∀i ∈ V, (2b)
x ik ≤ a k , ∀i ∈ V , ∀k ∈ K, ( 2c
) i∈V w i x ik + ra k ≤ W y k , ∀k ∈ K, (2d)
y k ∈ {0, 1}, ∀k ∈ K, (2e)
a k ∈ {0, 1}, ∀k ∈ K, (2f)
x ik ∈ {0, 1}, ∀i ∈ V, ∀k ∈ K. (2g)
Constraints (2b) are the same as (1b). Constraints (2c) give to each variable a k the value 1 if bin k contains at least one uncertain-size item. Constraints (2d) represent the bin capacity, taking into account the minimum desired level of robustness r for the bins having uncertain-size items. This constraint is also a natural consequence of Property 6, presented in Appendix A. More specifically, this property pertains to bins that accommodate uncertain items. In the present formulation of RBP 1 (r), these bins are open (y k = 1) and such that a k = 1. Objective (2a) is to minimize the number of bins used.

Note that, BP is a particular case of RBP 1 (r), where there is no uncertain item ( V = ∅), or all items are uncertain (V = V ), or, alternatively r = 0. When there is no uncertain item, variables a k can be set to 0, and we obtain a formulation of BP . When all items are uncertain, or r = 0, variables a k can be set to 1, and we also obtain a formulation of BP .

Besides, the linear programming relaxation of this compact formulation is expected to be weak, as shown by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] for their formulation of BP , which we extended. To check if a stateof-the-art solver is able to solve this compact formulation, we performed numerical experiments on adapted instances of [START_REF] Falkenauer | A hybrid grouping genetic algorithm for bin packing[END_REF]. We added 20% of uncertain-size items and we set r equal to 10% of the bin capacity. Only 30 of the 80 adapted instances were solved by IBM CPLEX 12.7 within a time limit of one hour per instance, which motivated us to develop a more efficient approach.

Set-cover reformulation of RBP 1 (r)

Another possibility is to use a set-cover formulation, which is obtained by applying the Dantzig-Wolfe decomposition principle [START_REF] Dantzig | Decomposition principle for linear programs[END_REF]), in order to obtain in this case a much tighter lower bound on the optimal value of bins.

Once the constraints (2b) are dualized in a Lagrangian way [START_REF] Lemaréchal | The omnipresence of lagrange[END_REF]), subsystem (2c)-(2d) decomposes into a subproblem for each bin k ∈ K. Let B be the family of the subsets of items that can be fit into one bin with respect to uncertain sizes and to the threshold r on stability

radius ρ 1 . Each subset B ∈ B is defined by an indicator vector x B (x B i = 1 iff item i ∈ V is in set B)
and associated with a binary variable λ B taking value 1 if the corresponding subset of items is selected to fill one bin.

The reformulation is:

min B∈B λ B (3a) s.t. B∈B x B i λ B ≥ 1, ∀i ∈ V, (3b) B∈B λ B ≤ K (3c) λ B ∈ {0, 1}, ∀B ∈ B. (3d)
Here, constraints (3b) replace constraints (2b), constraints (3c) limit the number of used bins to at most K, and all other constraints of the compact formulation are built into the definition of feasible sets B ∈ B of items. This problem will be referred to as the master problem. When V = ∅ or V = V or r = 0, we obtain the set-cover formulation of BP , for which it is conjectured that the difference between the linear relaxation value at root node and the optimal solution value is always less than or equal to two (see, for example, [START_REF] Scheithauer | Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem[END_REF].

The set-cover formulation, which has an exponential number of columns, is addressed by a branch-and-price approach. Its principles are described in Section 3.3. At each node of a branchand-bound tree, its linear relaxation is solved by dynamic column generation. The master problem is restricted to a subset of columns, and its linear relaxation is solved by the simplex method. Then, a pricing subproblem is solved to check for the existence of an improving column, with a negative reduced cost. It consists in solving the following robust variant of the knapsack problem, denoted as P S (LP ) :

max i∈V π i z i (4a) s.t. z i ≤ a, ∀i ∈ V , (4b)
i∈V

w i z i + ra ≤ W, (4c)
z i ∈ {0, 1}, ∀i ∈ V, (4d)
a ∈ {0, 1}. ( 4e
)
The formulation of the pricing subproblem is related to a vector of dual variables π corresponding to constraints (3b) of the set-cover reformulation. A binary variable z i indicates whether item i is selected. A binary variable a indicates whether the knapsack contains at least one uncertain-size item or not. Clearly, the feasible solutions to this problem are the feasible subsets B ∈ B of items.

Dynamic column generation at root node

The number of variables of the set-cover formulation grows exponentially with the number of items. Hence, it is only possible to generate all of its columns when the number of items is small.

Otherwise, with a large number of items, the well-known principle of dynamic column generation can be applied. Dynamic column generation allows the linear relaxation of the set-cover formulation to be solved, as proposed by [START_REF] Dantzig | Decomposition principle for linear programs[END_REF] for linear programs, considering, implicitly, the whole set of columns. An iteration of dynamic column generation starts with solving the linear relaxation of the set-cover formulation restricted to a relatively small subset of columns. The first iteration begins with a column pool constituted of columns corresponding to subsets of B containing exactly one item, and of columns in the solution provided by the adapted first-fit decreasing heuristic, described below in Section 3.6.1. Solving the restricted master problem with the Simplex method provides values of dual variables π i , for all i ∈ V .

Then, to check whether an improving column exists, reduced cost pricing is performed, by solving P S (LP ) , for the current values of dual variables. If its optimal objective value is strictly larger than one, the corresponding improving column, with a negative reduced cost, is added to the current restricted master problem, providing a new restricted master problem, and a new iteration of dynamic column generation starts. If not, no improving column exists, and the current feasible solution to the linear relaxation of the set-cover formulation is optimal.

P S (LP ) is a robust variant of the 0-1 knapsack problem. It can be solved in pseudo-polynomial time, by solving two instances of the 0-1 knapsack problem, as shown below.

Property 1. P S (LP ) can be solved in O(n•W ), by solving two instances of the 0-1 knapsack problem.

Proof. First, the value of binary variable a is set to 0 (the bin contains no uncertain-sized item), and the resulting 0-1 knapsack problem is solved in O(n • W ), with the classical dynamic programming algorithm (see [START_REF] Toth | Dynamic programming algorithms for the zero-one knapsack problem[END_REF]). Second, the same is done for a = 1 (the bin is allowed to contain at least one uncertain-sized item). Then, one of the two solutions which provides the best value is selected, and it is an optimal solution to P S (LP ) . Hence, solving P S (LP ) requires

O(2 • n • W ) = O(n • W ) operations.
Note that, by ordering the items such that certain-sized items are followed by uncertain-sized items, and by adapting the classical dynamic programming algorithm (see [START_REF] Toth | Dynamic programming algorithms for the zero-one knapsack problem[END_REF]) so that, when uncertain-sized items are reached, the knapsack capacity is decreased by r, it is possible to solve P S (LP ) with a single call to this adapted algorithm. However, we use two calls to the Combo algorithm [START_REF] Martello | Dynamic programming and strong bounds for the 0-1 knapsack problem[END_REF]) to deal with P S (LP ) and solving two knapsack problems.

As its name suggests, the Combo algorithm is a combination of several techniques. One of the central ideas upon which it relies is that a small subset of items is generally enough to form an optimal solution. Therefore, the Combo algorithm restricts the search to a subset of items denoted as the core, which is expanded when needed. Besides this, the algorithm makes use of upper and lower bounds, which allow to fathom dominated states in the list-based dynamic programming procedure, and to terminate the search earlier.

When the Combo algorithm is called to solve the second instance of the 0-1 knapsack problem, it takes advantage of the lower bound provided by the solution to the first one. It generally enables us to solve the robust 0-1 knapsack subproblem faster than the adapted dynamic programming algorithm. Note that, for a pricing subproblem occurring when V = ∅, Combo is called only one time (for a = 0).

Finally, we use the bound proposed by [START_REF] Farley | A note on bounding a class of linear programming problems, including cutting stock problems[END_REF] to terminate column generation early when

v RMP = v RMP v PS ,
where v RMP is the linear relaxation value of the current restricted master problem and v PS is the optimal solution value to the current pricing subproblem. This bound is also used by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] and [START_REF] Song | The robust machine availability problem -bin packing under uncertainty[END_REF]. It was shown to be effective in reducing tailing off effects.

Branching scheme

Dynamic column generation provides solutions to the linear relaxation of the set-cover formulation. However, its solution generally does not satisfy integrality constraints. When some of the variables of the solution to the linear relaxation of Problem (3) have non-integral values, branching is performed. We use the branching rule described by [START_REF] Ryan | An integer programming approach to scheduling[END_REF], which relies on the following property.

Property 2. Let B i,j ⊂ B be the set of patterns that contains both items i and j. A solution to the linear relaxation of the set-cover formulation contains variables with non-integral values if and only if there exists an item pair {i, j} such that: 0 < B i,j λ B < 1 [START_REF] Ryan | An integer programming approach to scheduling[END_REF]).

When the solution to the linear relaxation of the set-cover formulation contains variables with non-integral values, we select one of the item pairs {i, j} with the most unfeasible value, that is, which minimizes |0.5-B i,j λ B |. At least one such pair is guaranteed to exist, according to Property 2.

Then, two child nodes are created. In the left node, items i and j have to be in the same bin: the branching constraint is z i = z j . In the right node, items i and j have to be in different bins: the branching constraint is z i + z j ≤ 1. In each of the two nodes, the variables of the restricted master problem corresponding to columns which do not satisfy its branching constraints are removed. Each branching constraint is directly added to the subproblem of its node, so that such columns are not generated again. The problem of each node is solved by column generation, and branching occurs as with the root node. The search tree is explored by a depth-first search procedure with restart, in which the best-bound node is selected periodically for a new start of depth-first search.

In [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] The "Most unfeasible" strategy of the proposed branch-and-price algorithm shows faster convergence than the "Largest sum" strategy with these instances. These instances require the exploration of a relatively large search tree, and the choice of this strategy is therefore important with them. In the case of a non-optimal solution, only one extra bin was always used.

Subproblems after branching

Imposing branching constraints z i = z j on pairs {i, j} of items in a 0-1 robust knapsack subproblem preserves its structure. Each of these constraints ensure that either both or none of the items of its pair are selected. Hence, items i and j can be merged into an item of weight w i + w j and value

π i + π j .
The resulting item has an uncertain size if i or j has an uncertain size, otherwise it is a certain-size item. This subproblem is denoted as P S (lef t) and it is equivalent to P S (LP ) .

However, imposing branching constraints z i + z j ≤ 1 on pairs {i, j} of items (conflict constraints, also called disjunctive constraints) to a 0-1 robust knapsack subproblem alters its structure. It turns the subproblem into a robust 0-1 knapsack problem with conflict constraints on items, denoted as P S (right) . The non-robust variant of this problem is referred in the literature to as 0-1 knapsack problem with conflicts. The 0-1 knapsack problem with conflicts is strongly NP-hard, and the more general robust variant is therefore also strongly NP-hard. Property 1 can be straightforwardly adapted to P S (right) , which is addressed by solving two instances of the 0-1 knapsack problem with conflicts. The optimal solution value to the first P S (right) instance (for a = 0), is used as a lower bound for the second instance (for a = 1). Note that, for a pricing subproblem occurring when V = ∅, this algorithm is called only one time (for a = 0).

We solve the 0-1 knapsack problem with conflicts with the dedicated branch-and-bound algorithm by [START_REF] Sadykov | Bin packing with conflicts: A generic branch-and-price algorithm[END_REF], which combines the classic depth-first search based branchand-bound algorithm for the 0-1 knapsack problem by [START_REF] Kellerer | Knapsack problems[END_REF] with the enumeration algorithm for solving the maximum clique problem (or the independent set problem) by Östergård (2002). Upper bounds are computed at each node of the search tree by solving the linear relaxation of the residual knapsack problem, ignoring conflict constraints, with the well-known greedy algorithm for the 0-1 knapsack problem. This algorithm sorts the items in decreasing order of utility (i.e. the ratio value over weight), and then proceeds to insert them into the knapsack. A limit is set on the number of nodes, which is active only if the current primal bound is greater than one, that is, if an improving column has been found. The branch-and-bound terminates if this limit is reached and if one improving column is available. Otherwise, the solving process goes on, to obtain an improving column, or to prove that no such column exists.

Finally, we introduce the following dominance rule between items for P S (right) , which is an extension of classical dominance rules.

Property 3. Let C i ⊂ V be the set of items in conflict with i ∈ V , i.e., for each j ∈ C i we have

x i + x j ≤ 1.
If the following four conditions hold for any j ∈ C i , then item j is dominated by item i, and can be removed from the instance of the robust 0-1 knapsack problem with conflicts:

1. i ∈ V ∧ j ∈ V or i / ∈ V ∧ j / ∈ V or i / ∈ V ∧ j ∈ V , 2. π i ≥ π j , 3. w i ≤ w j , 4. C i \ {j} ⊆ C j \ {i}.
Proof. We show that, if the conditions are verified, any feasible solution s containing item j can be substituted by another solution s in which item j is replaced by item i, such that the value of s is greater than or equal to the value of s.

First, solution s is feasible, regarding (1) the slack space r required in the presence of at least one uncertain item, as i ∈ 2) the total item size, as w i ≤ w j , and (3) the conflicts between items, as C i \ {j} ⊆ C j \ {i}. Second, solution s has a value greater than or equal to solution s since π i ≥ π j .

V ∧ j ∈ V or i / ∈ V ∧ j / ∈ V or i / ∈ V ∧ j ∈ V , (
Hence, if the conditions are verified, it is not necessary to consider any solution containing j, which can be removed from the instance of the robust 0-1 knapsack problem with conflicts.

This dominance rule allows to eliminate some items of an instance of P S (right) in a preprocessing phase. It is not mentioned in the preceding studies by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF] and [START_REF] Sadykov | Bin packing with conflicts: A generic branch-and-price algorithm[END_REF], which uses the same branching rule, that conducts to a non-robust 0-1 knapsack problem with conflicts as subproblem.

We performed numerical experiments with the 50 difficult AI instances introduced by Delorme et al. ( 2016) to evaluate the impact of the proposed dominance rule. They do not allow free space in any optimal solution. The time limit was set to 3600 seconds. Results are reported in Table 2.

Column "Dominance rule" indicates whether the dominance rule is used or not. Column "Avg. CPU, (s.)" gives the average solution time in seconds. Column "#OPT" provides the number of proven optimal solutions obtained. Column "#NODES" gives the average number of opened nodes in the search tree. The proposed dominance rule enables a faster convergence for the algorithm, while exploring a larger number of nodes, as subproblems are solved faster after the reduction of the number of items they contain, and this reduction is done efficiently. In the case of a non-optimal solution, only one extra bin was always used.

Primal heuristics

We use the following primal heuristics, which have an important role in the efficiency of the proposed branch-and-price-algorithm, because they generally provide optimal or near optimal solutions earlier than the branching procedure would.

Adapted first-fit decreasing heuristic

The F F D (First-Fit Decreasing heuristic) for BP can be stated as follows: items are sorted by non-increasing weights, and placed into the first bin in that order where it is possible. If no bin with enough free space is available, a new bin is used. F F D uses no more that 11/9 OP T + 1 bins for BP , where OP T denotes the optimal number of required bins, as shown in [START_REF] Yue | A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm[END_REF].

F F D is simply adapted to RBP 1 (r) as follows: first, F F D is applied to uncertain-sized items only, with the capacity of the used bins decreased by r, producing a partial solution; second, F F D is applied to certain-sized items, using the residual bin capacities of the partial solution, and using new bins when needed.

The main idea here is to pack together uncertain-sized items, as the presence of only one uncertain-sized item in a bin decreases its capacity by r. Hence, in an optimal solution, uncertainsized items tend to be packed together as much as possible. The adapted F F D for RBP 1 (r) is used to initiate the branch-and-price algorithm with a primal solution, providing both a primal bound and columns for the first restricted master problem.

Integer programming based heuristics

We use all the integer programming based heuristics provided with the SCIP Optimization Suite, upon which our branch-and-price algorithm is implemented. Only three of the most efficient ones with the proposed formulation are presented here, for the sake of brevity. They are executed repetitively as new columns are generated during the branch-and-price algorithm, with the aim of constructing integer solutions using the pool of columns available at the current node.

Simple rounding. Given a feasible solution to the linear relaxation of the set-cover formulation, simple rounding rounds up each variable to obtain a feasible integer solution.

One-opt. One-opt starts from a feasible solution to the set-cover formulation, for example provided by Simple Rounding, and tries to improve it, by shifting some values of the variables from 1 to 0 whenever possible.

ZI Round. Given a feasible solution λ to the linear relaxation of the set-cover formulation, ZI Round defines the fractionality for each variable λ B as ZI(λ B ) = min{λ B -λ B , λ B -λ B } and the fractionality of the solution as ZI(λ) = B∈B ZI(λ B ). The goal of ZI Round is to identify the variables that can be rounded to improve ZI(λ) until the integer infeasibility becomes 0 at which point an integral solution has been found. Therefore, each variable λ B is rounded in the direction that reduces ZI(λ B ) the most. In the case of a tie, the variable is rounded down. The ZI Round heuristic is described in detail by [START_REF] Wallace | ZI round, a MIP rounding heuristic[END_REF].

Numerical experiments

We conduct, with three main purposes, numerical experiments based on standard instances of BP , from which we construct instances with uncertain-size items. First, we explore numerically the tractability of these problems by the proposed branch-and-price algorithm. Second, we estimate numerically the costs of robustness, in terms of the average additional numbers of required bins, for the three proposed robust approaches. Third, we perform simulations of solution feasibility under various scenarios generated with different probability distributions for increasing variations of uncertain sizes. Last, an evaluation of the ability of the proposed branch-and-price algorithm to deal with BP , using as a reference results found in the literature, is provided in Appendix B.

The branch-and-price algorithm is implemented in C on top of the SCIP Optimization Suite 7.0.2. IBM CPLEX 12.8 is used as the linear programming solver. All numerical experiments were performed on an Intel Core i7-6700HQ CPU at 2.6 GHz with 4 GB of RAM. The time limit was set to ten minutes of running time per instance. For the branch-and-bound algorithm which solves the knapsack problem with conflicts, the limit on the number of nodes, active only when an improving column has been found, is set to 10000|V |. Depth first search is restarted from the best-bound node every 100 nodes. Average results are reported here, but full results are available at: https://tinyurl.com/y6myu7uo.

4.1. Adaptation of the BP instances to RBP 1 (r), RBP ∞ (r) and RBP rr (α)

We considered all the most used BP benchmark sets from the literature, and selected those where item sizes are sufficiently lower than bin capacity, to be turned into feasible robust instances.

BP instances from the following studies were adapted to RBP 1 (r), RBP ∞ (r) and RBP rr (α).

Falkenauer (1996). We use the 80 instances from the set Falkenauer T, which have between 60 and 501 items, a bin capacity equal to 1000, and item sizes in the range {250, • • • , 499}. [START_REF] Scholl | Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[END_REF]. We use the 10 instances from the set Scholl 3. Their number of items is uniformly distributed between 50 and 500. The bin capacity is equal to 100,000. Item sizes are in the range {20000, • • • , 35000}. [START_REF] Schwerin | The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP[END_REF]. We use two sets of 100 instances, one with 100 items, Schwerin 1, the other with 120 items, Schwerin 2, and a bin capacity equal to 10,000. Item sizes are in the range

{150, • • • , 200}.
Let P stand for the probability for an item to have an uncertain size. We set P = 0.1 to generate 290 instances, in which a binary flag is simply added to indicate whether an item size is uncertain or not, then P = 0.3 to generate 290 others and finally P = 0.5 to generate the last 290. In the following, these instances are used for non-robust BP , treating for this problem uncertain sizes as certain, as well as for the robust approaches RBP 1 (r), RBP ∞ (r) and RBP rr (α), for which r or α is considered as a separate parameter.

Results of the proposed branch-and-price algorithm for the robust variants of BP

In Tables 3, 4 and5 Column "#OPT, (%)" provides the percentage of proven optimal solutions obtained. Column "#SOL, (%) with GAP = 1" gives the percentage of solutions with an absolute gap of one with the best known lower bound at the end of the optimization process.

In every case, the proposed algorithm either converged to a proven optimal solution or obtained a solution with an absolute gap of one to the best known lower bound. Hence, for each row, the sum of the two last columns equals 100 percent. As the proposed algorithm always obtains an optimal solution with RBP ∞ (r) and RBB rr (α), the last column is omitted in Tables 4 and5.

4.2.1. Results of the proposed branch-and-price algorithm with RBP 1 (r)

In Table 3, we report average results of the proposed branch-and-price algorithm with RBP 1 (r), aggregated by percentage of uncertain-size items and by value of r. With RBP 1 (r), the proposed branch-and-price algorithm obtains an optimal solution 91% of the times. Its average running time is less than one minute, and its running time is greater than one minute for 37% of the runs.

At the end of the optimization process, the absolute gap between the rounded-up lower bound and the best-found integer feasible solution value, within the time limit of ten minutes, is always lower than or equal to one. This means that either one extra bin is used, compared to an optimal solution, or that the solution is optimal, but the rounded-up lower bound is one unit below. In the latter case, proving optimality requires branching to increase the lower bound, which may be computationally expensive, and generally can't be achieved within the time limit of 600 seconds.

Only nine such instances were solved within this time limit.

4.2.2. Results of the proposed branch-and-price algorithm with RBP ∞ (r)

In Table 4, we report average results of the proposed branch-and-price algorithm with RBP ∞ (r), aggregated by percentage of uncertain-size items and by value of r. With RBP ∞ (r), the proposed branch-and-price algorithm always obtains an optimal solution, in less than 2 seconds on average. The algorithm requires only six times more than 30 seconds to converge, with a maximum solving time at 180 seconds. The gap between the rounded-up value of linear relaxation at root node and the optimal integer solution value is always equal to zero.

4.2.3. Results of the proposed branch-and-price algorithm with RBP rr (α)

In Table 5, we report average results of the proposed branch-and-price algorithm with RBP rr (α), aggregated by percentage of uncertain-size items and by value of α. With RBP rr (α), the proposed branch-and-price algorithm always obtains an optimal solution, in less than 3 seconds on average. The algorithm always requires less than 30 seconds to converge.

The gap between the rounded-up value of linear relaxation at root node and the optimal integer solution value is always equal to zero.

Numerical evaluation of the extra cost for robustness

In the following, the extra cost for robustness is measured as the percentage of extra-bins required in the best found robust solution, for the considered robust approach, compared to the best found non-robust BP solution, to the same base instance. Concerning the BP solutions, 868 out of 870 are optimal, and the two others may be optimal, or use at most one extra bin.

4.3.1. Extra costs for robustness with RBP 1 (r) and RBP ∞ (r)

In Figure 1, we report the increase of the number of bins in percentages, compared to the nonrobust case, for RBP 1 (r) and RBP ∞ (r), with a percentage of uncertain-size items varying from 10%, 30% to 50%, and r varying by 0.2W , 0.3W and 0.4W . The extra cost for robustness ranges from 4% to 146% of extra bins, depending on the robust approach, the percentage of uncertain-size items, and r. For RBP 1 (r), this extra cost remains moderate for V , (%) = 10%, ranging from 4% to 11% of extra bins. It grows up to 47% of extra bins for the maximum values of r = 0.4W and V , (%) = 50%. For RBP ∞ (r), this cost sharply increases with V , (%), particularly for larger value of r: for r = 0.4W , it ranges from 22% to 146%, as V , (%) increases.

Besides, we observe that the increase of the number of bins, compared to the non-robust case, is on average 2.8 times greater with RBP ∞ (r) than with RBP 1 (r). As can be easily proven, with the same value of the stability radius, and the same uncertain items, the extra cost with the ∞ norm is always greater than or equal to the one with the 1 norm.

4.3.2. Extra cost for robustness with RBP rr (α)

In Table 6, we report the increase of the number of bins in percentages, compared to the nonrobust case, for RBP rr (α), with a percentage of uncertain-size items equal to 10%, 30% or 50%, when α is set to 0.2 or 0.3 or 0.4.

Column " V , (%)" indicates the percent of uncertain-size items. Column "α" indicates the minimum relative resiliency. Column "Extra bins, (%)" provides the percent of extra bins required compared to the non-robust case. With relative resiliency, for 10% of uncertain items, the extra cost for robustness is almost negligible, under 4% of extra bins, even for α = 0.4. It remains under 10% for α ≤ 0.3, excepted for α = 0.3 and V , (%) = 50%. It reaches a maximum of 19% for the maximum considered values of α and V , (%). In the next section, we investigate through simulation the solution feasibility under various scenarios, for the proposed robust approaches, compared to a non-robust one.

Simulation of solution feasibility under various scenarios

We perform numerical simulation of solution feasibility under various scenarios. Random variables describing uncertain-size variations are assumed to be independent and identically distributed, with [-1, 1] as probability distribution's support. Five symmetric probability distributions are considered: truncated normal, triangular, bimodal, uniform and beta(0.5, 0.5). A variation is obtained by multiplying the draw of a random variable by a level of variation and by either bin capacity or current item size. Negative variations are converted to 0. Ten levels of variations are tested, from 0.05 to 0.5, by increment of 0.05.

For each of the 870 instances described in Section 4.1, each of the 10 levels of variation, each of the 5 probability distributions, in the case of variations relative to bin capacity and in the case of variations relative to item size, 1 000 scenarios are generated, resulting in a total of 87 000 000 scenarios. The feasibility of each solution obtained by the considered approaches, with the considered values for parameters r or α, is evaluated under each of the 100 000 scenarios generated for the corresponding instance.

For each probability distribution, in the case of variations relative to bin capacity and in the case of variations relative to item size, we report in Figure 2 the overall feasibility probability after real item sizes are known for each considered approach, against an increasing level of variation of uncertain sizes.

For a given probability distribution and a given level of variation, this overall feasibility probability of an approach, for a given value of r or α, is estimated as the number of scenarios that have a feasible solution, over the total number of scenarios. We observe that standard BP provides solutions with a feasibility probability always close to 0, as they don't reserve any free space in the used bins, that could absorb positive variations, and as they use as few bins as possible. Hence, in the case of uncertain sizes, if feasibility is required, a robust approach is a necessity.

Considering variations relative to bin capacity, therefore unrelated to each nominal size, only solutions to RBP ∞ (r) have a guarantee of feasibility, as long as any variation is not greater than r. Although the cost of robustness with RBP ∞ (r) is high (see Section 4.3.1), it is a requirement for this guarantee, according to Property 4. Once r is exceeded, the feasibility probabilities always quickly decrease, as r increases, at a rate that depends on the probability distribution, and which is higher when more extreme values are generated, for example with the beta(0.5, 0.5) distribution.

Hence, these solutions are not overly conservative, even in the presence of negative variations, as in these simulations, which compensate positive ones.

A solution to RBP 1 (r) comes with some protection against uncertainty, but generally no guarantee of feasibility. Its feasibility probability is close to one for a range of variation level that depends on the probability distribution and on r. With the truncated normal distribution, this probability is greater than 0.7 with a variation level not greater than r. For probability distributions generating more extreme values, this probability is lower.

As can be expected, relative resiliency based approaches are inadequate for variations that are not related to nominal item sizes, as they have a low probability of feasibility.

Finally, in the case of variations related to nominal sizes, relative resiliency is a more adequate approach, which offers both a feasibility guarantee and a smaller cost for robustness. In this case, the proposed stability radius based approaches require more bins to offer the same protection against uncertainty.

Conclusion and perspectives

In this paper, we introduced three robust variants of the BP problem with items of uncertain size. After the assignment of items to bins has been decided, the size of these items can vary. The objective was to minimize the number of bins used, while ensuring the chosen level of robustness.

Three indicators of robustness were studied: the stability radius calculated by using the 1 norm, the stability radius calculated by using the ∞ norm, and the relative resiliency, in which possible variations are related to nominal size values. A unique 0-1 linear program was designed, valid for the three robust variants of the BP problem. A set-cover reformulation of the model was done with an exponential number of columns, but a stronger linear relaxation bound. A branch-and-price algorithm with dynamic column generation was developed. Then, a thorough numerical study was performed with thousands of standard benchmark BP instances, in which randomly chosen item sizes were set are uncertain.

We observed that the proposed algorithm is able to obtain an optimal solution to every instance of RBP ∞ (r) and RBP rr (α), on average in less than three seconds per instance. It also provided a proven optimal solution to 91% of RBP 1 (r) instances, and a solution either optimal or requiring one extra bin to the remaining ones, on average in less than one minute.

We also measured the extra cost for robustness, which ranged from 2% to 146% extra bins, depending on the robust approach, the percentage of uncertain items, and the value of r or α. Then, we performed simulation of solution feasibility under various scenarios, generated with different probability distributions for increasing variations. We observed that standard BP provides solutions with a feasibility probability always close to 0. In the case of variations relative to bin capacity, for all the considered robust approaches, feasibility probability always decreases relatively fast, as the level of variation increases. The solutions obtained with RBP ∞ (r) have a greater cost for robustness but come with a guarantee of feasibility when any variation is not greater than r. With variations observing a truncated normal distribution, a solution to RBP 1 (r) had a feasibility probability greater than 0.7 with a variation level not greater than r. For probability distributions generating more extreme values, this bound was lower. Finally, in the case of variations relative to item sizes, RBP rr (α) offers both a feasibility guarantee and a smaller cost for robustness.

This work offers several perspectives. First, one could consider different robustness models, with for example uncertain bins, in which all item sizes can deviate, or with different kinds of uncertainties, affecting different subsets of items. Second, the proposed branch-and-price algorithm could be improved. To achieve this, a possible research direction is related to the acceleration of the lower bound evaluation, another one to the improvement of this lower bound, and another one to the design of primal heuristics.

Appendix A Formal definitions

A.1 Definition of stability radius ρ 1 , stability radius ρ ∞ and relative resiliency ρ rr

To evaluate the robustness of a feasible solution, we use the stability radius concept, whose formal definition requires some additional notations to the ones provided in Section 3.1:

• w = (w 1 , w 2 , . . . , w n ) ∈ R n + , a vector expressing nominal item sizes. For any item i ∈ V of certain size, nominal and real sizes are assumed to be equal. For any item i ∈ V of uncertain size, there may be a difference between nominal and real sizes,

• Ξ = {ξ ∈ R n | ξ i = 0, i ∈ V \ V },
a set of vectors, such that each vector ξ ∈ Ξ represents a possible scenario of uncertain-size variations,

• F (w), the set of feasible solutions with respect to a given vector w ∈ R n + ,

• K = {k ∈ K | V k ∩ V = ∅},
= i∈ V |ξ i | and ξ ∞ = max i∈ V {|ξ i |}.
As a consequence, the notations ρ 1 and ρ ∞ will be used for 1 and ∞ , respectively.

The integer programming formulation of RBP 1 , RBP ∞ and RBP rr is based on the following three theorems, which are demonstrated by [START_REF] Rossi | Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations[END_REF], by [START_REF] Sotskov | Stability analysis of an optimal balance for an assembly line with fixed cycle time[END_REF] and by [START_REF] Pirogov | Robust balancing of production lines: MILP models and pre-processing rules[END_REF], respectively.

Theorem 1 [START_REF] Rossi | Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations[END_REF]). The stability radius ρ for a given feasible solution is calculated as follows: ρ 1 = min k∈ K W -i∈V k w i .

Theorem 2 [START_REF] Sotskov | Stability analysis of an optimal balance for an assembly line with fixed cycle time[END_REF]). The stability radius ρ ∞ for a given feasible solution is calculated as follows:

ρ ∞ = min k∈ K W -i∈V k w i |V k ∩ V | .
For some practical applications, a possible limitation of theses approaches is that variations are not related to nominal size values. Therefore, we consider another robust approach, proposed by [START_REF] Pirogov | Robust balancing of production lines: MILP models and pre-processing rules[END_REF], based on the relative resiliency.

The relative resiliency ρ rr (s, w) refers to the situation where each uncertain-size variation is bounded by an amount that is proportional to the nominal value defined by a coefficient α > 0.

The set of vectors representing possible scenarios of uncertain-size variations is then defined as Ξ(α, w) = {ξ ∈ Ξ | ξ i ≤ αw i , i ∈ V }. In this case, the relative resiliency ρ rr (s, w) = max{α ≥ 0 | s ∈ F (w + ξ), ξ ∈ Ξ(α, w)} is the greatest value of α for which the solution s remains feasible.

Theorem 3 [START_REF] Pirogov | Robust balancing of production lines: MILP models and pre-processing rules[END_REF]). The relative resiliency ρ rr for a given feasible solution is calculated as follows:

ρ rr = min k∈ K W -i∈V k w i i∈V k ∩ V w i .
A.2 Robust bin-packing problems RBP 1 (r), RBP ∞ (r) and RBP rr (α)

We define:

• RBP 1 (r) (resp. RBP ∞ (r)) as the problem of obtaining a solution to BP with a stability radius in norm 1 (resp. ∞ ) at least equal to r ∈ R + using a minimum number of bins.

• RBP rr (α) as the problem of obtaining a solution to BP with a relative resiliency at least equal to α ∈ R + using a minimum number of bins.

We introduce the following property which states that adding a value r ∈ R + to each uncertain size ensures that any feasible solution to the resulting instance of BP has a stability radius ρ ∞ at least equal to r in the original instance.

Property 4. A given feasible solution of BP has the stability radius ρ ∞ at least equal to r iff the following inequality i∈V k ∩ V (w i + r) + i∈V k \ V w i ≤ W holds for any bin k ∈ K.

Proof. The latter inequality is equivalent to the following one

i∈V k w i + |V k ∩ V | • r ≤ W , which can be transformed into r ≤ W -i∈V k w i |V k ∩ V |
and, as a consequence, we have r ≤ min

k∈ K W -i∈V k w i |V k ∩ V | .
Based on Theorem 2, we finally obtain that r ≤ ρ ∞ .

In Figure A.3, a robust solution to an instance of BP is presented with a total of five items, three uncertain sizes (items 2, 3 and 5), a bin capacity of ten, and a stability radius ρ ∞ equal to one. Property 4 states that to obtain such a solution, with a stability radius ρ ∞ at least equal to one, it is possible to add one to each uncertain size, and to solve the resulting BP instance, as it appears in the figure.

Similarly, the following property states that adding a value αw i to each uncertain size w i for i ∈ V ensures that any feasible solution to the resulting instance of BP will have a relative resiliency ρ rr at least equal to α in the original instance.

Property 5. A given feasible solution of BP has a relative resiliency ρ rr at least equal to α iff the following inequality i∈V k ∩ V (1 + α)w i + i∈V k \ V w i ≤ W holds for any bin k ∈ K.

Proof. The latter inequality is equivalent to the following one α • i∈V k ∩ V w i + i∈V k ∩ V w i ≤ W -i∈V k \ V w i , which can be transformed into α ≤ W -i∈V k w i i∈V k ∩ V w i and, as a consequence, we have α ≤ min k∈ K W -i∈V k w i i∈V k ∩ V w i . Based on Theorem 3, we finally obtain that α ≤ ρ rr .

Property 4 (resp. Property 5) implies that a solution to any instance of RBP ∞ (r) (resp.

RBP rr (α)) can be obtained by solving an instance of BP , in which item sizes are chosen accordingly.

(out of 5450) used by [START_REF] Delorme | Bin packing and cutting stock problems: Mathematical models and exact algorithms[END_REF]. The maximum amount of time per instance is set to one minute.

In Table B.7, we report comparative numerical results for BP obtained by the proposed branchand-price algorithm and other branch-and-price algorithms from the literature. In the column "Set", the name of the set of instances is provided. In the column "#INSTANCE", the number of tested instances for the corresponding set of instances is given. In the columns "#OPT", "#OPT Vance", "#OPT SCIP", "#OPT Belov", and "#OPT Song", the number of instances solved to optimality in less than one minute per instance, by the proposed branch-and-price algorithm, and by the ones by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF], by [START_REF] Gamrath | The SCIP Optimization Suite 3.2[END_REF], by [START_REF] Belov | A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[END_REF], and by [START_REF] Song | The robust machine availability problem -bin packing under uncertainty[END_REF], are provided, respectively. For "#OPT Vance", "#OPT SCIP", and "#OPT Belov", the reported results come from the study by [START_REF] Delorme | Bin packing and cutting stock problems: Mathematical models and exact algorithms[END_REF], in which a benchmark of several algorithms for BP was performed on the same computer, an Intel Xeon CPU at 3.1 GHz, with 8 GB of RAM, faster than the Intel Core i7-6700HQ CPU at 2.6 GHz with 4 GB of RAM that we used. An asterisk in a cell indicates that the algorithm obtained the maximum number of optimal solutions. In [START_REF] Song | The robust machine availability problem -bin packing under uncertainty[END_REF], results are provided for only six instance sets, and a hyphen "-" in a cell indicates that no results are available for the algorithm.

by [START_REF] Mukhacheva | Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB)[END_REF], may be adapted to RBP 1 and incorporated into the algorithm, to speed-up the solving process.

  , we report aggregated results obtained by the proposed branch-and-price algorithm for RBP 1 (r), RBP ∞ (r) and RBP rr (α), respectively. Results are grouped by percentage of uncertain-size items and by value of r or α. Each row provides aggregated results with 290 instances.Column " V , (%)" indicates the percentage of uncertain-size items. Column "r" or "α" provides the minimum value of the robustness indicator. The four other columns give aggregated values for the corresponding group of instances. Column "Min. CPU, (s.)" gives the minimum solution time in seconds. Column "Avg. CPU, (s.)" gives the average solution time in seconds. Column "Max. CPU, (s.)" gives the maximum solution time in seconds. Column "Std. CPU, (s.)" gives the standard deviation of solution time in seconds. Column "Avg. #BIN" indicates the average number of bins in the best found solutions.

Figure 1 :

 1 Figure 1: Increase of the extra cost for robustness, varying the percentage of uncertain-size items and r, for RBP1(r) and RBP∞(r)

Figure 2 :

 2 Figure 2: Simulation results of solution feasibility under five probability distributions, increasing maximum possible absolute variation, relative to bin size or item sizes

  the set of bins of a given feasible solution having at least one uncertain item, where V k is the set of items assigned to bin k.The stability radius of a feasible solution s ∈ F (w) can then be defined as follows (see[START_REF] Sotskov | Stability analysis of an optimal balance for an assembly line with fixed cycle time[END_REF]): ρ(s, w) = max{ ≥ 0 | ∀ξ ∈ B( ), s ∈ F (w + ξ)}, where B( ) = {ξ ∈ Ξ | ξ ≤ }.Hence, ρ(s, w) is determined as the value of the radius of the greatest closed ball B(•), called the stability ball which represents uncertain size variations, for which s remains feasible. Any element ξ of B(•) is evaluated based on a given norm • defining the distance between vectors w and w + ξ (or the amplitude of variations from w). In this paper, two norms 1 ( • 1 ) and ∞ ( • ∞ ) are considered, where by definition ξ 1

Table 1 :

 1 , a different item pair selection strategy is proposed: one of the {i, j} with the largest total size, but lower than the bin capacity, is selected for branching. We performed numerical experiments with the 50 difficult AI instances introduced by[START_REF] Delorme | Bin packing and cutting stock problems: Mathematical models and exact algorithms[END_REF] to compare this node selection strategy with the one we propose. These instances do not allow free space in any optimal solution. The time limit was set to 3600 seconds. Results are reported in Table1. Column "Strategy" provides the node-selection strategy. Column "Avg. CPU, (s.)" gives the average solution time in seconds. Column "#OPT" provides the number of proven optimal solutions obtained. Column "#NODES" gives the average number of opened nodes in the search tree. Comparison of two node-selection strategies

	Strategy	#OPT	Avg. CPU, (s.)	Avg. #NODES
	Most unfeasible	32	1337	8420
	Largest sum	12	2796	11444

Table 2 :

 2 Impact of the dominance rule

	Dominance rule	#OPT	Avg. CPU, (s.)	Avg. #NODES
	Yes	32	1337	8420
	No	24	1879	6427

Table 3 :

 3 Results of the proposed branch-and-price algorithm with RBP1(r), 870 runs

Table 4 :

 4 Results of the proposed branch-and-price algorithm RBP∞(r), 870 runs

	V , (%)	r	Min. CPU, (s.)	Avg. CPU, (s.)	Max. CPU, (s.)	Std. CPU, (s.)	Avg. #BIN	#OPT, (%)
		All	0.04	2.47	56.2	4.68	42.04	100%
		0.2W (290)	0.11	2.65	21.74	4.7	40.37	100%
	10%
		0.3W (290)	0.04	2.37	55.7	4.15	41.81	100%
		0.4W (290)	0.06	2.4	56.2	5.15	43.94	100%
		All	0	1.54	180.43	8.47	52.25	100%
		0.2W (290)	0.05	1.65	20.73	3.06	46.62	100%
	30%
		0.3W (290)	0.02	2.47	180.43	14.26	51.83	100%
		0.4W (290)	0	0.48	4.99	1.06	58.31	100%
		All	0	0.37	16.59	0.93	65.3	100%
		0.2W (290)	0.01	0.77	16.59	1.51	53.1	100%
	50%
		0.3W (290)	0.01	0.31	1.08	0.19	63.04	100%
		0.4W (290)	0	0.04	1.43	0.11	79.77	100%
	All	All	0	1.46	180.43	5.68	53.2	100%

Table 5 :

 5 Results of the proposed branch-and-price algorithm with RBPrr(α), 870 runs

	V , (%)	α	Min. CPU, (s.)	Avg. CPU, (s.)	Max. CPU, (s.)	Std. CPU, (s.)	Avg. #BIN	#OPT, (%)
		All	0.09	3.01	25.23	4.91	38.2	100%
		0.2W (290)	0.13	2.71	22.84	4.49	37.88	100%
	10%
		0.3W (290)	0.09	3.15	20.97	5.04	38.13	100%
		0.4W (290)	0.13	3.16	25.23	5.17	38.57	100%
		All	0.03	2.78	28.34	4.63	40.45	100%
		0.2W (290)	0.1	2.92	28.34	4.89	39.38	100%
	30%
		0.3W (290)	0.03	2.87	27.33	4.85	40.44	100%
		0.4W (290)	0.07	2.55	19.36	4.09	41.52	100%
		All	0.02	2.17	21.32	3.26	42.68	100%
		0.2W (290)	0.06	2.53	21.32	3.96	40.83	100%
	50%
		0.3W (290)	0.04	2.25	15.89	3.36	42.61	100%
		0.4W (290)	0.02	1.72	11.67	2.17	44.61	100%
	All	All	0.02	2.65	28.34	4.34	40.44	100%

Table 6 :

 6 Extra cost for robustness increasing relative resiliency, for RP Brr(α)

Idle time is the difference between the cycle time and the effective load of the considered workstation.

However, for RBP 1 (r), we can't use the same kind of straightforward reduction, as implied by the following Property. Property 6. A given feasible solution of BP has a stability radius ρ 1 at least equal to r iff the following inequality i∈V k w i + r ≤ W holds for any bin k ∈ K.

Proof. The latter inequality is equivalent to the following one r ≤ W -i∈V k w i , which conducts us to r ≤ min k∈ K W -i∈V k w i . Based on Theorem 1, we finally obtain that r ≤ ρ 1 .

Hence, with RBP 1 (r), any bin containing one uncertain item or more must keep a quantity of unused space at least equal to r, which led us to the 0-1 linear programming formulation of Section 3.1.

Appendix B Numerical results with BP

We provide numerical results for BP , with instances from the benchmark sets proposed by [START_REF] Falkenauer | A hybrid grouping genetic algorithm for bin packing[END_REF], [START_REF] Scholl | Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[END_REF], [START_REF] Wäscher | Heuristics for the integer one-dimensional cutting stock problem: A computational study[END_REF], [START_REF] Schwerin | The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP[END_REF], [START_REF] Schoenfield | Fast, exact solution of open bin packing problems without linear programming[END_REF] and [START_REF] Delorme | Bin packing and cutting stock problems: Mathematical models and exact algorithms[END_REF]. We restrict the report to the subset of 3877 instances Globally, the proposed algorithm is able to solve 93 percent of the instances of the considered subset in less than one minute per instance. It solves more instances than the previous ones based on the same branching rule: 19 percent more instances than the best previous one proposed by [START_REF] Vance | Solving binary cutting stock problems by column generation and branch-and-bound[END_REF]. It solves only 6 percent less instances than the best known branch-and-price algorithm for BP proposed by [START_REF] Belov | A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[END_REF].

Regarding the instances which are not solved within one minute, there are two main difficulties.

First, in the case of a large number of items or a large bin capacity, solving the linear relaxation of the master problem at root node may require more than one minute. Improving the performance of the proposed branch-and-price algorithm would require accelerating the lower bound evaluation. Second, obtaining an integer optimal solution may require too much branching and column generation. A very efficient tailored heuristic such as the one used by [START_REF] Belov | A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[END_REF] and introduced