Yacine Al Najjar

Noam Goldberg
email: noam.goldberg@biu.ac.il

Shlomo Karhi
email: shlomo.karhi@biu.ac.il

Michael Poss
email: michael.poss@lirmm.fr

Robust Two-Stage Packing into Designated and Multipurpose Bins

Multitype bin packing is a natural extension of the classical bin packing with applications to shipping using climate-controlled containers and plain dry containers. In transportation and other logistics applications there may be significant uncertainty with respect to the exact quantities of different variants of products (or item types) that may need to be shipped at the time when the containers and packaging are procured. In the current paper we model the problem as a robust two-stage two-item type bin packing problem. In the first stage bins of different types are acquired (e.g., reefer containers and dry containers). In the second stage the items are packed into bins. The bins that are secured in the first phase must allow for all of the items to be packed in the "worst-case" demand scenario. We first develop an algorithm for the robust two-stage two-item type bin packing problem with general itemnumber uncertainty sets and certain box uncertainty sets for item sizes (or equivalently two item sizes). We then consider the special case of identical (or unit) item sizes. In this special case we develop closed-form solutions for the optimal solution. Our closed-form solution reveals that it is optimal to use a number of multipurpose bins that is linear in the number of items. This is in contrast with solutions of the online and offline deterministic version of our problem that use at most one multipurpose bin. Finally, we consider computational methods that are efficient in practice for a generalization with unit item sizes but with an arbitrary number of item and bin types and arbitrary compatibility structures.

INTRODUCTION

Consider a two-stage problem in which there are demands for two types of items and these have to be packed using three types of bins; a bin type designated for each type of item and an additional multipurpose type of bin that can be used to pack both types of items. The bins are acquired before the demands, accordingly the quantities of the items n = (n 1 , n 2 ) are realized and become known. The objective is to minimize the costs while being able to meet every possible demand n in a (compact) set of possible scenarios N of the item demands. Some of our results may apply in particular to the case of finite uncertainty sets N . This case includes the standard bin packing problem setting where the numbers of bins are natural numbers. Without loss of generality we assume that the type-1 bin cost is 1 unit and that α, β are the costs of type-2 bins and multipurpose (type-3) bins, respectively, satisfying 1 ≤ α ≤ β < 1 + α.

The two-item type bin packing problem is introduced in Goldberg and [START_REF] Goldberg | Packing into designated and multipurpose bins: A theoretical study and application to the cold chain[END_REF]. It is motivated by two types of items to be transported with different climate control settings. In Figure 1 there are two types of items -ones that must be refrigerated above the freezing point and ones that need to be transported frozen. Then the three container types are a refrigerated containers set to the corresponding temperatures of refrigerating, freezing, and a multi-temperature container that can simultaneously transport items with different temperature requirements (see for example [START_REF] Savvas Tassou | Food transport refrigeration-approaches to reduce energy consumption and environmental impacts of road transport[END_REF]). Each bin type has a different cost and it is expected that more versatile bin types would cost more than ones that can contain only a few item types. In [START_REF] Goldberg | Packing into designated and multipurpose bins: A theoretical study and application to the cold chain[END_REF] the online two-size two-item type problem is considered. A tight (optimal) absolute competitive ratio of 1.618 is proved for this problem. The bin packing problem is closely related to machine scheduling where similar multipurpose machines and machine compatibility restrictions have been extensively studied; see for example [START_REF] Azar | The competitiveness of on-line assignments[END_REF], [START_REF] Shabtay | Online scheduling of two job types on a set of multipurpose machines with unit processing times[END_REF], [START_REF] Karhi | Online scheduling of two job types on a set of multipurpose machines[END_REF].

Robust optimization is a useful mathematical modeling framework that aims to determine solutions that are immune to uncertainty while addressing issues of computational tractability; see [START_REF] Ben-Tal | Robust optimization[END_REF], [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF]. This modeling approach is also useful in cases where the uncertainty is not easily described or estimated by any particular probability distribution. In such cases, the number of items of each type may be defined by a given uncertainty set. The type of uncertainty set is typically a box, given by an interval for each (independent) input parameter, budgeted uncertainty (which restricts not only the deviation of each parameter independently but also the total deviation), or an ellipsoid. [START_REF] Bougeret | Robust scheduling with budgeted uncertainty[END_REF] recently consider several variants of robust machine scheduling with different scheduling objectives (in the absence of multipurpose machines) in the robust optimization framework. Computational techniques such as branch-and-price algorithms are considered for a robust bin packing problem, in which item sizes are subject to uncertainty (or job processing times), in [START_REF] Song | The robust machine availability problem-bin packing under uncertainty[END_REF].

Multi-stage (also known as adjustable) robust optimization is an especially challenging setting in which the uncertainty is realized and decisions are made over two or more stages. The challenge remains also in the case of robust two-stage linear programs that are proven to be NP-hard [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. In the following we consider particular two-stage robust formulations motivated by the container shipping application of multitype bin packing that has been introduced by [START_REF] Goldberg | Packing into designated and multipurpose bins: A theoretical study and application to the cold chain[END_REF].

Multitype bin packing is extended to a two stage problem where the bins are ordered in the first stage and the items are produced and must be assigned to compatible bins in the second stage. The number of items of each type is subject to uncertainty in the first stage when the bins are ordered. For example, the uncertainty may be associated with the uncertain demand that each particular product variant faces before it is realized in the second stage.

A GENERAL ROBUST TWO-STAGE TWO-TYPE PROBLEM

In the general two-type problem, the number of bins of each type, as well as possibly the item sizes, are defined within given uncertainty sets. Suppose an arbitrary item number uncertainty set N ⊆ R 2 . Then, in the most general case for each n ∈ N , an uncertainty set is defined for the item sizes A(n) ⊆ R n1+n2

+

. The two-stage robust multipurpose bin packing problem is stated in the following.

Two-Stage Two-Type Robust Bin Packing

Given uncertainty (scenario) set N for the number of items of each type, and for each n ∈ N , item size uncertainty set A(n), determine the number of designated type-1 and type-2 bins y 1 , y 2 ∈ N, respectively, and number of multipurpose bins y 3 ∈ N so that the cost of bins needed to store all of the items in the worst case scenario, y 1 + αy 2 + βy 3 is minimized.

We focus on the particular case of a bin packing problem with two item types and item size sets A 1 and A 2 for type 1 and type 2 items, respectively. Accordingly A(n) = A 1 × A 2 for all n ∈ N . We also model unit-size situations in which uncertainty sets are defined only for the number of items and the set A(n) is a singleton. A key observation is that the problem with hyper-cube item-size uncertainty (for each item type) reduces to a two-size problem. It is summarized in the following proposition.

Observation 1. Suppose a 2-type bin packing problem with uncertain item numbers n = (n 1 , n 2 ) ∈ N and item sizes in hypercube sets A 1 and A 2 for type 1 and type 2 items, respectively. Then, the robust bin packing problem reduces to a two-size uncertain item number bin packing problem with sizes: a 1 = max a∈A1 ||a|| and a 2 = max a∈A2 ||a||.

In the following two sections we focus on the problem where each item type has a distinct size and then on the unit size case. Efficient algorithmic and closed-form results, respetively, are developed for these two settings.

In Section 5 we consider computational solution schemes in a general setting with an arbitrary number of item types and type-compatibility structure with unit-item sizes and variable bin sizes for different bin types.

ROBUST TWO-STAGE TWO-SIZE TWO-TYPE PROBLEM

Now consider the two-item size case where type 1 items have size a 1 and type 2 items have size a 2 = a 1 . The formulation (1) accounts for different item sizes in multipurpose bins using the set of all possible two-size feasible packing pattern set P. For each p ∈ P and i = 1, 2, z i (p) denotes the number of items of type i placed in a multipurpose bin by a (feasible) packing pattern p. For each i = 1, 2, y i denotes the number of designated bins of type i used, and x(n) i the number of items of type i packed into a bin a type i for n ∈ N . Note that although there may be exponentially many patterns (even with a constant number of item sizes) this formulation has a tighter linear programming relaxation compared with a compact assignment-based formulation of bin packing. Letting λ p denote the decision variable indicating how many bins of a pattern p ∈ P are opened then y 3 = p∈P λ p . Finally, the two-size robust two-stage integer program is given by the pattern based formulation

z * ≡ min y 1 + αy 2 + β p∈P λ p (1a) s.t. x(n) i ≤ V a i y i ∀n ∈ N , i = 1, 2 (1b) p∈P z i (p)λ p ≥ n i -x(n) i ∀n ∈ N , i = 1, 2. (1c) 0 ≤ x(n) i ≤ n i , ∀n ∈ N , i = 1, 2 (1d) λ p ∈ N p ∈ P y j ∈ N. j = 1, 2, 3
Let us define

n max ≡ max n∈N {n 1 + n 2 } , n max 1 ≡ max n∈N n 1 ,
and

n max 2 ≡ max n∈N n 2 .
For fixed numbers of designated bins, given by a pair of values, x 1 and x 2 , a sequence of two-size problems can be solved to determine the number of multipurpose bins needed in the worst case scenario. To this end, let ŷ3 (n 1 , n 2 ) denote the minimum number of bins required to pack n 1 , n 2 items of type 1 and type 2, respectively, in multipurpose bins. Then, the cost of a feasible solution given that x 1 , x 2 are packed in designated bins of type 1 and 2, respectively, is given by

f (x 1 , x 2 ) = x 1 V /a 1 + α x 2 V /a 2 + β max n∈N {ŷ 3 (n 1 -x 1 , n 2 -x 2 )} .
Note that N in this expression can be effectively replaced by a subset of nondominated scenarios N ⊆ N . In particular, n ∈ N implies that for all n ∈ N either n1

≥ n 1 or n2 ≥ n 2 . Conversely, n ∈ N is said to dominate n ∈ N if n ≥ n. Let f (x 1 , x 2 ) denote f (x 1 , x 2 ) with N replaced by N . So, given this set a straightforward algorithm is given by z A = min x1=0,...,n max 1 ,x2=0,...,n max 2 f (x 1 , x 2 ). ( 2
)
The subset of nondominated solutions can be computed in output-polynomial time [START_REF] Bökler | Output-sensitive complexity of multiobjective combinatorial optimization[END_REF]. The following proposition establishes the correctness and a running time complexity bound of the straightforward algorithm given by 2 in the case that the uncertainty (scenario set) N is either finite or polyhedral. Proposition 1. Suppose that N is either a finite or polyhedral set. Then, the algorithm given by (2) outputs z A = z * , an optimal solution for (1), with a time complexity bound of

O(n max 1 n max 2 N log n log 2 V ).
Proof. The algorithm enumerates for i = 1, 2 all possible values of x i in {0, . . . , n max i }. For each value of (x 1 , x 2 ), f (x 1 , x 2 ) evaluates the cost of opening x 1 and x 2 type 1 and type 2, respectively, designated bins, and the number of multipurpose bins required to maintain feasibility in the worst case nondominated scenario (in the set N ). In either case that N is finite or polyhedral, then the set N is finite (in the case that N is polyhedral then N is a subset of the finite set of extreme points of N ). The standard two-size problem is solved by the algorithm in [START_REF] Mccormick | A polynomial algorithm for multiprocessor scheduling with two job lengths[END_REF] whose complexity is O(log n log 2 V ), then the overall running time complexity of this straightforward algorithm is

O(n max 1 n max 2 N log n log 2 V ). 2
Note that the proof of the proposition in the case that N is polyhedral relies on the fact that N is a subset of the extreme points of N , which is a finite set. Further, the set of nondominated points N can be significantly smaller in cardinality than the set of extreme points of N .

UNIT SIZE ITEMS

In the unit size case we can formulate the problem as a robust mathematical program

z * ≡ min y 1 + αy 2 + βy 3 (3a) s.t. x(n) ii + x(n) i3 = n i ∀n ∈ N , i = 1, 2 (3b) x(n) ii ≤ V y i ∀n ∈ N , i = 1, 2 (3c) x(n) 13 + x(n) 23 ≤ V y 3 ∀n ∈ N (3d) y j , x ij ∈ N i = 1, 2, j = 1, 2, 3.
Here, for j = 1, 2, 3, y j is the number of bins of type j that are procured. For i = 1, 2 and j = 1, 2, 3, x(n) ij is the number of items of type i assigned to bin type j in demand scenario n = (n 1 , n 2 ), where n i is the demand for item type i.

Let y 3 = n max 1 V
-y 1 and consider the function f : R → R given by

f (y 1 ) =y 1 + (β -α)y 3 + α max n max V -y 1 , n max 2 V =(1 -β)y 1 + α max n max V , n max 2 V + y 1 + (β -α) n max 1 V .
Lemma 1. Suppose that y * is optimal for (3). Then, z * = y * 1 + αy * 2 + βy * 3 = f (y * 1 ). Proof. The fact that y * is feasible for (3), and in particular that it satisfies (3d), implies that y * 3 ≥

n max 1 V -y * 1 . If β > α,
then over all y that are feasible for (3), a pair

(y * 2 , y * 3 ) that minimizes f (y * 1 ) must have y * 3 ≤ n max 1 V -y * 1 .
To see this, suppose for the sake of contradiction that y * is optimal for (3) and y * 3 >

n max 1 V -y * 1 . Then, y * 3 ≥ n max 1 V - y * 1 + 1.
Letting y be defined by

y i =    y * 1 i = 1 y * 2 + 1 i = 2 y *
3 -1 i = 3, evidently y satisfies (3c)-(3d) and is therefore also feasible for (3). Further, the fact that β > α implies that y 1 +αy 2 + βy 3 < z * , thereby establishing a contradiction. Then, feasibility, in particular the fact that y * satisfies (3c

) for i = 2, implies that y * 2 = max n max V -y * 1 -y * 3 , n max 2 V -y * 3 . √ 2r V + (α + 1) √ 2r V -r V .
Interestingly, in the robust two-stage problem the number of multipurpose bins that are acquired in an optimal solution depends on the number of items and the uncertainty set. In sharp contrast, in the offline deterministic unit-size problem as well as online two-size problems that are described in [START_REF] Goldberg | Packing into designated and multipurpose bins: A theoretical study and application to the cold chain[END_REF], (optimal) solutions use at most one multipurpose bin (when β > α).

ARBITRARY NUMBER OF BIN TYPES WITH UNIT ITEM SIZES AND VARIABLE-SIZE BINS

In this section we generalize the unit-item size problem by considering an arbitrary number of item types and bin types. We are given as data for the problem a set of item types S and a set of bin types T . Each item type i ∈ S can only fit in a given subset T (i) ⊆ T of bins types. We also note S(j) the item types that can fit into bin j.

Each bin of type j ∈ T may contain up to V j items, and its cost is c j . The problem is to determine the number of bins of each type that must be ordered such that all possible realizations of the demand n ∈ N ⊆ R |S| can be satisfied at a minimum cost. We suppose that N is bounded from above, otherwise there may not exist any finite number of bins that can satisfy all possible demands n ∈ N . We model this problem as a mixed-integer linear program (MILP), which may contain an infinite number of variables and constraints,

z * ≡ min j∈M c j y j (4a) s.t. j∈T (i) x(n) ij = n i ∀i ∈ S, n ∈ N (4b) j∈S(j) x(n) ij ≤ V j y j ∀j ∈ T, n ∈ N (4c) y j ∈ N j ∈ T x(n) ij ≥ 0 i ∈ S, j ∈ T, n ∈ N .
Here for each j ∈ T , y j is a decision variable that represents the number of bins of type j that are ordered.

x ij is the number of items of type i ∈ S that are stored in a bin of type j ∈ T . Constraints (4b) ensure that for each demand scenario n ∈ N and for each item type i, its demand n i is fully assigned to some bin. Constraints (4c) ensure that the capacity of a bins is not exceeded in any scenario. Note that this problem generalizes notoriously hard (strongly NP-hard) weighted set cover and set partitioning problems; see for example [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF].

As discussed in Section 3, the notion of dominance can be used to consider a potentially small subset of set N . Dominance may not suffice to make problem (4) tractable. To this end, we develop computational schemes that are efficient in practice. In particular, methods are proposed for iteratively generating certain critical subsets of demand vectors N 0 ⊆ N .

Iterative methods

As in the case of the two-item type problem, we expect that a small subset of N may suffice to determine an optimal decision variable vector y. Accordingly, we now introduce an iterative algorithm that at each iteration solves the problem (4) with only a subset N 0 of all possible demand scenarios to obtain a solution y * ∈ N |T | . Then, the iterative algorithm solves another separation problem, described below, to check if there is a demand scenario n * ∈ N for which no feasible assignment of the items to the ordered bins corresponding to y * can be found (a violated demand scenario). If such a violated scenario n * ∈ N exists, then n * is appended to the set N 0 and an iteration is repeated. Otherwise, the problem is solved. This method is referred to as a row and column generation (RCG) algorithm, as each iteration adds variables x(n * ) ij , for all i ∈ S and j ∈ T , and associated constraints (4b)-(4c) to problem (4).

A variant of the general RCG method is a row generation (RG) algorithm. RG solves the problem in the yspace (initially with an empty set of the some of the constraints of formulation (4)), and at each iteration a cut violated by the current solution y * is appended to the formulation. These two algorithms have been previously introduced for two-stage robust optimization in [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF] and [START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF]. We now propose how to determine a violated demand scenario n * ∈ N and corresponding cut at each iteration where (4) is solved, with N replaced by some N 0 ⊆ N .

For a given solution y * ∈ N |T | and demand scenario n ∈ N , the ordered bins corresponding to y * can satisfy the demand vector n if and only if the following problem has a zero optimal objective value,

min i∈S α i (5a) s.t. α i + j∈T (i) x ij ≥ n i ∀i ∈ S (5b) i∈S(j) x ij ≤ V j y * j ∀j ∈ T (5c)
x ≥ 0, α ≥ 0 By linear programming duality, the optimal solution of problem (5) has the same objective value as the dual problem,

max i∈S n i π i -µ j V j y * j (6a) s.t. π i -µ j ≤ 0 ∀i ∈ S, ∀j ∈ T (i) (6b) π i ≤ 1 ∀i ∈ S (6c) π, µ ≥ 0.
Thus, to check if a given solution y * can cover all demand vectors in N , we can solve problem (6) individually for every demand n ∈ N . It may be possible only if N is finite. Alternatively, n ∈ N can be incorporated in the formulation as a vector of decision variables, resulting in a (nonconvex) quadratic program in the decision variables n, π, and µ,

w * ≡ max i∈S n i π i -µ j V j y * j (7a) s.t. π i -µ j ≤ 0 ∀i ∈ S, ∀j ∈ T (i) (7b) π i ≤ 1 ∀i ∈ S (7c) n ∈ N (7d) π, µ ≥ 0.
Let n * , π * , µ * denote an optimal solution to (7).

Lemma 2. A bin vector y ∈ N |T | is feasible for (4) if and only if

w * = i∈S n * i π * i -µ * j V j y j ≤ 0. ( 8
)
Proof. If i∈S n * i π * i -µ * j V j y j ≤ 0, then it implies that the optimal objective value of ( 6) is non-positive for all n ∈ N . Then, y is feasible for (4) together with some x(n) ≥ 0, for each n ∈ N . Otherwise w * > 0, implying that n * is a scenario in which, for all x(n * ), y is infeasible for (4). 2

If w * > 0, then n * is used a violated scenario for RCG (to be appended to the formulation) while ( 8) is a violated valid inequality that can be used with RG. The finite convergence of both methods is established by the following proposition. Proposition 3. Algorithms RG and RCG converge in a finite number of iterations.

Proof. Following Lemma 2, each iteration either accepts a solution y * (of (4) with N 0 in place of N ) or rejects it because w * > 0, in which case either the inequality (8), or the set of variables and constraints associated to violated scenario n * (RCG), are appended to the formulation. In either case, the previous solution y * is no longer feasible for the problem. Then, note that a solution y that is optimal to (4) (together with some x) must satisfy for each j ∈ T , y j ≤ max n∈N ||n|| 1 . Hence, at most a finite number of candidate solutions y * is enumerated by each of the algorithms. 2

Budgeted uncertainty set

Quadratic program ( 7) is nonconvex and accordingly it is hard to solve exactly in general. For some polytopes, problem (7) can be reformulated as a MILP that may be tractable to solve in practice. This is the case, for instance, when considering the following polytope

N Γ = n ∈ N |S| ∃z ∈ [0, 1] |S| : ∀i∈S:ni=ni+nizi, i∈S zi≤Γ ,
where n i represents the nominal demand for item type i, ni the maximum possible deviation of the demand from n i , and Γ > 0 is a parameter that controls the desired level of protection or immunity. The quadratic objective function (7a) can be rewritten in this case as i∈S

(n i + ni z i )π i -µ j V j y * j = i∈S n i π i + i∈S ni z i π i -µ j V j y * j , (9)
where only the second term is (bilinear) quadratic. One readily verifies (see for example [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF] for details) that there exists an optimal solution to (7) with N = N Γ , for integer Γ, that satisfies z ∈ {0, 1} |S| . Therefore, we can linearize the product z i π i , for each i ∈ S, by introducing auxiliary variable η i and the constraints

η i ≤ z i , η i ≤ π i , η i ≥ π i + z i -1. Notice that N Γ satisfies N Γ ⊆ N Γ+1 (10)
Further, for integer Γ the number of nondominated extreme points of N Γ is equal to the number of subsets of S of cardinality Γ. Thus, the number of non-dominated extreme points of N Γ is the binomial coefficient |S| Γ . In particular, if Γ = 0, or Γ = |S|, then N Γ contains one nondominated extreme point, either n or n + n, respectively.

Numerical experiments

In our numerical experiments we considered randomly generated instances given the parameters c min > 0, c max > c min , V min > 0, V max > V min and p ∈ (0, 1). For each bin type j ∈ T we draw its cost c j and its size V j , uniformly from the intervals [c min , c max ] and [V min , V max ], respectively. For every item type i ∈ S, it is set to be in S(j), for each j ∈ T , with a probability p. We consider a demand uncertainty polytope N Γ , generating n i and ni uniformly from an intervals [n min , n max ] and [n min , nmax ], respectively, for parameters n min , n max , nmin , nmax .

Table 1 reports average numerical results obtained for 10 instances generated for the parameter values |S| = 10, |T | = 15, c min = 1, c max = 10, V min = 1, V max = 10, p = 0.5, n min = 1, n max = 10, nmin = 1, nmax = 10. We solved the instance for all possible values of Γ. It can be observed that, following the inclusion (10), the objective value of the optimal solution increases in Γ. The results of Table 1 indicate, unsurprisingly, that the extreme cases Γ = 0 and Γ = 10 are easiest to solve. It can also be observed that the solution time of the RG method exceeds that of the RCG method. It can be expected since the RCG algorithm appends more information to the master problem (violated scenarios including both rows and columns) at each iteration, compared with the RG algorithm that may append only violated cuts.

ONGOING AND FUTURE WORK

In the current paper we considered the robust two-stage bin packing problem focusing on the uncertainty of the number of items of different item types. For the special case of unit item sizes we proved closed-form solutions for the optimal solutions. These closed-form solutions provide insight and show that a large number of multipurpose bins is used to address the uncertainty compared to the deterministic case in which at most a single multipurpose bin is used. We developed an algorithm for the two size model for polyhedral or finite item number uncertainty (scenario) sets. The algorithm that we propose is polynomial in the number of items. In future work we are considering algorithms that scale logarithmically in the number of items and linearly in the number of nondominated scenarios. We also plan to extend the row and column generation scheme developed for arbitrary type compatibility structures for an even more general setting with arbitrary item sizes.

Fig. 1 .

 1 Fig. 1. Two item types and three bin types illustrated for shipping of medicine and vaccines that require refrigeration and freezing, respectively.

Table 1 .

 1 Numerical comparison of RG and RCG on randomly generated instances.

	Γ	0	1	2	3	4	5	6	7	8	9	10
	Cost	77.5 108.8 118.9 126.4 132.1 136.7 139.8 141.9 144	145 145.6
	Time RCG (s)	0.9	2.6	3.2	4.6	3.2	3.1	2.7	2.2	2.7	1.7	0.7
	Iterations RCG	2.0	4.0	4.4	4.7	4.4	4.2	3.7	3.2	3.1	2.9	2.0
	Time RG (s)	6.4	12.8	12.5	11.6	10.4	9	7.6	7.2	6.7	6.1	6.2
	Iterations RG	11.6	13.4	13	12.2	11.2	10.9	10.1	12.2	10 10.2	10.9

, and y * must be optimal since y * 2 + y * 3 is the minimum number of bins required to store the type 2 items. 2

The following proposition establishes that an optimal solution and optimal solution value are given by closed-form solutions. Note that we may assume 1 < β without loss of generality (otherwise we may use only multipurpose or designated bins, respectively), in addition to the assumption in Section 1 that 1 ≤ α ≤ β < 1 + α. Proposition 2. Suppose that 1 < β < α + 1. The optimal objective value of (3) is attained with some y * such that

. Further, the optimal objective value

Proof. Following Lemma 1 the optimal objective value of ( 3) is given by the minimum of f over the integers. Note that the function f is continuosly differentiable over 0,

For

For

, ∞ , by our assumption on β it follows that df dy1 (y 1 ) = 1 -β + α > 0. It follows that f is increasing over

∈ arg min y1≥0 f (y 1 ). Since y * 1 ∈ N ⊆ R + it must also be that y * 1 ∈ arg min y1∈N f (y 1 ). 2

It follows that in the unit size case only the three scenarios corresponding to n max 1 , n max 2 and n max need to be considered. This also applies to infinite uncertainty sets N such as in the following example. Example 1. Consider an example where N is an ellipsoid

In particular, for a circle (b 1 = b 2 = 1) this gives n 1 = n 2 = r/ √ 2, and solving the problem for the circle-uncertainty set reduces to solving the problem with a set of three scenarios {(r, 0), (0, r), (r/ √ 2, r/ √ 2)} (although there are points of the circle that are not convex combinations of these 3 points). Then, z * = β 2 r V -