Luis Marques

François Clautiaux

Aurélien Froger

Mathematical models based on decision hypergraphs for designing a storage cabinet

Keywords: Cutting and Packing, Integer linear programming, Temporal knapsack, Arc flow models, Decision hypergraphs

We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to design a set of shelves, a set of compartments in each shelf and to select the items to be inserted into the compartments. The objective is to maximize the sum of the profits of the selected items. We call our problem the Storage Cabinet Physical Design (SCPD) problem. The SCPD problem combines a two-dimensional guillotine cutting problem for the design of the shelves and compartments with a set of temporal knapsack problems for the selection and assignment of items to compartments. We formalize the SCPD problem and formulate it as a maximum cost flow problem in a decision hypergraph with additional linear constraints. To reduce the size of this model, we break symmetries, generalize graph compression techniques and exploit dominance rules for precomputing subproblem solutions.

We also present a set of valid inequalities to improve the linear relaxation of the model. We empirically show that solving the arc flow model with all our enhancements outperforms solving a compact mixed integer linear programming formulation of the SCPD problem.

Introduction

In this article, we study the strategic problem of the internal physical design of a storage cabinet. We focus on the design of pull-out compartments within a cabinet of a given size. For this purpose, we are given stock entry and exit dates for a set of (representative) items, which may come from historical or forecast data. We assume that the cabinet may be undersized for the items that are candidates for storage over time. We must therefore decide the selection of the items to be stored so as to maximize their profit contribution (a measure of their total utility) and, where appropriate, their allocation to a compartment. As the contents of the compartments are supposed to slide (or be pushed by a mechanism) forward when opened, the items must be the same width as the compartment in which they are stored. We aim to mathematically model and solve this problem.

Our problem is inspired by a real-life application involving inner-city pharmacies that use an automatic under-the-counter storage and retrieval cabinet for the most common drugs. A related application is in small retail stores, where a storage cabinet can be installed close to the counter and store the most popular products, while the others are stored in the backroom. Here we tackle a simplified version of such problems as a first step towards optimizing such systems.

problem an arc flow formulation originally developed for its one-dimensional version [START_REF] Valério De Carvalho | Exact solution of bin-packing problems using column generation and branchand-bound[END_REF] and introduce reduction criteria to reduce the size of the graph on which an arc flow formulation is constructed.

The TKP is more recent, but there exist several exact methods, based on integer programming and dynamic programming [START_REF] Caprara | Uncommon dantzig-wolfe reformulation for the temporal knapsack problem[END_REF][START_REF] Bartlett | The Temporal Knapsack Problem and Its Solution[END_REF][START_REF] Gschwind | Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities[END_REF][START_REF] Caprara | Solving the temporal knapsack problem via recursive dantzig-wolfe reformulation[END_REF][START_REF] Clautiaux | An iterative dynamic programming approach for the temporal knapsack problem[END_REF]. [START_REF] Clautiaux | An iterative dynamic programming approach for the temporal knapsack problem[END_REF] solved the TKP exactly using an iterative refinement method called successive sublimation dynamic programming. The problem is formulated as a dynamic program of exponential size and relaxations of the problem are obtained by projecting the formulation into lower-dimensional state spaces whose size is increased until the resulting solution satisfies the constraints of the original problem.

In this paper, we focus on mixed integer linear programming (MILP) formulations, and in particular on arc flow reformulations in decision hypergraphs. Arc flow formulations are increasingly popular in the field of cutting and packing problems since their first successful use [START_REF] Valério De Carvalho | Exact solution of bin-packing problems using column generation and branchand-bound[END_REF]. Such formulations are known to provide good linear relaxations for combinatorial problems and can be solved directly by a general purpose MILP solver. We refer to de [START_REF] De Lima | Arc Flow Formulations Based on Dynamic Programming: Theoretical Foundations and Applications[END_REF] for a thorough survey about arc flow formulations where the networks are derived from state transition graphs associated with dynamic programs. [START_REF] Martin | Polyhedral Characterization of Discrete Dynamic Programming[END_REF] studied arc flow formulations in decision hypergraphs. These latter are derived for problems formulated as dynamic programs in which decisions combine partial solutions (i.e., multiple states) into a single solution (i.e., a single state). [START_REF] Arenales | An AND/OR-graph approach to the solution of two-dimensional nonguillotine cutting problems[END_REF] implicitly used such formulations to solve two-dimensional non-guillotine cutting problems, but the name and-or graph replaces the term hypergraph. They detail an algorithm for constructing an and-or graph by studying specific structures of the solutions to the studied problem, develop reduction methods to restrict the solution space and develop a branch-and-bound algorithm to compute an optimal solution. [START_REF] Clautiaux | Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem[END_REF] explicitly used an arc flow formulation in a decision hypergraph to solve a two-dimensional four-stage guillotine cut bounded knapsack problem. They show how dynamic programming-based techniques such as Lagrangian filtering techniques and state-space relaxation designed for graphs can be extended to The size of arc flow formulations is generally the bottleneck when solving them directly with a MILP solver. Several techniques have been used in the literature to address this issue. [START_REF] Brandão | Bin packing and related problems: General arc-flow formulation with graph compression[END_REF] proposed so-called graph compression techniques, which exploit the structure of the problem to reduce the number of arcs and vertices in the network. Similar ideas have been used in the field of decision diagrams for years (see e.g. [START_REF] Castro | Decision Diagrams for Discrete Optimization: A Survey of Recent Advances[END_REF]).

We now outline the main original contributions of this paper:

• We formulate a relaxation of the SCPD problem as a dynamic program. We derive a decision hypergraph from this dynamic program and reformulate the SCPD problem as a maximum cost flow problem with additional constraints to ensure feasibility. This leads us to the introduction of an arc flow formulation of the problem.

• We introduce valid inequalities to strengthen the arc flow formulation.

• To reduce the size of the formulation, we extend existing graph compression techniques to the case of hypergraphs, and propose new ones to detect and exploit the presence of subproblems whose solutions can be easily computed in a preprocessing phase.

• We empirically demonstrate on randomly generated instances the advantages of solving the arc flow formulation over a compact MILP formulation. We first observe that the results obtained by solving the arc flow formulation without any graph reduction or valid inequalities are not competitive with those obtained by solving the compact formulation. By strengthening the linear relaxation of the arc flow formulation, reducing the size of the decision hypergraph and breaking certain symmetries, 25 more instances (out of 180) are optimally solved compared to the compact MILP formulation and the average gap is 4.38% versus 6.32%.

The rest of this paper is organized as follows. In section 2 we formally define the SCPD problem, describe some of its properties, and present a compact MILP formulation. In section 3 we introduce an arc flow formulation of the SCPD problem. In section 4 we describe several improvements to the arc flow formulation that help to keep its size tractable. In section 5 we present how we generated our instances and the results of our computational experiments. In section 6, we offer a few brief concluding remarks.

Problem definition

In this section, we give a formal definition of the problem, state some of its properties, and formulate it as a compact MILP model.

Let (H max , W max , L max ) be a storage cabinet with height H max ∈ N, width W max ∈ N and length L max ∈ N.

Let I be a set of items. Each item i ∈ I has a height h i ∈ N, a width w i ∈ N, a length ℓ i ∈ N, a profit p i ∈ R + and a time interval [s i , s i + d i ) with s i ∈ N and d i ∈ N * , during which the item, if selected, is present in the cabinet. We denote by T = ∪ i∈I {s i , s i + d i } the set of time steps to be considered.

In the problem, we define a shelf ψ as a three-dimensional rectangular object of size (h ψ , W max , L max ), where h ψ ≤ H max , and we define a compartment ϕ as a three-dimensional rectangular object of size (h ϕ , w ϕ , L max ), where h ϕ ≤ H max , w ϕ ≤ W max .

A solution to the problem is characterized by a set of shelves, a set of compartments, an assignment of the compartments to the shelves, and an assignment of a subset of items to the compartments. In the problem, we restrict items to be assigned only to compartments with exactly the same width. This constraint stems from a technical feature of the storage device. To retrieve an item, it is pushed along its compartment. If its width is less than that of the compartment, the item would rotate, which could block the mechanism.

For the sake of clarity and precision, we formalize the decision and optimization versions of the problem.

Problem 1 (Storage Cabinet Physical Design decision problem (SCPD-Decision problem)). Given (H max , W max , L max ), I, B with B ∈ R + , the Storage Cabinet Physical Design decision (SCPD-Decision) problem is formulated as follows: is there (Ψ, Φ, I ′ , µ, ρ), where Ψ is a set of shelves, Φ a set of compartments, I ′ ⊆ I a subset of items, µ : Φ → Ψ a mapping of the compartments to the shelves, and ρ : I ′ → Φ a mapping of the selected items to the compartments, which satisfy the following six conditions? 1. The total profit of the items in

I ′ is at least B. i∈I ′ p i ≥ B
2. The sum of the heights of the shelves in Ψ is less than or equal to H max . ψ∈Ψ h ψ ≤ H max 3. A compartment ϕ is assigned to a shelf µ(ϕ) whose height is greater than or equal to its height.

∀ϕ ∈ Φ, h ϕ ≤ h µ(ϕ)
4. For each shelf ψ, the sum of the widths of the compartments assigned to ψ is less than or equal to W max . ∀ψ ∈ Ψ, ϕ∈Φ:µ(ϕ)=ψ w ϕ ≤ W max 5. For each compartment ϕ, the items assigned to ϕ have a height less than or equal to the height of ϕ and a width equal to the width of ϕ.

∀ϕ ∈ Φ, i ∈ I ′ , h i ≤ h ρ(i) and w i = w ρ(i)
6. For each compartment ϕ and each time step t, the sum of the lengths of the items in ϕ at t is less than We prove that the SCPD-Decision problem is NP-hard by polynomially reducing the Temporal Knapsack decision problem (Problem 3), known to be NP-hard in the strong sense [START_REF] Bonsma | A constant-factor approximation algorithm for unsplittable flow on paths[END_REF], to it.

or equal to L max . ∀t ∈ T , ∀ϕ ∈ Φ, i∈I ′ :ρ(i)=ϕ,si≤t<si+di ℓ i ≤ L max

Problem 3 (Temporal Knapsack decision problem (TK-Decision problem)

). An instance of the Temporal Knapsack decision (TK-Decision) problem is a tuple (C, J , B) where C ∈ N is the capacity of the knapsack, J is a set of items, and B ∈ R + . Each item j ∈ J has a weight w j ∈ N, a profit p j ∈ R + and a time interval [s j , s j +d j ) with s j ∈ N and d j ∈ N, during which, when selected, it is present in the knapsack. Given (C, J , B), the TK-Decision problem is formulated as follows: is there J ′ ⊆ J such that the following two conditions are satisfied? (i) At each time step, the sum of the weights of the items assigned to the knapsack in that time step is less than or equal to C.

∀t ∈ j∈J ′ {s j , s j + d j }, j∈J ′ :sj ≤t<sj +dj w j ≤ C (ii)
The sum of the profits of the items assigned to the knapsack is at least B.

j∈J ′ p j ≥ B
Proposition 1 (NP-hardness of the SCPD-Decision problem). The SCPD-Decision problem is NP-hard in the strong sense.

Proof. The TK-Decision problem is polynomially reducible to the SCPD-Decision problem. To reduce an instance (C, J , B) of the TK-Decision problem to an instance (H max , W max , L max ), I, B of the SCPD-Decision problem, take (H max , W max , L max ) = (1, 1, C), B = B and construct I as follows: for each item j ∈ J , create an item i ∈ I with attributes h i = 1, w i = 1, l i = w j , p i = p j , s i = s j , and

d i = d j .
Let us now discuss a restriction of the solution space. Dominance rule 1 states that it is never useful to build shelves that have a height greater than all the items it can contain. It is easy to see that, since items do not stack vertically, the space between the highest item a shelf can contain and the top of the shelf is wasted space in any solution.

Dominance rule 1. There exists an optimal solution to the SCPD problem such that the height of each shelf built in the cabinet is equal to the height of an item.

We now introduce a compact MILP model for the SCPD problem. Thanks to Dominance rule 1, we do not need to consider all possible shelf heights, and thus restrict ourselves to heights equal to those of the items.

By definition, the width of a compartment is always the width of an item. In our formulation, the creation of shelves and compartments is modelled using representative items. For i ∈ I, the binary variable z i is equal to 1 if a shelf is represented by item i, meaning it has height h i , 0 otherwise. Each binary variable y i,j is equal to 1 if a compartment in the shelf represented by i is represented by item j, meaning it has width w j , 0 otherwise. Finally, each binary variable x j,k is equal to 1 if the item k ∈ I is assigned to the compartment represented by j, 0 otherwise. We define the sets

I ≤h = {i ∈ I : h i ≤ h}, I ≤h,w = {i ∈ I : h i ≤ h, w i = w}
and I h,w = {i ∈ I : h i = h, w i = w} as the set of items with a height less than or equal to h, the set of items with a height less than or equal to h and a width equal to w, and the set of items with a height equal to h and a width equal to w, respectively. The MILP model is as follows: maximize j∈I k∈I ≤h j ,w j

p k x j,k (1a)
subject to

i∈I h i z i ≤ H max (1b) j∈I ≤h i w j y i,j ≤ W max i ∈ I (1c) k∈I ≤h j ,w j : s k ≤t<s k +d k ℓ k x j,k ≤ L max j ∈ I, t ∈ T (1d) j∈I: k∈I ≤h j ,w j x j,k ≤ 1 k ∈ I (1e) x j,k ≤ x j,j j ∈ I, k ∈ I ≤hj ,wj (1f)
x j,j = i∈I j∈I ≤h i y i,j j ∈ I (1g)

y i,j ≤ z i i ∈ I, j ∈ I ≤hi (1h) y i,i = z i i ∈ I (1i) z i ∈ {0, 1} i ∈ I (1j) y i,j ∈ {0, 1} i ∈ I, j ∈ I ≤hi (1k) x j,k ∈ {0, 1} j ∈ I, k ∈ I ≤hj ,wj (1l)
The objective function in (1a) is the total profit of the selected items. Constraint (1b) ensures that the sum of the heights of the shelves does not exceed the height of the cabinet. Constraints (1c) ensure that the sum of the widths of the compartments in a shelf does not exceed the width of the cabinet. Constraints (1d) state that the sum of the lengths of the items in a compartment does not exceed the length of the cabinet with respect to the time steps at which the items are present. Note that it is sufficient to add this constraint only for the time steps when new items enter the compartment. Constraints (1e) ensure that each item is assigned to no more than one compartment. Constraints (1f) and (1g) ensure that an item is assigned to a compartment only if that compartment is created and that the item representing that compartment is assigned to it. Constraints (1h) and (1i) ensure that a compartment is created in a shelf only if that shelf is created and that the item representing the shelf represents one of the compartments built into the shelf. Constraints (1j)-(1l) require the variables to be binary.

An hypergraph-based reformulation

In this section, we propose an arc flow model for the SCPD problem based on its reformulation as a maximum cost flow problem with additional constraints. We use the following methodology. We formulate a relaxation of the SCPD problem as a dynamic program in §3.1. This dynamic program defines a decision hypergraph [START_REF] Martin | Polyhedral Characterization of Discrete Dynamic Programming[END_REF] which we use in §3.2 as the network on which we derive an arc flow formulation of the SCPD problem.

A dynamic program

We first propose a dynamic program to model the relaxation of the SCPD problem where each item can be assigned to more than one compartment. This corresponds to relaxing constraints (1e) in the MILP model (1).

We use a classical dynamic programming formalism where states represent partial solutions, and decisions represent the possible extensions of a partial solution. Unlike the classical case, where a decision from one state leads to another state, here a decision can lead to several states at once. In the problem we are modelling, there are several types of decisions: creating a shelf, creating a compartment, selecting an item. We define three stages in our problem and each state belongs to one of them. In a stage 1 state, a decision corresponds to building a shelf in the cabinet and leads to a stage 2 state and a residual stage 1 state. In a stage 2 state, a decision corresponds to building a compartment in the shelf and leads to a stage 3 state and a residual stage 2 state. In a stage 3 state, a decision corresponds to selecting an item to enter or leave the compartment and leads to another stage 3 state. Figure 3 shows decisions made from stage 1 and stage 2 states. We introduce our dynamic program in a bottom-up fashion, from stage 3 to stage 1. For each stage, we first describe the information needed to express a state. We then present a recursive formulation to compute the maximum profit that can be obtained from the current state by making decisions leading to the initial states of the dynamic program. We define H = {h : ∃i ∈ I, h i = h} as the set of possible shelf heights and, for each h ∈ H, W h = {w : ∃i ∈ I, h i ≤ h, w i = w} as the set of possible compartment widths. The union of each possible compartment width is noted W = ∪ h∈H W h .

In stage 3, each state is associated with a compartment of a given height h ∈ H and width w ∈ W h . Once the height and width of a compartment have been decided (we recall that all compartments have a length equal to L max ), the problem restricted to this compartment is a TKP. [START_REF] Martinovic | A combinatorial flow-based formulation for temporal bin packing problems[END_REF] and [START_REF] Clautiaux | An iterative dynamic programming approach for the temporal knapsack problem[END_REF] presented two formulations of TKP as a dynamic program. If no compression or reduction is applied, the former leads to fewer states. However, our recursive formulation for stage 3 is an adaptation of the latter, as it allows us to make better use of the preprocessing and symmetry breaking techniques described in Section 4.

It is an event-based formulation. Specifically, we define two events for each item i ∈ I, one when i can be selected at time step s i to enter the compartment and one when i leaves the compartment at time step

s i + d i if present inside. Let E = (0, 1, . . . , 2|I|
) be an ordered list of events where 0 represents a dummy event signalling the start of the time horizon. We define E in ⊂ E (resp. E out ⊂ E) as the subset of events related to the start (resp. end) of a time interval associated with an item. For each event e ∈ E, we denote by i(e) ∈ I the item to which the event relates and by t(e) the time step at which it occurs, i.e. t(e) = s i(e) if e ∈ E in and t(e) = s i(e) + d i(e) if e ∈ E out . The events in E in ∪ E out are ordered from 1 to 2|I| as follows: e 1 < e 2 if t(e 1 ) < t(e 2 ) or t(e 1 ) = t(e 2 ) ∧ e 1 ∈ E out ∧ e 2 ∈ E in . For a compartment with height h and width w, we denote by E h,w = {e ∈ E : h i(e) ≤ h, w i(e) = w} the events associated to items that can be assigned to it. We also note E * h,w the last event of a compartment of height h and width w. For each event e ∈ E h,w , we denote by E - h,w (e) the event preceding e in E h,w , i.e. E - h,w (e) = max{ẽ : ẽ < e : w i(ẽ) = w, h i(ẽ) ≤ h}. The information needed to make decisions from a stage 3 state is the height h ∈ H of the compartment, its width w ∈ W h , its available length L ∈ {0, . . . , L max }, the current event e ∈ E, and the set of items currently in the compartment, represented as a binary vector q of size |I|. A stage 3 state is thus denoted by (h, w, L, e, q).

In the remainder, α 3 (h, w, L, e, q) is the maximum profit that can be obtained from a stage 3 state (h, w, L, e, q) by making decisions that lead to the initial stage 3 state (h, w, L max , 0, 0). In other words, α 3 (h, w, L, e, q) is the maximum profit that can be obtained by selecting items to be inserted in the compartment up to event e.

Note that the profit associated with an item is only earned when it leaves the compartment. Denoting ε k the characteristic vector of the subset {k} of the underlying set I, the forward recursion is as follows:

α 3 (h, w, L, e, q) =                            0 if e = 0 α 3 (h, w, L, E - h,w (e), q) if e ∈ E in ∧ q i(e) = 0 α 3 (h, w, L + ℓ i(e) , E - h,w (e), q -ε i(e) ) if e ∈ E in ∧ q i(e) = 1 ∧ L + ℓ i(e) ≤ L max max    p i(e) + α 3 (h, w, L -ℓ i(e) , E - h,w (e), q + ε i(e) ), α 3 (h, w, L, E - h,w (e), q)    if e ∈ E out ∧ q i(e) = 0 ∧ L ≥ ℓ i(e) α 3 (h, w, L, E - h,w (e), q) if e ∈ E out ∧ q i(e) = 0 ∧ L < ℓ i(e) (2)
Five cases are considered in the above formula. The first case is the dummy event and the profit is set to 0 because we are at the beginning of the time horizon. The second and third cases involve a state associated with an ingoing event e, and the decision whether or not to insert i(e) into the compartment has already been made. The fourth and fifth cases involve a state associated with an outgoing event e, and the item i(e) has already left the compartment if it was present.

In stage 2, only the height of the current shelf and its width are needed to decide which compartments to build. A stage 2 state is thus denoted by (h, W ), where h ∈ H and W ∈ {0, . . . , W max }. We denote by α 2 (h, W )

the maximum profit that can be obtained from a stage 2 state (h, W ) making decisions that lead to initial stage 3 states (h, w, L max , 0, 0) with w ≤ W . In other words, α 2 (h, W ) is the maximum profit that can be obtained by building compartments into a shelf with height h, width W , and length L max . We set α 2 (h, W ) = 0 if there is no item with height less than or equal to h or width less than or equal to W . The forward recursion is as follows:

α 2 (h, W ) = max w∈W h ,w≤W α 3 (h, w, L max , E * h,w , 0) + α 2 (h, W -w) (3)
In stage 1, each state only requires the height available in the cabinet for building shelves. A stage 1 state is denoted by (H), where H ∈ {0, . . . , H max }. We denote by α 1 (H) the maximum profit that can be obtained from a stage 1 state (H) making decisions that lead to initial stage 3 states (h, w, L max , 0, 0) with h ≤ H and w ≤ W max . In other words, α 1 (H) is the maximum profit that can be obtained by building shelves into a cabinet of height H , width W max , and length L max . We set α 1 (H) = 0 if there is no item of height less than or equal to H. The forward recursion is as follows:

α 1 (H) = max h∈H,h≤H {α 2 (h, W max ) + α 1 (H -h)} (4)
The optimal value of the relaxation of the SCPD problem defined at the beginning of this section is

α 1 (H max ).
The time and space complexity of computing this value is exponential in the worst case, because the maximum number of stage 3 states is exponential in the input size (the vector q can take at most 2 |I| values).

However, if the number of items of the same width that can be simultaneously present in a compartment is not large, the total number of states in the dynamic program remains tractable.

An hypergraph representation and an arc flow formulation

We now introduce the so-called decision hypergraph associated with the dynamic program defined by the recursive formulae ( 2), (3), and (4). We use this hypergraph representation to build an arc flow formulation of the SCPD problem. Using the vocabulary and notations of [START_REF] Martin | Polyhedral Characterization of Discrete Dynamic Programming[END_REF], a decision hypergraph is the generalization of a directed acyclic graph and consists of a set of vertices and a set of decision hyperarcs (hyperarcs in the remainder). In [START_REF] Martin | Polyhedral Characterization of Discrete Dynamic Programming[END_REF] , an hyperarc is a triple (F, v, p), where F is a multiset of vertices called the tail of the hyperarc, v is a vertex called the head of the hyperarc, and p is a profit. To avoid unnecessarily heavy notations, we consider that F is a set of vertices instead of a multiset. In an hypergraph representation of a dynamic program, the vertices are the states of the dynamic program and the hyperarcs symbolize the decisions. Specifically, each hyperarc (F, v, p) represents the transition from the states at its tail to the state at its head.

For illustration purposes, the recursive formula (4) for a given H ∈ {0, . . . , H max } leads to an hyperarc with a zero profit for each h ∈ H such that h ≤ H where the two vertices at its tail represent the stage 2 state (h, W max ) and the stage 1 state (H -h), and the vertex at its head represents the stage 1 state (H).

Similarly, the recursive formula (3) for given values of h ∈ H and W ∈ {0, . . . , W max } leads to an hyperarc with zero profit for each w ∈ W h such that w ≤ W where the two vertices at its tail represent the stage 3 state (h, w, L max , E * h,w , 0) and the stage 2 state (h, W -w), and the vertex at its head represents the stage 2 state (h, W ). Finally, the recursive formula (2) gives rise to hyperarcs with a tail of cardinality one. Among these hyperarcs, the one carrying to decision of an item leaving a compartment have a profit equal to the profit of the item. There is a unique vertex with no successor, called sink, which corresponds to the final state (H max ) of the dynamic program. We assume that there also exists a vertex called source with no predecessor. For this purpose, each vertex associated with a stage 3 state (h, w, L max , 0, 0) is the head of an hyperarc with the source as the tail. The decision hypergraph is built recursively from the sink to the source. Algorithm 1 describes the creation procedure. It starts from the final state represented by the sink of the hypergraph, and recursively adds vertices and hyperarcs using the recursive formulas (2)-( 4). Note that we do not create vertices associated with stage 1 and stage 2 states from which no feasible decision can be taken (above we have explicitly set the maximum profit associated with these states to 0). Each feasible solution to the problem being modelled by the decision hypergraph corresponds to a flow (from the source to the sink) whose quantity arriving at the sink is one and whose value is the total cost of Algorithm 1: Generating the decision hypergraph associated with the dynamic program defined by the recursive formulas ( 2)-( 4)

Input: An SCPD instance (Hmax, Wmax, Lmax), I Output: The decision hypergraph associated with the dynamic program applied to the given instance

1 V ← {v + , (Hmax)} ;
// set of vertices of the hypergraph

2 A ← ∅ ; // set of hyperarcs 3 S 1 ← {(Hmax)} ;
// stage 1 states to process 4 S 2 ← ∅ ; // stage 2 states to process 5 S 3 ← ∅ ; // stage 3 states to process

6 while S 1 ̸ = ∅ do 7 v = (H) ← element of S 1 that maximizes H ; 8 S 1 ← S 1 \ {v} ; 9
Apply Algorithm 2 with (Hmax, Wmax, Lmax), I , v, S 1 , S 2 , and (V, A) as inputs ;

while S 2 ̸ = ∅ do v = (h, W ) ← element of S 2 that maximizes lexicographically h and W ; S 2 ← S 2 \ {v} ;
Apply Algorithm 3 with (Hmax, Wmax, Lmax), I , v, S 2 , S 3 , and (V, A) as inputs ;

while S 3 ̸ = ∅ do v = (h, w, L, e, q) ← element of S 3 that maximizes lexicographically h, w, e ; S 3 ← S 3 \ {v} ;
Apply Algorithm 4 with (Hmax, Wmax, Lmax), I , v, S 3 and (V, A) as inputs ;

Algorithm 2: Create the decision hyperarcs incoming to a vertex associated with a stage 1 state

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 1 state v = (H), two sets S 1 and S 2 , an hypergraph (V, A)

Result: Creates the hyperarcs incoming to v, updates V, A, S 1 , S 2

1 for h ∈ H, h ≤ H do 2 v1 ← (h, Wmax) ; // generate a stage 2 state 3 S 2 ← S 2 ∪ {v1}, V ← V ∪ {v1}, F ← {v1} ; 4 if ∃i ∈ I, hi ≤ H -h then 5 v2 ← (H -h) ; // generate a stage 1 state 6 S 1 ← S 1 ∪ {v2}, V ← V ∪ {v2}, F ← F ∪ {v2} ; 7 A ← A ∪ {(v, F, 0)} ; // create the hyperarc
Algorithm 3: Create the decision hyperarcs incoming to a vertex associated with a stage 2 state

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 2 state v = (h, W ), two sets S 2 and S 3 , an hypergraph (V, A)

Result: Creates the hyperarcs incoming to v, updates V, A, S 2 , S 3

1 for w ∈ W h , w ≤ W do 2 v1 ← (h, w, Lmax, E * h,w , 0) ; // generate a stage 3 state 3 S 3 ← S 3 ∪ {v1}, V ← V ∪ {v1},F ← {v1} ; 4 if ∃i ∈ I : hi ≤ h, wi ≤ W -w then 5 v2 ← (h, W -w) ; // generate a stage 2 state 6 S 2 ← S 2 ∪ {v2}, V ← V ∪ {v2}, F ← F ∪ {v2} ; 7 A ← A ∪ {(v, F, 0)} ; // create the hyperarc
Algorithm 4: Create the decision hyperarcs incoming to a vertex associated with a stage 3 state

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 3 state v = (h, w, L, e, q), a set S 3 , an hypergraph (V, A)

Result: Creates the hyperarcs incoming to v, updates V, A, S 3

1 if e = 0 then 2 A ← A ∪ {(v, {v + }, 0)} ;
// connect the source with this state Let G = (V, A) be the decision hypergraph where V is the set of vertices, A the set of hyperarcs, v + its source and v -its sink. We define A(i) as the set of hyperarcs associated with the exit of item i from a compartment (in which it was previously inserted). We denote by A -(v) (resp. A + (v)) the set of hyperarcs of which v ∈ V is the head (resp. of which v belongs to the tail). With a slight abuse of notation, for each hyperarc a ∈ A, we denote by p a its profit. It is equal to p i if a ∈ A(i) and to 0 otherwise. An arc flow formulation of the SCPD problem is as follows:

3 else if e ∈ E out then 4 v1 ← (h, w, L, E - h,w (e), q) ; // skipping the item 5 S 3 ← S 3 ∪ {v1}, V ← V ∪ {v1} ; 6 A ← A ∪ {(v, {v1}, 0)} ; // create the hyperarc 7 if L ≥ ℓ i(e) then 8 v2 ← (h, w, L -ℓ i(e) , E - h,w (e), q + ε i(e) ) ; // selecting the item 9 S 3 ← S 3 ∪ {v2}, V ← V ∪ {v2} ; 10 A ← A ∪ {(v,
S 3 ← S 3 ∪ {v1}, V ← V ∪ {v1} ; 17 A ← A ∪ {(v, {v1} ,
maximize a∈A p a x a (5a) subject to a∈A -(v)
x a -

a∈A + (v) x a = 0 v ∈ V \ {v + , v -} (5b) a∈A -(v -)
x a = 1 (5c)

a∈A(i) x a ≤ 1 i ∈ I (5d) x a ∈ N a ∈ A (5e)
The objective function in (5a) is the total profit obtained inserting items into the cabinet. Constraints (5b) model flow conservation, while constraint (5c) imposes that the quantity of flow received at the sink is one (there is a single cabinet in the problem). Constraints (5d) ensure that each item is assigned at most once in the cabinet. Constraints (5e) require that the arc variables are integer. Note that the flow of an hyperarc can be greater than one, as shelves and compartments of the same size can be built into the cabinet (but different items must be selected in each).

Remark 1. A solution to the arc flow formulation (5) is converted into a solution to the SCPD problem by iterating over the hyperarcs with non-zero flow value starting from the sink and tracking the assignment of compartments to shelves and items to compartments (see Algorithm 5 in §S.1 of the supplementary material).

To handle the case where a flow greater than one exits a vertex/state, we store pairs consisting of a stage 2 state and a shelf in L 2 , and pairs consisting of a stage 3 state and a compartment in L 3 . Without loss of generality, we assume that the shelves and compartments built with our procedure are placed in the cabinet from top to bottom and from left to right, respectively.

Table 1 describes an instance of the SCPD problem and Figure 4 shows the decision hypergraph associated with this instance, and, in blue, a feasible solution to the problem, i.e. a flow from the source to the sink. We recall that the hypergraph is built from the sink v -and the decisions to select an item to leave a compartment must be taken before the decisions to select the item to enter into it. To avoid overloading the figure, if the profit associated with an hyperarc is 0, then it is not explicitly indicated. The same applies to a flow with a value of 0. Figure 5 illustrates the storage cabinet physical design system associated with the solution.

H max W max L max 10 5 4 (5, 5)

i h i w i ℓ i p i s i d i 1 5 2 2 1 0 2 2 9 2 1 2 1 2
(5) (9, 5)

(5, 2, 4, 3, (0, 0))

(5, 3) (9, 2, 4, 4, (0, 0)) (9, 3)

1 1 1 v +
(5, 2, 2, 1, (1, 0))

(5, 2, 4, 1, (0, 0)) (5, 2, 4, 0, (0, 0)) (9, 2, 3, 3, (0, 1)) (9, 2, 4, 3, (0, 0))

(9, 2, 1, 2, (1, 1)) (9, 2, 3, 2, (0, 1)) (9, 2, 2, 2, (1, 0)) (9, 2, 4, 2, (0, 0)) (9, 2, 2, 1, (1, 0)) (9, 2, 4, 1, (0, 0)) (9, 2, 4, 0, (0, 0)) event 1 event 2 event 3 event 4 event 1 event 3 1 1 2 1 1 1 1 1 1 1 1 1 2 xa pa
event 4: decision to whether or not select item 2 to leave the compartment event 3: decision to whether or not select item 1 to leave the compartment event 2: decision to select item 2 to enter the compartment if present in it, or to not select it if not present event 1: decision to select item 1 to enter the compartment if present in it, or to not select it if not present The aim of this section is to describe improvements on the arc flow formulation (5). To strengthen the quality of its linear relaxation, we start by introducing valid inequalities in §4.1. Since the formulation is non-polynomial in the size of the instance, we describe in §4.2 to §4.4 symmetry breaking and graph compression techniques to reduce the number of hyperarcs in A. The modifications of Algorithm 1 to take into account all these latter improvements during the hypergraph generation procedure are given in §S.2 of the supplementary material.

We first define two optimization problems that some of our techniques have to solve and describe the notation that will be used throughout this section.

Problem 4 (Bin Packing (BP)). Suppose an infinite number of bins with capacity C ∈ N and let J be a set of items. Each item j ∈ J has a weight w j ∈ N. The BP problem is to find an assignment of the items to the bins such that (i) the sum of the weights of the items assigned to each bin is less than or equal to C, (ii) the number of bins to which at least one item is assigned is minimized.

Problem 5 (Temporal Bin Packing (TBP)). Suppose an infinite number of bins with capacity C ∈ N and let J be a set of items. Each item j ∈ J has a weight w j ∈ N and a time interval [s j , s j + d j ) with s j ∈ N and d j ∈ N, during which the item is present. The TBP problem is to find an assignment of the items to the bin such that (i) for each bin, the sum of the weights of the items simultaneously present in it is less than or equal to C, (ii) the number of bins to which at least one item is assigned is minimized.

We note z * BP(J ,C) (resp. z * TBP(J ,C) ) the value of an optimal solution to the BP (resp. TBP) problem with capacity C and set of items J . We recall that the sets I ≤h , I ≤h,w and I h,w are the set of items with a height less than or equal to h, the set of items with a height less than or equal to h and a width equal to w, and the set of items with a height equal to h and a width equal to w, respectively. Given a set of items J ⊆ I, we define h max (J ) = max j∈J {h j }. In the following, we abuse the notation z * TBP(J ,C) by denoting as z * TBP(I ≤h,w ,Lmax)

the value of an optimal solution to the TBP problem with capacity L max where the items are defined as follows:

for each i ∈ I ≤h,w , create an item with weight ℓ i and time interval [s i , s i + d i ).

A family of valid inequalities

Successful applications of arc flow models depend on the quality of the formulation obtained. In these cases, the value obtained by solving their linear relaxation is generally close to the optimum. For hypergraph-based arc flow formulations, some structures may weaken the quality of the relaxation. We illustrate one such structure below and propose a set of valid inequalities to eliminate it.

We want to address a problem that arises when a specific structure is met in the solution of the linear relaxation to (5). We illustrate this situation in Figure 6. We consider an instance with a cabinet of size

(2, 4, 1) and a single item with size (2, 1, 1). In this figure, there are 0.25 units of flow passing through the leftmost hyperarc, corresponding to the creation of a shelf with height 2. Then, four compartments with identical width equal to 1 are built iside this shelf and, due to flow conservation, there are 0.25 units of flow going through the corresponding rightmost hyperarcs. Then there is one unit of flow on the arc going out of the vertex associated with the stage 3 state. Although only "a quarter of a shelf" has been built, the item in our instance can be "entirely" selected in the compartment built inside this shelf. In a solution of the linear relaxation to (5), fractional units of flow are successively combined to form a whole unit of flow leaving vertices associated with stage 3 states, increasing the number of items selected and thus the total profit.

(2) The following inequalities prevent an item from being selected if no shelf has been built to hold it. We note Ã(h) the set of hyperarcs associated with the design of a shelf of height h ∈ H in the cabinet. These hyperarcs are those whose head is a vertex associated with a stage 1 state and whose tail includes a vertex associated with a stage 2 state (h, W max ).

v - (2, 4) (2, 3) (2, 2) (2, 1) (2, 1, 1, 2, (0)) (2, 1, 0, 1, (1)) (2, 1, 1, 1, (0)) (2, 1, 1, 0, ( 0
Proposition 2. For each item i ∈ I, the following inequality is valid for model (5):

a∈A(i) x a ≤ h∈H,h≥hi a∈ Ã(h)
x a (6)

Proof. First, note that in the model (5), we have a∈A(i) x a ≤ 1. In an integer solution, if a∈A(i) x a = 0, the inequality (6) holds due to the positivity of the variables. If a∈A(i) x a = 1 (i.e., item i is selected), then there must be an hyperarc ā ∈ Ã(h) with h ≥ h i such that x ā is equal to 1 (i.e., a shelf with height greater than h i should be built) . Therefore the inequality (6) holds in this case too.

The number of inequalities ( 6) is equal to the number of items in the instance. When we say later that we use these inequalities, this means that we add them all in the formulation (5). Note that the solution displayed in Figure 6 is eliminated because there is only 0.25 units of flow traversing the single hyperarc associated with the design of a shelf with height greater than or equal to the height of the item.

Pruning hyperarcs using dominance rules

In this section, we introduce dominance rules (see e.g., [START_REF] Jouglet | Dominance rules in combinatorial optimization problems[END_REF]), which we use to remove hyperarcs associated with design decisions (i.e., building shelves and compartments in the cabinet). We use the following methodology. We first state a dominance rule, i.e., a property that is satisfied by at least one optimal solution to the SCPD problem, and then describe how we modify the hypergraph creation to accommodate it.

We first introduce dominance rules 2 and 3 for the design of shelves within the cabinet.

Dominance rule 2.

There exists an optimal solution to the SCPD problem such that the shelves are ordered from top to down by non-decreasing height.

Dominance rule 2 is straightforward to exploit in a constructive approach: only shelves whose height is less than that of the shelves present in the partial solution can be built subsequently. In the hypergraph, a vertex associated with a given stage 1 state can be reached from the sink by different sequences of decisions (i.e., the vertex belongs to the tail of several hyperarcs), and thus the sets of shelves built in each of the corresponding partial solutions are different. This means that we cannot force all solutions of the arc flow formulation to satisfy the dominance rule 2. However, we partially enforce it by recording additional information at the vertices associated with stage 1 states and building their incoming hyperarcs considering these vertices in nonincreasing order of height. To each vertex v ∈ V associated with a stage 1 state, we attach an additional value c 1 (v, h) ∈ N for each height h ∈ H which is the minimum number of times an hyperarc corresponding to the creation of a shelf of height h must be traversed to reach the sink v -. Denoting h(v) the height of the stage 1 state represented by v, this value can be computed in a recursive way as follows:

c 1 (v -, h) = 0 h ∈ H c 1 (v, h) = min u∈A + (v) {c 1 (u, h) + [h(u) -h(v) = h]} v ̸ = v -, h ∈ H If c 1 (v, h) ≥ 1
, then at least one hyperarc associated with the creation of a shelf of height h belongs to any path from v to v -, and therefore hyperarcs asociated with the creation of shelves of height larger than h and incoming at v can be removed, or, better still, not built during the hypergraph creation. Figure 7 illustrates the dominance rule. Let us assume that state v = ( 6) is such that c 1 (v, 2) = 1 and that the dashed hyperarc incoming at v is related to the creation of a shelf with height 4. If this hyperarc has a non-zero flow value in a solution of the formulation (5), then the shelves are not ordered from top to bottom by non-decreasing height in the solution to the SCPD problem obtained by the conversion procedure described in Remark 1.

(

) (4) 8
(4, Wmax)

(2, Wmax)

(2) The additional values c 1 (v, h) can also be used to enforce another dominance rule. Let N 1 (J ) be an upper bound on the number of shelves (of any height) to build if one selects all items in J ⊆ I. For each height h, the smallest possible value for N 1 (I ≤h ) is z * BP(L,Lmax) where L contains z * TBP(I ≤h,w ,Lmax) items with weight w for each width w ∈ W h . The validity of this procedure comes from the fact that items assigned to the same compartment must share the same width. Minimizing the number of compartments to be built can be done width by width. Once the minimum number of compartments for each width is known, minimizing the number of "bins" minimizes the number of shelves to be built. Solving the BP problem and the TBP problem to optimality is not required to compute a valid upper bound using this procedure.

h i ∈ {2, 4}

Dominance rule 3. Let h ∈ H and U 1 (h) = min Hmax h

, N 1 (I ≤h ), w∈W h min z * TBP(I ≤h,w ,Lmax) , |I h,w | . There exists an optimal solution to the SCPD problem where the number of shelves with height h is not greater than U 1 (h).

Proof. The first term of the expression comes from the fact that a cabinet of height H max cannot contain more than ⌊H max /h⌋ shelves of height h.

Let S * be an optimal solution to the SCPD problem such that there are N 1 (I ≤h ) + k shelves of height h with k ∈ N * . Since the items in I ≤h can all fit into N 1 (I ≤h ) shelves, we can obtain a solution with the same value by removing the N 1 (I ≤h ) + k shelves, and reassigning their contents to N 1 (I ≤h ) shelves. This is always possible by definition of N 1 (I ≤h ).

The validity of the third term follows from a similar argument. Consider a feasible solution S to the SCPD problem with more than w∈W h min{z * TBP(I ≤h,w ,Lmax) , |I h,w |} shelves of height h. Now consider a solution S obtained from S by removing all shelves of height h, and creating new shelves as follows. For each width w ∈ W h , group all items of the set I ≤h,w selected in S into z * TBP(I ≤h,w ,Lmax) , compartments and create one shelf per compartment. The height of each shelf in S is the maximum height of an item in its compartment.

Therefore, there cannot be more than |I h,w | shelves containing an item of height h. The new solution S contains for each w at most z * TBP(I ≤h,w ,Lmax) shelves among which at most |I h,w | have height h. The solution S has at most w∈W h min{z * TBP(I ≤h,w ,Lmax) , |I h,w |} shelves of height h.

We use dominance rule 3 to remove hyperarcs that would create shelves unused in at least one optimal solution. When extending a stage 1 state v = (H) during the creation of the hypergraph, the decision to design

a shelf with height h ∈ H is skipped if c 1 (v, h) = U 1 (h).
We also introduce dominance rules 4 and 5 for the design of compartments within a shelf.

Dominance rule 4.

There exists an optimal solution to the SCPD problem such that the compartments in each shelf are ordered from left to right by non-decreasing height of their tallest item (i.e., the item with the greatest height).

During the creation of the hypergraph, the assignment of the items to the compartments is unknown.

Therefore, we cannot strictly enforce dominance rule 4. Instead, we order the compartments by non-decreasing height of the tallest item they can contain. To enforce this, we modify the height in the two states generated when making a compartment design decision at a stage 2 state. Specifically, creating a compartment of width w ∈ W h from a stage 2 state (h, W ) leads to the creation of a stage 3 state (h max (I ≤h,w ), w, L max , E * h,w , 0) and a stage 2 state (h max (I ≤h,w ), W -w).

Dominance rule 5 extends the dominance rule 3 to compartments built inside a shelf. Let N 2 (J ) be an upper bound on the minimum number of compartments to build if one selects all items in J ⊆ I. For each height h ∈ H and width w ∈ W h , the smallest possible value for N 2 (I ≤h,w ) is equal to z * TBP(I ≤h,w ,Lmax) .

Dominance rule 5.

Let h ∈ H, w ∈ W h and U 2 (h, w) = min Wmax w , N 2 (I ≤h,w ) . There exists an optimal solution to the SCPD problem where in a shelf of height h the number of compartments of width w is less than or equal to U 2 (h, w).

Proof. Each shelf in a feasible solution of the SCPD problem, and hence in any optimal solution, cannot have more compartments of width w than the number of compartments that can fit in the shelf, hence U 2 (h, w) ≤ Wmax w

. If, in a solution, a shelf of height h contains more than N 2 (I ≤h,w ) compartments of width w, then it is possible to remove these compartments and replace them with at most N 2 (I ≤h,w ) compartments of width w with the same set of items.

To enforce dominance rule 5, we attach an additional value c 2 (v, w) ∈ N to each vertex v for each width w, which is the minimum number of times an hyperarc corresponding to the creation of a compartment of width w must be traversed to reach the sink v -. Denoting w(v) the width of a stage 2 state represented by v, this value can be computed recursively as follows:

c 2 (v -, w) = 0 w ∈ W c 2 (v, w) = min u∈Γ + (v) {c 2 (u, w) + [w(u) -w(v) = w]} v ̸ = v -, w ∈ W
When extending a stage 2 state v = (h, W ) during the creation of the hypergraph, the decision to design a compartment of width w ∈ W h is skipped if c 2 (v, w) = U 2 (h, w).

In dominance rule 6, we exploit dominance rule 2 to formalize the fact that it is never useful to create a shelf whose size is greater than the tallest object it can hold.

Dominance rule 6. There exists an optimal solution to the SCPD problem such that, for each shelf of height h ∈ H, the leftmost compartment has a width such that there is an item of this width with height equal to h.

Proof. Let S * be an optimal solution to the SCPD problem and let ψ be a shelf in S * . The shelf ψ can be transformed in two steps into a shelf where the leftmost compartment contains an item with height equal to h ψ . Since the compartments in ψ can be permuted without changing the feasibility or the optimality of S * , a compartment that can contain an item with the largest height h ≤ h can be permuted with the leftmost compartment in ψ. If h < h, then the height of shelf ψ can be reduced to h.

Considering dominance rule 6 in the hypergraph generation is straightforward since it means building only compartments of width in the set {w ∈ W h : ∃i ∈ I ≤h,w , h i = h} instead of in the set {w ∈ W h : ∃i ∈ I ≤h,w , h i ≤ h} when a stage 2 state v = (h, W max ) is considered.

Merging equivalent states

To further reduce the size of the hypergraph, we now aim at merging states that represent equivalent subproblems, i.e., the possible item selection decisions from each of these states to the source v + of the hypergraph are identical. For a given state v, let η(v) ⊆ P(I) be the set of partial solutions, in terms of items, that can be derived from v, i.e. the set of possible subsets of items selected in a solution to the subproblem represented by v. Note that this set is independent of the structure of the solution and the order in which the different items are selected. Definition 1 clearly specifies what we call equivalent states.

Definition 1. (Equivalent states) We say that two states (vertices) v 1 and v 2 of the decision hypergraph (V, A)

are equivalent if η(v 1 ) = η(v 2 ).
The procedures we implement to reduce the hypergraph are inspired by those of [START_REF] Brandão | Bin packing and related problems: General arc-flow formulation with graph compression[END_REF] and [START_REF] Bergman | Decision Diagrams for Optimization[END_REF], originally introduced for simple graphs. Merging two states corresponds to removing the two corresponding vertices and creating a new vertex whose set of ingoing (resp. outgoing) hyperarcs is the union of the hyperarcs ingoing to (resp. outgoing from) the two original vertices. Proposition 3 indicates that merging vertices associated with equivalent states does not change the optimal value of the arc flow formulation (5).

Proposition 3. Let v 1 and v 2 be two vertices of the decision hypergraph (V, A). If η(v 1 ) = η(v 2 ), then merging the states associated with v 1 and v 2 in (V, A) does not modify the optimal value of the arc flow formulation (5).

Proof. Any feasible flow obtained by solving formulation (5) considering the original decision hypergraph can be converted into a feasible flow in the modified hypergraph by simply replacing the two vertices v 1 and v 2 by the new vertex corresponding to the state resulting from the merge of the two states. Since η(v 1 ) = η(v 2 ), no additional solutions in terms of items selection are added by this procedure.

The following three propositions introduce sufficient conditions for states to be equivalent. We now introduce additional notations. We call a height H ∈ {0, . . . , H max } (resp. width W ∈ {0, . . . , W max }) reachable if there exists a subset of items such that the sum of their heights (resp. widths) equals H (resp. W ). We define the sets RH H = H : ∃J ⊆ I ≤h , j∈J h j = H and RW H = W : ∃J ⊆ I ≤h , j∈J w j = W as the sets of reachable heights and reachable widths considering only items with height less than or equal to

H ∈ {0, . . . , H max }.
Proposition 4 is inspired by a classical technique used in packing problems, and is related to the notion of raster points [START_REF] Terno | Zuschnittprobleme und ihre praktische Lösung: mathematische Modelle von Layout-Problemen[END_REF]. Similar ideas for widths rather than heights lead to Proposition 5.

Proposition 5. Let h ∈ H and W 1 , W 2 ∈ {0, . . . , W max }. The stage 2 states v 1 = (h, W 1 ) and v 2 = (h, W 2 ) are equivalent if max W ∈RW h : W ≤W1 { W } = max W ∈RW h : W ≤W2 { W } Proof. Let W = max W ∈RW h : W ≤W1 { W } = max W ∈RW h : W ≤W2 { W }.
Since the largest possible combination of item widths is equal to W ≤ min{W 1 , W 2 }, the same subset of compartments can be built inside a cabinet of height h and width W 1 or W 2 . This translates into η(v 1 ) = η(v 2 ).

During the creation of the hypergraph, the two equivalent states v 1 = (h, W 1 ) and v 2 = (h, W 2 ) are merged by changing their width to the same value Ŵ = max{ W ∈ RW h : W ≤ W 1 }. Computing this value is as difficult as computing Ĥ, but the same observation holds.

Figure 8 illustrates how we merge vertices of the hypergraph when they represent equivalent stage 2 states.

In this example, the items have heights in the set {3, 6, 7} and the cabinet has a height of 10. Building a shelf of height 6 leads to a remaining stage 1 state with height 4 and building a shelf with height 7 leads to a remaining stage 1 state with height 3. The two stage 1 states (4) and (3) are equivalent because only items of height less than or equal to 3 can fit into the remaining cabinet. Proposition 6. Let h 1 , h 2 ∈ H, w ∈ W, L ∈ {0, . . . , L max }, e 1 , e 2 ∈ E, and q ∈ {0, 1} |I| . The two stage 3

states v 1 = (h 1 , w, L, e 1 , q) and v 2 = (h 2 , w, L, e 2 , q) are equivalent if {ẽ ∈ E h1,w : ẽ ≤ e 1 } = {ẽ ∈ E h2,w : ẽ ≤ e 2 }.
Proof. Note that v 1 and v 2 are both associated with a compartment of width w which currently contains the subset of selected items q. The condition ensures that the set of items that can enter or leave the compartment if considering the events in descending order are exactly the same from e 1 as from e 2 . Therefore, η(v 1 ) = η(v 2 ).

We use Proposition 6 to merge vertices associated with equivalent stage 3 states. For each event e ∈ E, we compute H -(e, h) = max h i(ẽ) : ẽ ∈ E, ẽ ≤ e, h i(ẽ) ≤ h, w i(ẽ) = w i(e) as the maximum height of items in the events occurring before e that share their width with i(e), considering only items with a height less than or equal to h. After making the item selection decision associated with event e, we change the height of the resulting stage 3 states to H -(E - h,w (e), h), which in a sense corresponds to reducing the height of the compartment. Figure 9 illustrates how we merge vertices of the hypergraph when they represent equivalent stage 3 states.

Note that this procedure reduces the number of vertices and hyperarcs in the decision hypergraph.

(4, 4, Lmax, E * 4,4 , 0) (2, 4, Lmax, E * 2,4 , 0) (4, 4, L, e, q)
(2, 4, L, e, q)

v +

Set of decisions D1

Set of decisions D2 ⊊ D1

Set of decisions D3

Set of decisions D3

(a) Without merging vertices associated with equivalent stage 3 states, the dashed and dotted paths are distinct

(4, 4, Lmax, E * 4,4 , 0) (2, 4, Lmax, E * 2,4 , 0) (4, 4, L, e, q) (2, 4, L, e, q) v +

Exploiting trivial subproblems

In the SCPD problem, there may exist states that represent trivial subproblems, i.e., all the admissible items can be selected by making decisions from these states to the source of the hypergraph. For a stage 1 state (H), an admissible item is an item that fits into a cabinet with height H, width W max , and length L max . For a stage 2 state (h, W ), an admissible item is an item that fits into a shelf with height h, width W , and length L max . For a stage 3 state (h, w, L, e, q), an admissible item is an item that leaves a compartment with height h, width w, and length equal to L before or at event e. We refer to a state associated with a trivial subproblem as a trivial state. We first clarify this notion in Definition 2, then we show how it can be leveraged to simplify our dynamic program, and thus reduce the size of the decision hypergraph.

Definition 2. A state v of the dynamic program (2)-( 4) is said to be trivial if

• it is a stage 1 state (W ) and η(v) = P(I ≤H )

• it is a stage 2 state (h, W ) and η(v) = P ∪ w≤W I ≤h,w

• it is a stage 3 state (h, w, L, e, q) and η(v) = P ({i ∈ I ≤h,w : ∃ẽ ∈ E out , ẽ ≤ e, i(ẽ) = i})

Nothing prevents an item from being selected more than once in the dynamic program (2)-(4). Selecting an item at most once is only enforced by constraints (5d) in the arc flow formulation. This prevents us from creating directly in the hypergraph an arc from the source to the vertex corresponding to a trivial state, with a profit equal to the sum of the profits of the admissible items. Since each item in an instance of the SCPD problem cannot be selected twice, even if taking an item is locally obviously profitable, we have to consider the possibility of not selecting this item. When a trivial state is detected, we use a simplified recursion, as we only need to decide which items to select and sum their respective profits. We introduce two recursions: one used when we detect a trivial stage 1 or stage 2 state and another used when we detect a trivial stage 3 state.

Before defining our simplified states, let us define additional notation to simplify the formulas. We denote by I w the list of items of I with width w ordered by non-decreasing value of their height. We also denote by I ≤h,w the list of items of I ≤h,w , ordered by non-decreasing value of their exiting time step (the exiting time step of an item i ∈ I is

s i + d i ). Let I w [k] (resp. I ≤h,w [k]
) be the item at index k in I w (resp. I ≤h,w ).

Let β ‡ (h, w, k) be the maximum profit that can be obtained considering the selection of items in I ≤h,w at an index lower than or equal to k ∈ {0, . . . , |I ≤h,w |}. The forward recursion is as follows:

β ‡ (h, w, k) =    0 if k = 0 max p I ≤h,w [k] + β ‡ (h I ≤h,w [k] , w, k -1), β ‡ (h I ≤h,w [k] , w, k -1) otherwise (7)
Note that if an item could be selected any number of times, only the first term within the maximum operator in ( 7) would be necessary. However, both terms are necessary to allow the non-selection of an item in a trivial suproblem, and to keep the arc flow formulation valid in the hypergraph associated with the dynamic program.

If a stage 3 state v = (h, w, L, e, q) is detected trivial, we compute the index k e of an item in I ≤h,w related to the first outgoing event occurring before or exactly at e, i.e. k e = max{k ∈ {1, . . . , |I ≤h,w |} : e out (I ≤h,w [k]) ≤ e} where e out (i) is the outgoing event of an item i ∈ I. Then we do the following substitution:

α 3 (h, w, L, e, q) = β ‡ (h, w, k e ) (8)
We refer to the states created by the combined use of equations ( 7) and (8) as trivial stage 3 states, but we denote them as (h, w, k) ‡ , where h ∈ H, w ∈ W and k ∈ {1, . . . , |I ≤h,w |}.

Let β † (w, k) be the maximum profit that can be obtained given a selection of items in I w with an index less than or equal to k ∈ {0, . . . , |I w |}. The forward recursion is as follows:

β † (w, k) =    0 if k = 0 max p Iw[k] + β † (w, k -1), β † (w, k -1) otherwise (9)
For each height H ∈ {0, . . . , H max } and width w ∈ W H , let k w (H) be the index in I w of the first item of width w whose height is less than or equal to H, i.e. k w (H) = max{k ∈ {0, . . . , |I w |} : h Iw[k] ≤ H}. If a stage 2 state (h, W ) or a stage 1 state (H) is found to be trivial, we make the following substitutions:

α 2 (h, W ) = w∈W h :w≤W β † (w, k w (h)) (10)
α 1 (H) = w∈W H β † (w, k w (H)) (11)
As before, we refer to the states created by the combined use of the equations ( 9), ( 10) and (11) as trivial states, but we denote them as (w, k) † , where w ∈ W and k ∈ {1, . . . , |I w |}.

In the specific case where a stage 3 state (h, w, L max , E * h,w , 0) is detected trivial, we use the following non-recursive formula to indicate whether all or none of the items are selected.

α 3 (h, w, L max , E * h,w , 0) = max    i∈I ≤h,w p i , 0    (12)
Again, if an item could be selected any number of times, only the first term within the maximum operator in ( 12) would be needed. We show below that equation ( 12) is valid.

Dominance rule 7. If a stage 3 state (h, w, L max , E * h,w , 0) is trivial, then there exists at least one optimal solution to the SCPD problem where exactly one of the following assertions is true:

• there is no compartment of size (h, w)

• all compartments of size (h, w) are empty

• exactly one compartment of size (h, w) is not empty and contains all items of I ≤h,w Proof. Let S * be an optimal solution to the SCPD problem and assume that none of the three assertions is true. This means that there exists multiple non-empty compartments of size (h, w), or a single non-empty compartment of size (h, w) containing only a subset of I ≤h,w . In both cases, a solution that satisfies the above condition can be obtained by removing all items from all compartments of size (h, w), and assigning all items of I ≤h,w to a single compartment. This is always feasible since (h, w, L max , E * h,w , 0) is trivial.

Figure 10 illustrates how the recursive formula (9) and equation ( 10) leads to the creation of hyperarcs when we encounter a trivial stage 2 state (h, W ). In this example, the items have widths in the set {1, 2, 3}.

Note that this modification to the dynamic program makes the design of shelves and compartments implicit in the decision hypergraph. Once the arc-flow formulation has been solved, if the flow entering trivial states is non-zero, we consider the same design decisions as in the solution where each item is assigned, but we remove the items that are not selected. We now extend the notion of trivial subproblems. If a stage 1 state (H) is not trivial, it may happen that if one considers the possibility of building only shelves of height h < H or less in a cabinet of height H, all admissible items can be selected. In this case, we say that v is h-trivial. We specify this notion in Definition 3.

(h, W ) (1, 3) † (1, 2) † (1, 1) † (1, 0) † (2, 3) † (2, 2) † (2, 1) † (2, 0) † (3, 2) † (3, 1) † (3, 0) † v +
Definition 3. Let H ∈ {0, . . . , H max } and h ∈ H such that h < H. A stage 1 state (H) is said to be h-trivial if η(v) ⊃ P(I ≤h ).
If a stage 1 state v = (H) is detected h-trivial for h ∈ H, then the equation ( 4) can be replaced by

α 1 (H) = max    max h∈H,h<h≤H {α 2 (h, W max ) + α 1 (H -h)} , w∈W h β † (h, w)    ( 13
)
This equation is derived by separating a stage 1 state into two cases. Either a shelf with a height greater than h is built, in which case the recursion does not change from the initial one, or a shelf of height less than or equal to h is built, in which case, by Dominance rule 2 only shelves of height h or less will be subsequently used. Since by assumption the problem is trivial by using only shelves of height h of less, the right-hand part of the equation, which allows to select any subset of items of height less than h, is valid. Figure 11 illustrates how the recursive formula (9) and equation ( 13) leads to the creation of hyperarcs when we encounter a stage 1 state (H) that is h-trivial with H = 4 and h = 2. In this example, the items have a height in the set {1, 2, 3}, a width in the set {1, . . . , 7} and there is enough space to place each item with height less than 2 in shelves of height 2. The creation of shelves of height 1 is ignored and the creation of a shelf of height 2 is replaced by a transition to the trivial states.

(4) The following observation highlights the fact that all of the proposed reductions can be applied together while maintaining the validity of the arc flow model.

(3, 4) (1) (2, 4) (2) (1, 4) (3)
Observation 1. Because (12) is the only simplification of the dynamic program that reduces the set of partial solutions in terms of item selection, simultaneously using (8), ( 10), ( 11), ( 12), and (13) does not cut off all optimal solutions to the SCPD problem.

To conclude this section, we now describe our procedures for detecting whether a state v is trivial or h-trivial if v is a stage 1 state. We detect whether a stage 3 state v = (h, w, L, e, q) is trivial by trying to select each item i ∈ I ≤h,w such that s i + d i ≤ t(e). We formalize this procedure in Proposition 7. For each e ∈ E and q ∈ {0, 1} |I| , let σ(e) be the event ẽ ̸ = e such that i(ẽ) = i(e) and l(e, q) defined as follows:

l(e, q) =                -ℓ i(e) if e ∈ E out ℓ i(e)
if e ∈ E in ∧ σ(e) > e ∧ q i(e) = 1 0 if e ∈ E in ∧ σ(e) > e ∧ q i(e) = 0

ℓ i(e) if e ∈ E in ∧ σ(e) ≤ e
Proposition 7. A stage 3 state v = (h, w, L, e, q) is trivial if and only if the following conditions hold:

∀ẽ ∈ E h,w , ẽ < e, L + e ê=ẽ l(ê, q) ≥ 0 (14)

Proof. Let v = (h, w, L, e, q) be a stage 3 state. The state v is trivial if, at each time step before t(e), each item is selected in the solution and the remaining available length in the compartment does not fall below 0.

This condition is equivalent to the statement that, for each event ẽ ≤ e, the sum of the contributions to the length constraint of events between ẽ and e is less than or equal to L max . Therefore, v is trivial if the condition (14) holds.

We determine whether a stage 2 problem is trivial by computing an upper bound on the minimum width required to select each admissible item in the shelf. If this value is less than or equal to the width W max of the cabinet, then the stage 2 problem is trivial.

Proposition 8. A stage 2 state v = (h, W ) is trivial if the following condition holds:

w∈W h w • z * TBP(I ≤h,w ,Lmax) ≤ W (15)
Proof. Let v = (h, W ) be a stage 2 state. For each width w ∈ W h , z * TBP(I ≤h,w ,Lmax) is the minimum number of compartments of width w required to select each item i ∈ I ≤h,w . Hence, w∈W h w • z * TBP(I ≤h,w ,Lmax) denotes an upper bound on the minimum width required to place each item in the shelf.

Finally, let H(J ) be the minimum height of a cabinet of width W max and length L max required to select all items in J ⊆ I. For a given h ∈ H, we compute H(I ≤h ) by solving a BP problem considering W max as the capacity of the bins and defining J with z * TBP(I ≤h,w ,Lmax) items with weight w for each w ∈ W h . Each item of weight w in the BP instance corresponds to a bin in a solution to the TBP problem defined with the items from I ≤h,w (the weight of these latter items in the TBP problem is equal to their length in the SCPD problem). We associate to each item of the BP instance a height computed as the maximum height of an item of I ≤h,w assigned to the corresponding bin in the solution to the TBP problem. For each bin in the optimal solution to the BP problem, we compute the maximum height of an item assigned to it. The value H(I ≤h ) is then the sum of the maximum height of each bin. We determine whether a stage 1 state v = (H) is h-trivial by comparing H(I ≤h ) and h. Solving the BP and the TBP problems to optimality is not required to compute a valid upper bound using this procedure.

Proposition 9. A stage 1 state v = (H) is h-trivial with h ∈ H such that h ≤ H if H(I ≤h ) ≤ H. Note that if v = (H) is h-trivial and there is no h ∈ H such that h < h ≤ H, then v is trivial.

Computational experiments

In this section, we first explain in §5.1 how we generated instances to the SCPD problem. We then describe in §5.2 the outcomes of the computational experiments we performed.

The aim of our experiments is twofold. First, we assess the added value of the improvements described in §4.1, §4.2, §4.3 and §4.4 on the results of the arc flow formulation. Second, we compare using several metrics (size of the formulation, integrality gap, number of instances solved, solution time, and optimality gap) the results obtained by the solver with the compact MILP formulation (1) and the arc flow formulation (5) with and without all the improvements introduced in section 4.

Data sets

Our experiments are conducted using randomly generated instances 1 . For each instance, we set (H max , W max , L max ) = (300, 300, 300), and for each item, the height, width, length and profit are all uncorrelated and uniformly randomly distributed in the interval [50,100]. To ensure that the compartments represent relevant problems, the number of different widths is set equal to m ∈ N * and the generation algorithms are adapted to this property. For the time intervals, we separate the instances into two classes, using the same methodology as [START_REF] Caprara | Uncommon dantzig-wolfe reformulation for the temporal knapsack problem[END_REF]. For the second class of instances, denoted I, we generate the time intervals using a clique-based methodology.

The notion of clique comes from the interval graph representation of the time intervals. A clique in an interval graph corresponds to a set of overlapping intervals. In the clique-based framework, we consider each width independently of the others. For each width, we generate C cliques, where each time step corresponds to a different clique of items. The generation algorithm starts by creating a set of items at the first time step, i.e. items i such that s i = 0. Iteratively, at each time step t, the algorithm removes b% of the items, (i.e. selects b% items from the previous clique and sets d i = t -s i for these items), and adds a new items (i.e. items such that s i = t), to form the clique of time step t. The parameters b and a are uniformly randomly drawn in [b min , b max ] and [a min , a max ], respectively. The algorithm stops when the last clique has been generated. Algorithm 13 in §S.3 of the supplementary material summarizes the generation algorithm for the instances of class I.

1 available online from https://gitlab.inria.fr/edge/scpd/scpd-artifacts

We now define the different instance groups we created and explain the relevance of the chosen generation parameters. For each size of the input, i.e. the number of items, we create three instance groups where the only varying parameter is the number of different widths. The values we have chosen for s max , d min , d max , a min , a max , b min and b max ensure that there is no instance where there is at most one item per width at each time step, i.e. the instance only requires solving the design phase. Finally, the parameter m plays an important role in the structure of our instances, with a lower value usually meaning an easier design phase and a more difficult assignment phase. Therefore, we use different values depending on the instance group to study the impact it has on the difficulty of our instances. Tables 2a and2b summarize the generation parameters for the instances of classes U and I, respectively. In these tables, the column |I|, which is the mean number of items per instance in the group, is given as an additional information and does not impact the instances generation.

We generate 10 instances per instance group for a total of 180 instances. To ensure that the clique-based instances in the same group generated by a probabilistic method do not unexpectedly differ in the number of items, we generate many instances but keep only a subset of them, chosen randomly so that the difference in the number of items of the minimum and maximum size instances is less than or equal to 5.

Numerical results

All of our experiments were run on a Haswell Intel Xeon E5-2680 v3 CPU running at 2.5 GHz with 128 Go RAM. For each instance, we solved each MILP formulation with CPLEX 20.1 using 8 threads with a CPU time limit of 60 minutes. We solved the compact formulation of the TBP and BP problems (see Dell'Amico et al.

(2020)) associated with the improvements described in §4.2 and §4.4 with CPLEX 20.1 with default parameters and a time limit of 10 seconds. The detailed results for every single tested instance are available online2 .

In the remainder, we note C the compact formulation (1), AF the arc flow formulation (5) and AF +ALL the arc flow formulation (5) with the improvements described in section 4. We consider an instance to be solved if the solver returns a proven optimal solution.

reports the number of instances considered in the comparison. In this We observe that the arc flow formulations have a smaller integrality gap than the compact formulation.

The valid inequalities we add help to improve the linear relaxation of the formulation AF. Specifically, the formulation AF +VI has a better linear relaxation than the formulation AF for 36 out of the 180 instances. The relative difference between the integrality gap obtained with and without the valid inequalities is at most 0.3%.

We observe that the other improvements of Section 4 further improve the linear relaxation of the formulation AF. For 39 instances, the integrality gap is equal to 0. In our experiments, this corresponds to instances where all the items are selected in the solution. These instances all have at most 100 items.

We now examine for which formulation the solver returns the largest number of proven optimal solutions or gives the best solutions among the formulations C and AF +ALL . For each instance, we calculate the best primal solution and the best dual solution obtained by the solver over the two formulations. For each group of ten instances and each formulation, Table 5 reports in columns "Primal best", "Dual best" and "Solved", the number of times the best primal solution is obtained with the formulation, the number of times the best dual solution is obtained with the formulation, and the number of instances solved, respectively. The gray values in the column "Primal best" (resp. "Dual best") are the number of times the solver found a feasible primal (resp.

dual) solution with this formulation.

Table 5: Results obtained by the solver within 3600 seconds for the formulations C and AF +ALL

We observe that 25 more instances are solved with the formulation AF +ALL than with the formulation C.

Note that every instance solved with the formulation C is also solved with the formulation AF +ALL . Of the 84 solved instances, the 39 instances where all the items are selected are all solved in less than 7 seconds with the formulation AF +ALL and in less than 66 seconds with the formulation C. The solver finds 90 better dual solutions with the formulation AF +ALL than with the formulation C. However, it returns 14 fewer best primal solutions with the former than with the latter and no feasible solution is found with the former within the time limit for seven large instances of group U200-3. This comes from the fact that the formulation AF +ALL has a comparable number of constraints to the formulation C, but has more than 25 times as many variables as the latter. For the 39 instances (resp. 28) instances where the solver returns a better primal solution with formulation C (resp. AF +ALL ) than with the formulation AF +ALL (resp. C), the gap between the value of the primal solution obtained by the two formulations is on average equal to 4.21% (resp. 0.92%). This gap is calculated using the formula 100 • |z * -z| |z * | where z * is the primal bound for the formulation C (resp. AF +ALL ) and z is the primal bound for the formulation AF +ALL (resp. C).

We finally examine the solution time and the gap obtained for the formulations C, AF and AF +ALL .

Figure 12a shows for each formulation the number of instances solved as a function of time. We observe that as many instances are solved in 10 minutes with the formulation C as with the formulation AF in 60 minutes.

More interestingly, we observe that as many instances are solved in 10 minutes with the formulation AF +ALL as with the formulation C in 60 minutes, which confirms the superiority of the formulation AF +ALL . Figure 12b plots for each formulation the number of instances for which the optimality gap is smaller than the value given on the x-axis. For each formulation and each instance, the optimality gap is calculated using the formula 100 • |z-d| |d| where z and d are the primal and dual bounds returned by the solver. Overall, better optimality gaps are obtained with the formulation AF +ALL , with the exception of the seven instances with no feasible solution computed within the time limit. The average optimality gap is equal to 6.32%, 9.98% and 4.38% for formulations C, AF and AF +ALL , respectively. For the 25 instances solved with the formulation AF +ALL but not with the formulation C, the average optimality gap returned by the solver for the latter is 8.78%.

All the results in this section indicate that on the instances we have generated, the results obtained with the formulation AF +ALL are significantly better than those obtained with the formulation C .

Conclusion

In this paper we considered the design of shelves and compartments in a storage cabinet. We defined the problem as a combination of a guillotine cutting problem and a set of temporal knapsack problems. We presented a compact mixed-integer linear program for it and an arc flow formulation based on an exponentially large hypergraph corresponding to a decision hypergraph of a dynamic program for a relaxation of the SCPD problem. We showed that using this arc flow formulation as it is does not lead to any additional solved instances compared to using a compact formulation, although its linear relaxation is of better quality. We presented several improvements to reduce the size of the hypergraph while maintaining the validity of the arc flow formulation. With the introduced refinements, we manage to reduce the hypergraph to approximately 41 % of its original size. The arc flow formulation based on this reduced hypergraph and containing valid inequalities produces significantly better results than those obtained with the original hypergraph, solving 35 more instances and providing better primal and dual bounds. Compared to the compact formulation, 25 more instances are solved using the arc flow formulation on the reduced hypergraph and with valid inequalities, and the average gap is reduced from 6.32% to 4.38%.

A possible way for solving more instances of the SCPD problem with our arc flow formulation is to give a primal solution computed by problem-specific heuristics to the solver. Generalizing our filtering techniques to problems than can be formulated using decision hypergraphs is also of particular interest.

Figure 1 and

 1 Figure 1 and Figure 2 show an instance of the SCPD problem with four items and two time steps and a feasible solution. In this instance, items 1 and 3 are present only during time step 1, 2 and 4 are present at time steps 1 and 2, and items 5 and 6 are present at time step 2. The solution we present has one shelf with two compartments and each item of the instance has been assigned to a compartment. The gray parts represent wasted space.

Figure 1 :Figure 2 :

 12 Figure 1: An instance with four items and two time steps

Figure 3 :

 3 Figure 3: Illustration of the design decisions

  0)} ; // create the hyperarc the flow. Such a flow in the decision hypergraph associated with the dynamic program defined by (2), (3), and (4) is not necessarily a feasible solution to the SCPD problem because it does not ensure that an item is assigned to no more than one compartment. We therefore formulate the SCPD problem as a maximum cost flow problem in the hypergraph, but with additional linear constraints to ensure the feasibility of the solution represented by the flow.

Figure 4 :(Figure 5 :

 45 Figure 4: Decision hypergraph of the instance given inTable 1 and an optimal solution

Figure 6 :

 6 Figure 6: Example of a solution to the linear relaxation of model (5)

Figure 7 :

 7 Figure 7: Illustration of how to exploit dominance rule 2 in the hypergraph generation

Figure 8 :

 8 Figure 8: Example of equivalent stage 2 states

Figure 9 :

 9 Figure 9: Example of equivalent stage 3 states

Figure 10 :

 10 Figure 10: Illustration of the hyperarcs created from a trivial stage 2 state (h, W )

Figure 11 :

 11 Figure 11: Example of h-trivial stage 1 problems reduction

For

  the first class of instances, denoted U, we generate the starts of time intervals uniformly at random in the interval [0, s max ] and the durations uniformly at random in the interval [d min , d max ]. Algorithm 12 in §S.3 of the supplementary material summarizes the generation algorithm for the instances of class U.

Figure 12 :

 12 Figure 12: Performance profiles for the three MILP formulations

  Generation algorithm for the instances of class U Input: n the number of items, m the number of different widths Output: An instance of the SCPD problem I ← ∅ denotes the set of items ; W ← ∅ denotes the set of different widths ; for k ∈ {0, . . . , m} do w ← value from U[rmin, rmax] ; W ← W ∪ {w} ; nw ← ⌈ n |W| ⌉ ; for w ∈ W do for k ∈ {0, . . . , nw} do i denotes an item ; hi ← value from U[rmin, rmax] ; wi ← w ; ℓi ← value from U[rmin, rmax] ; pi ← value from U[rmin, rmax] ; si ← value from U[0, smax] ; di ← value from U[1, dmax] ; return ((300, 300, 300), I)

Table 1 :

 1 An SCPD instance with two items

	v -
	(10)

  Proposition 4. Let H 1 , H 2 ∈ {0, . . . , H max }. The stage 1 states v 1 = (H 1 ) and v 2 = (H 2 ) of the decision Let H = max H∈RH H 1 : H≤H1 { H} = max H∈RH H 2 : H≤H2 { H}. Since the largest possible combination of item heights is equal to H ≤ min{H 1 , H 2 }, the same subset of shelves can be built inside a cabinet of heightH 1 or H 2 . This translates into η(v 1 ) = η(v 2 ).During the creation of the hypergraph, the two equivalent states v 1 = (H 1 ) and v 2 = (H 2 ) are merged by changing their height to the same value Ĥ = max{ H ∈ RH H1 : H ≤ H 1 }. Note that computing Ĥ involves solving a subset sum problem which is known to be weakly NP-hard. However, considering that the target instances of the SCPD problem have hundreds of items, computing this value is never a bottleneck. Furthermore, in the specific case of stage 1 states, Proposition 4 can be improved by combining it with dominance rule 2. When creating a shelf of height h in a cabinet of height H, instead of modifying the height of the remaining stage 1 state to max{ H ∈ RH

	hypergraph are equivalent if
	max H∈RH H 1 : H≤H1	{ H} =	max H∈RH H 2 : H≤H2	{ H}
	Proof.

H : H ≤ H}, we change it to max{ H ∈ RH h : H ≤ H}.

Table 2 :

 2 Generation parameters for the instances

  table, the formulation AF +VI denotes the arc flow formulation with the valid inequalities of Subsection 4.1. For each formulation and each of these instances, we compute the integrality gap with the formula 100 • |z * -d| |d| where z * is the optimal value of the instance and d is the value obtained solving by the linear relaxation of the formulation.

			Number of		Integrality gap
	Group	|I|
			instances	C	AF AF +VI AF +ALL
	I5-3	38	10	0	0	0	0
	I5-5	63	7	1.13 1.13	1.13	1.13
	I5-10	125	9 26.25 6.19	6.17	5.94
	I10-3	72	4	0.70 0.70	0.70	0.70
	I10-5	126	0	-	-	-	-
	I10-10	253	3 46.48 3.61	3.61	3.55
	I15-3	114	0	-	-	-	-
	I15-5	191	0	-	-	-	-
	I15-10	375	0	-	-	-	-
	U70-3	70	10	0	0	0	0
	U70-5	70	9	0.35 0.35	0.35	0.35
	U70-10	70	10	3.34 2.92	2.92	2.73
	U100-3	100	3	0	0	0	0
	U100-5	100	5	6.97 5.26	5.20	4.95
	U100-10 100	9 11.22 4.93	4.92	4.70
	U200-3	200	0	-	-	-	-
	U200-5	200	0	-	-	-	-
	U200-10 200	5 32.52 3.98	3.96	3.79
	Mean	-	84	8.59 2.38	2.37	2.28

Table 4 :

 4 Integrality gap of the formulations

https://gitlab.inria.fr/edge/scpd/scpd-artifacts

Acknowledgments

This research was funded by the French Agence Nationale de la Recherche through project AD-LIB (ANR-22-CE23-0014-01). Experiments presented in this paper were carried out using the PLAFRIM experimental testbed, being developed under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d'Aquitaine, Université de Bordeaux and CNRS (and ANR in accordance to the programme d'investissements d'Avenir (see http://www.plafrim.fr))

Evaluating the improvements made to the arc flow formulation

In this section, we examine the individual added value of the improvements to the formulation AF contained in the formulation AF +ALL . For this purpose, we classify the improvements into four families, each family corresponding to one of the subsections §4.1 (valid inequalities, VI), §4.2 (pruning hyperarcs, PH), §4.3 (merging equivalent states, MES) and §4.4 (trivial subproblems, TS). First, considering the formulation AF, for each family of improvements, we consider all the improvements listed in the corresponding subsection, creating the formulations AF +VI , AF +PH , AF +MES and AF +TS , respectively. Second, considering the formulation AF +ALL , for each family of improvements, we remove the improvements listed in the corresponding subsection, creating the configurations AF +ALL-VI , AF +ALL-PH , AF +ALL-MES and AF +ALL-TS , respectively. For each configuration, we report in Table 3 the size of the model and the number of instances solved. Note that, due to memory constraints, the formulation AF could not be created for 9 instances of the group U200-3 and for 1 instance of the group I15-10 (the largest formulation created contains around 12 millions of variables and 11 millions of constraints).

Formulation Variables Constraints Solved Difference

AF

1.0 1.0 49 -

AF +TS 0.9 0.9 56 +7

Variables/Constraints: The average ratio between the number of variables and the number of constraints of the formulation and the formulation AF.

Solved: The number of instances solved (to optimality).

Difference: The difference in the number of instances solved between the formulation and the formulation AF.

(a) Arc flow formulation with one family of improvements added Formulation Variables Constraints Solved Difference

Variables/Constraints: The average ratio between the number of variables and the number of constraints of the formulation and the formulation AF +ALL .

Solved: The number of instances solved (to optimality).

Difference: The difference in the number of instances solved between the formulation and the formulation AF +ALL .

(b) Arc flow formulation with each family of improvements added except one

Table 3: Impact of the improvements on the size and the number of the instances solved using the arc flow formulation When considered independently, merging equivalent states (MES) has the highest added value, followed by using dominance rules (PH) to prune hyperarcs and exploiting trivial subproblems (TS). This is highly correlated with reducing the size of the model. If only valid inequalities are introduced in the formulation AF, they have a negative effect on the results obtained with the solver. However, removing these inequalities from the formulation AF +ALL results in three less instances being solved. To conclude this analysis, the best configuration is obtained by using all the improvements described in this paper. Note that the number of variables and constraints in the formulation AF +ALL is reduced by about 59% on average compared to the formulation AF.

Comparing the results obtained with the compact and the arc flow formulations

We now compare in Table 4, Table 5, and Figure 12, the arc flow formulations to the formulation C in terms of integrality gap, number of instances solved, and number of best primal and dual bounds found.

We first study the linear relaxations of the different models. We consider only the instances for which the linear relaxation of each formulation was solved in less than 70 hours using CPLEX 20.1 and for which the optimal value is known (i.e., the instance has been solved during at least one of our tests). Primal best: The number of times the formulation found the best primal solution and, in gray, the number of times the formulation found a feasible primal solution.

Dual best: The number of times the formulation found the best dual solution and, in gray, the number of times the formulation found a feasible dual solution.

Solved: The number of instances solved (to optimality) by the formulation. // pairs (stage 3 state, compartment) to process

Supplementary material

// add the shelf information to u else

Choose arbitrarily F such that x (F ,v) ≥ 1 ;

for u ∈ F do if u is a stage 3 state (h ψ , wu, Lmax, E * h ψ ,wu , 0) then ϕ ← (h ψ , wu, Lmax) ; // creation of a compartment with height h ψ , width wu

Choose arbitrarily F such that x (F ,v) ≥ 1 ;

if e ∈ E out and qi(e) = 1 then ρ(i(e)) ← ϕ ;

S.2. Hypergraph generation algorithms with all improvements of Section 4

Algorithm 6: Generating the decision hypergraph associated with the dynamic programs (2)-( 4) and the improvements of Section 4

Input: An SCPD instance (Hmax, Wmax, Lmax), I

Output: A decision hypergraph associated with the given instance

Apply Algorithm 2 with (Hmax, Wmax, Lmax), I , v, S 1 , S 2 , S † and (V, A) as inputs ;

while S 2 ̸ = ∅ do v = (h, W ) ← element of S 2 that maximizes lexicographically h and w ;

S 2 ← S 2 \ {v} ;

Apply Algorithm 3 with (Hmax, Wmax, Lmax), I , v, S 2 , S 3 , S † , and (V, A) as inputs ;

while S 3 ̸ = ∅ do v = (h, w, L, e, q) ← element of S 3 that maximizes lexicographically h, w, e ;

S 3 ← S 3 \ {v} ;

Apply Algorithm 4 with (Hmax, Wmax, Lmax), I , v, S 3 , S ‡ and (V, A) as inputs ;

while S † ̸ = ∅ do v = (w, k) † ← element of S † that maximizes lexicographically w, k ;

Apply Algorithm 10 with (Hmax, Wmax, Lmax), I , v, S † and (V, A) as inputs ;

Apply Algorithm 11 with (Hmax, Wmax, Lmax), I , v, S ‡ and (V, A) as inputs ;

Algorithm 7: Create the decision hyperarcs incoming to a vertex associated with a stage 1 state (improved)

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 1 state v = (H), three sets S 1 , S 2 and S † , an hypergraph (V, A)

Result: Creates the hyperarcs incoming to v, updates V, A, S 1 , S 2 , and S †

Algorithm 8: Create the decision hyperarcs incoming to a vertex associated with a stage 2 state (improved)

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 2 state v = (h, W ), three sets S 2 , S 3 , and S † an hypergraph (V, A)

Result: Creates the hyperarcs incoming to v, updates V, A, S 2 , S 3 and S † v1 ← ( ĥ, w, Lmax, E * ĥ,w , 0) ; v2 ← ( ĥ, Ŵ ) ;

Algorithm 9: Create the decision hyperarcs incoming to a vertex associated with a stage 3 state (improved)

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a stage 3 state v = (h, w, L, e, q), a set S 3 and S ‡ an hypergraph (V, A)

Result: Adds predecessors to v, updates V, A, S 3 , and S ‡ v1 ← ( ĥ, w, L, E - h,w (e), q) ; // skipping the item

v2 ← ( ĥ, w, L -ℓ i(e) , E - h,w (e), q + ε i(e) ) ; // selecting the item

A ← A ∪ {(v, {v2}, p i(e) )} ; // generate an hyperarc else if e ∈ E in then ĥ ← H -(E - h,w (e), h) ; // Proposition 6 if q i(e) = 0 then v1 ← ( ĥ, w, L, E - h,w (e), q) ; // skipping the item else v1 ← ( ĥ, w, L + ℓ i(e) , E - h,w (e), qε i(e) ) ; // selecting the item

Algorithm 10: Create trivial states

Input: An SCPD instance (Hmax, Wmax, Lmax), I , a trivial state v = (w, k) † , a set S † , an hypergraph (V, A)

// connect the source with this state return ((300, 300, 300), I)