# An Exact Method for the 2D Guillotine Strip Packing Problem

Authors: Abdelghani Bekrar; Imed Kacem
Journal: Advances in Operations Research
 (2009)

---

## Abstract

We consider the two-dimensional strip packing problem with guillotine
cuts. The problem consists in packing a set of rectangular items on one strip of widthW and infinite height. The items packed without overlapping must be extracted by a series of
cuts that go from one edge to the opposite edge (guillotine constraint). To solve this problem,
we use a dichotomic algorithm that uses a lower bound, an upper bound, and a feasibility test
algorithm. The lower bound is based on solving a linear program by introducing new valid
inequalities. A new heuristic is used to compute the upper bound. Computational results
show that the dichotomic algorithm, using the new bounds, gives good results compared to
existing methods.


---

## Body

## 1. Introduction

The two-dimensional  strip packing problem (2SP) is a well-known combinatorial optimization problem. It has several industrial applications like the cutting of rolls of paper or textile material. Moreover, some approximation algorithms for bin packing problems are in two phases where the first phase aims to solve a strip packing problem [1, 2]. Consider a set J of n rectangular items. Each item i has a width wi and a height hi(i∈{1,2,…,n}). The 2SP consists in packing all the items in a strip of width W and infinite height. The dimensions of the items and the strip are integers. The objective is to minimize the total height used to pack the items without overlapping. The orientation of items is fixed, that is, they cannot be rotated.This problem is NP-hard in the strong sense since the special case where all items have the same height is equivalent to the one-dimensional bin packing [3, 4].An additional constraint considered in this paper is the guillotine cut: All items must be extracted by cuts that go from one edge to the opposite edge. Figure1(a) shows a guillotine pattern where all items can be extracted by guillotine cuts. When items cannot be extracted by guillotine cuts, the pattern is called nonguillotine as shown in Figure 1(b).(a) Guillotine pattern, (b) nonguillotine pattern.
(a)(b)Most of  papers considering the 2SP problem are approximation algorithms. Fernandez de la Vega and Zissimopoulos [5], Lesh et al. [6] Kenyon and Rémila [7], and Zhang et al. [8] presented approximation algorithms for the strip packing problem. Bortfeldt [9], and Beltran et al. [10] used metaheuristics. Hopper and Turton [11] provided an overview of metaheuristic algorithms applied to 2D strip packing problem.To the best of our knowledge, there are only few papers which used exact algorithms to solve 2SP problem. Hifi [12] introduced the cutting/packing problem with guillotine cut, and he proposed two algorithms based on branch and bound. Martello et al. [4] proposed a new lower bound and used a branch and bound to solve the problem without guillotine constraint.Recently, three papers introduced the strip packing problem with guillotine constraint. Cui et al. [13] proposed a recursive branch and bound to obtain an approximate solution. A new lower bound and a Branch and Bound were proposed by Bekrar et al. [14]. Finally, Cintra et al. [15] used the column generation method and dynamic programming to solve another variant of the problem (a bound on the number of each small rectangle to be packed is imposed).In this paper, we propose an exact algorithm based on dichotomic search to solve the two-dimensional strip packing problem with guillotine cut. In Section2 we present some lower bounds proposed in literature. In Sections 3 and 4, we, respectively, present the lower bound and the upper bound used in the algorithm. In Section 5, we explain the dichotomic algorithm. We provide computational results in Section 6. Finally, we discuss some perspectives of our work.


## 2. Lower Bounds for the 2SP Problem

In this section, we first recallexisting lower bounds proposed for the strip packing problem: the continuous lower bound Lc, the lower bounds of Martello et al. [4], Lmmv1 and Lmmv2, and our lower bound proposed in Bekrar et al. [16], LBKCS. Note that, in all lower bounds the guillotine constraint is relaxed.


### 2.1. The Continuous Lower BoundLc

By splitting each item into unit squares, we obtain a lower boundLc which is called the continuous lower bound:
(2.1)Lc=⌈∑i=1nhiwiW⌉
Let L0=max{Lc,maxi=1,…,nhi}. Martello et al. [4] proved that the absolute worst case performance ratio is equal to 1/2.


### 2.2. First Lower BoundLmmv1 (Martello et al. [4])

This first lower bound presented by Martello et al. [4] is an extension of the one presented in Martello and Toth [17] proposed for the one-dimensional bin packing problem. The idea is to decompose the set of items (J) into three subsets according to their dimensions: the subset of the largest items (J1), the subset of medium items (J2), and the subset of the smallest items (J3).Letα∈[1,W/2],J1={j∈J:wj>W-α},J2={j∈J:W-α≥wj>W/2},J3={j∈J:W/2≥wj≥α}.Observe that(i)
beside a large item we cannot pack any item of the other subsets,(ii)
two items of the subset of medium items cannot be packed one beside the other, and(iii)
beside items of medium items only items of the last class can be packed.The sum of heights of items in the two first classes is a valid lower bound for the 2SP problem,LJ1J2. Some items of J3 cannot be packed beside the first class or the second class. A continuous lower bound on those items is computed and added to LJ1J2.


### 2.3. Second Lower BoundLmmv2 (Martello et al. [4])

The second lower bound proposed by Martello et al. [4] is based on a relaxation of the 2SP problem by cutting each item j∈J into hj unit-height slices of width wj. The authors consider the one-dimensional contiguous bin packing problem (1CBP), where all slices must be packed in bins of size W. The hj slices derived from the item j must be packed into hj contiguous bins. The optimal solution value of (1CBP) is a valid lower bound for the 2SP problem (denoted Lmmv2). This solution is computed by a Branch and Bound. The authors proved that Lmmv2 dominates the previous bounds (Lc and Lmmv1).When the Branch and Bound fails in determining the optimal solution within a fixed time, a new instance of (1CBP) is created from the 2SP instance by cutting each itemj∈J into ⌊hj/2⌋ slices of height 2 or into ⌊hj/3⌋ slices of height 3, and so on, until a solvable (1CBP) instance is produced. Lmmv2 is improved by using a special binary search procedure (for more details see [4]).This lower bound gives the best results on the tested instances, but as we can remark it is complicated and it takes considerable computation time.


### 2.4. Bekrar et al. [14] Lower Bound (LBKCS)

This lower bound is based on the same decomposition presented in Martello et al. [4]. The idea is to calculate the maximum number of items from the last class J3 that can be packed beside items of the second class J2. This allowed us to compute a best bound on the items of J3 that cannot be packed with J2.This lower bound gives good results on the same instances of Martello et al. [4] with the advantage of reducing the computation time.


## 2.1. The Continuous Lower BoundLc

By splitting each item into unit squares, we obtain a lower boundLc which is called the continuous lower bound:
(2.1)Lc=⌈∑i=1nhiwiW⌉
Let L0=max{Lc,maxi=1,…,nhi}. Martello et al. [4] proved that the absolute worst case performance ratio is equal to 1/2.


## 2.2. First Lower BoundLmmv1 (Martello et al. [4])

This first lower bound presented by Martello et al. [4] is an extension of the one presented in Martello and Toth [17] proposed for the one-dimensional bin packing problem. The idea is to decompose the set of items (J) into three subsets according to their dimensions: the subset of the largest items (J1), the subset of medium items (J2), and the subset of the smallest items (J3).Letα∈[1,W/2],J1={j∈J:wj>W-α},J2={j∈J:W-α≥wj>W/2},J3={j∈J:W/2≥wj≥α}.Observe that(i)
beside a large item we cannot pack any item of the other subsets,(ii)
two items of the subset of medium items cannot be packed one beside the other, and(iii)
beside items of medium items only items of the last class can be packed.The sum of heights of items in the two first classes is a valid lower bound for the 2SP problem,LJ1J2. Some items of J3 cannot be packed beside the first class or the second class. A continuous lower bound on those items is computed and added to LJ1J2.


## 2.3. Second Lower BoundLmmv2 (Martello et al. [4])

The second lower bound proposed by Martello et al. [4] is based on a relaxation of the 2SP problem by cutting each item j∈J into hj unit-height slices of width wj. The authors consider the one-dimensional contiguous bin packing problem (1CBP), where all slices must be packed in bins of size W. The hj slices derived from the item j must be packed into hj contiguous bins. The optimal solution value of (1CBP) is a valid lower bound for the 2SP problem (denoted Lmmv2). This solution is computed by a Branch and Bound. The authors proved that Lmmv2 dominates the previous bounds (Lc and Lmmv1).When the Branch and Bound fails in determining the optimal solution within a fixed time, a new instance of (1CBP) is created from the 2SP instance by cutting each itemj∈J into ⌊hj/2⌋ slices of height 2 or into ⌊hj/3⌋ slices of height 3, and so on, until a solvable (1CBP) instance is produced. Lmmv2 is improved by using a special binary search procedure (for more details see [4]).This lower bound gives the best results on the tested instances, but as we can remark it is complicated and it takes considerable computation time.


## 2.4. Bekrar et al. [14] Lower Bound (LBKCS)

This lower bound is based on the same decomposition presented in Martello et al. [4]. The idea is to calculate the maximum number of items from the last class J3 that can be packed beside items of the second class J2. This allowed us to compute a best bound on the items of J3 that cannot be packed with J2.This lower bound gives good results on the same instances of Martello et al. [4] with the advantage of reducing the computation time.


## 3. MIP Formulation and Introduction of Valid Inequalities

This method is based on an adapted formulation of the problem in a mixed integer programming. It is impossible to solve effectively this problem by a commercial solver because of the large number of constraints and variables.In addition, the linear relaxation (relaxation of the integrity constraint) is very poor. This is why we add a family of valid inequalities to the model to improve the lower bound associated to its linear relaxation.


### 3.1. The MIP Formulation for the Two-Dimensional Bin Packing Problem  (Pisinger and Sigurd [18])

The model which we used is adapted from the one presented by Pisinger and Sigurd [18] for the two-dimensional bin packing problem. The latter is based on the modeling technique proposed by Onodera et al. [19] and Chen et al. [20] described as follows.LetJ denote the set of items. (W,H) are, respectively, the width and the length of the bin.Decision Variables
Consider the following variables.(i)
(xi,yi),for alli∈J: the lower-left coordinates of item i.(ii)
mi,for alli∈J: the index of the bin containing rectangle i.(iii)
lij∈{0,1},for alli,j∈J is equal to 1 if rectangle i is located left of rectangle j, that is, lij=1 if xi+wi≤xj.(iv)
bij∈{0,1},for alli,j∈J is equal to 1 if rectangle i is located below rectangle j, that is, bij=1 if yi+hi≤yj.
(3.1)(MIP1){Minvs.t.lij+lji+bij+bji+pij+pji≥1,i,j∈J,i<j,(1)xi-xj+Wlij≤W-wi,i,j∈J,(2)yi-yj+Hbij≤H-hi,i,j∈J,(3)mi-mj+npij≤n-1,i,j∈J,(4)0≤xi≤W-wi,i∈J,(5)0≤yi≤H-hi,i∈J,(6)1≤mi≤v,i∈J,(7)lij,bij,pij∈{0,1},i,j∈J,(8)xi,yi∈R,i∈J,(9)mi,v∈N,i∈J,(10)(v)
pij∈{0,1},for alli,j∈J: pij=1 if mi+1≤mj, that is, pij=1 if rectangle i is packed in a bin before the bin where rectangle j is packed (the index of the bin containing i is less than the bin containing j).(vi)
v is the number of used bins.Constraints (1) avoids the overlapping between items, so item i should be in the left or the right side of item j, and, in the same time, it should be located above or below item j. In constraint (2), if lij=1, we have: xj≥xi+wi, which means that item i is located left to item j. If bij=1 in constraint (3), we deduce that item i is located below item j. In constraint (4), we determine if item i is packed “before” item j, pij=1 (the index of the bin containing i is less than the index of the bin containing j). These three constraints determine the position of item i relative to the position of item j. Constraints (5) and (6) ensure that the items do not exceed the edges of the bins.


### 3.2. MIP Formulation for the Two-Dimensional Strip Packing Problem 2SP

We adapted the model of Pisinger and Sigurd [18] for the 2SP problem. Constraints (4), (7), and (10) are eliminated since they concern the bin packing problem. The length of the bin H is replaced by an upper bound Hh corresponding to the length of the strip.The2SP problem can be formulated in the following MIP model, denoted (MIP2):
(3.2)(MIP2){MinHHs.t.lij+lji+bij+bji≥1,i,j∈J,i<j,(1)xi-xj+Wlij≤W-wi,i,j∈J,(2)yi-yj+Hhbij≤Hh-hi,i,j∈J,(3)0≤xi≤W-wi,i∈J(4)0≤yi≤Hh-hi,i∈J(5)HH≥yi+hi,i∈J(6)lij,bij∈{0,1},i,j∈J,(7)HH,xi,yi∈R,i∈J.(8)The valid inequalities are added toMIP2 in which we relax the integrity constraint (constraints (7) are replaced by the constraints 0≤li,j≤1 and 0≤bi,j≤1, resp.).In the following, we propose a series of valid inequalities to improve the lower bound of the2SP problem.


### 3.3. Inequalities Related to the Parallel-Machine Scheduling Problem andyi

This bound is inspired from the principle proposed in Kacem [21] applied to the tardiness minimization on a single machine. Kacem [21] associates fictitious weights to jobs to be scheduled and computes a lower bound on the weighted flow-time of the optimal solution. Therefore, for each vector of fictitious weights, he obtained a valid inequality. For the studied problem, we consider the items as a set of jobs (i.e., each item i is a set of wi jobs of duration hi) to be scheduled on W identical parallel machines. Hence, the variables (yi+hi) represents the completion time of the item i (all the jobs corresponding to this item). Clearly, feasible packing can be viewed as a schedule of these fictitious jobs. To each item i, we associate a fictitious weight γi. We use an iterative method to calculate different values of weights. For each vector of fictitious weights, we obtain a valid inequality. We deduce the following valid inequality based on the lower bound of Eastman et al. [22] for the problem of minimizing the weighted flow-time on identical parallel machines(Pm∥∑wiCi):
(3.3)∑i=1nγiwi(yi+hi)≥1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi,
where [i] is the item in position i when the set J is sorted in non-decreasing order of hi/γi. This constraint is valid for any positive vector of fictitious weight γ=(γi)1≤i≤n. We generated several constraints of this type.Recall that the bound of Eastman et al. [22] for the Pm∥∑‍wiCi problem is given by the following equation:
(3.4)LBM=LB1M+M-12M∑j=1Nwjpj,
where LB1 is the optimal solution of the problem on a single machine. M is the number of machines, and N is the number of jobs. wj and pj are, respectively, the weight and the duration of the job j.


### 3.4. Inequalities Related to the Parallel-Machine Scheduling Problem andxi

This inequality consists in the same principle. We consider items as jobs; each itemi is considered as a set of hi jobs of duration wi. These jobs are to be scheduled on Hh identical machines. Therefore, the variables (xi+wi) represent the completion time of the item i. It is obvious that any feasible packing can be viewed as a scheduling of fictitious jobs.To each jobi, a fictitious weight γi is associated. Hence, we deduce the following valid inequalities that used the bound of Eastman et al. [22] for the problem Pm∥∑wiCi:
(3.5)∑i=1nγihi(xi+wi)≥1Hh∑i=1nγ[i](h[i]∑j=1i-1w[j]h[j]+∑j=1h[i]jw[i])+Hh-12Hh∑i=1nγiwihi,
where [i] is the ith item when the set J is sorted in nondecreasing order of wi/γi.This constraint is valid for any vectorγ=(γi)1≤i≤n of fictitious weights. For this reason, we generate several constraints of this family.


### 3.5. Inequalities Linkingyi and HH

By solving the model with the previous cuts (Sections3.3 and 3.4), we noticed that in the obtained solutions items are in the bottom and in the right of the strip to respect these inequalities. To avoid this problem, we adopted the solution which consists in bounding the weighted sum of yi.We apply the same reasoning used in the previous inequality, and then we can obtain a valid inequality able to linkyi and HH. Indeed, by replacing (yi′=HH-yi, i.e., yi=HH-yi′) and using a similar notation as in the first family (Section 3.3), we can introduce the following inequality:
(3.6)∑i=1nγiwiyi′≥1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi,
or
(3.7)H∑i=1nγiwi≥∑i=1nγiwiyi+1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi.


### 3.6. Inequalities Bounding the Weighted Sum onxi

This inequality is similar to the previous one. It is based on the following transformation of variables:xi′=W-xi. It is described as follows:
(3.8)W∑i=1nγihi≥∑i=1nγihixi+1Hh∑i=1nγ[i](h[i]∑j=1i-1‍w[j]h[j]+∑j=1h[i]‍jw[i])+Hh-12Hh∑i=1nγiwihi.


### 3.7. Inequalities for large items and high items

For the set of large items such that each pair cannot be packed side by side, we can consider it as items of widthW. Indeed, let 𝒢={i∣for allj∈𝒢 and j≠i, we have wi+wj>W}. The following constraints are valid inequalities:
(3.9)li,j+lj,i=0∀i,j∈𝒢,j≠i,bi,j+bj,i=1∀i,j∈𝒢,j≠i
Let (γi)1≤i≤|𝒢| be a vector of fictitious weights. [i]1≤i≤|𝒢| represents the ith item of the set 𝒢 by sorting the items in nondecreasing order of hi/γi. The following constraint defines a valid inequality:
(3.10)∑i∈𝒢γi(yi+hi)≥∑i=1|𝒢|γ[i](∑j=1ih[j]).
Obviously, the  following constraint is also a valid inequality:
(3.11)HH∑i∈𝒢γi≥∑i∈𝒢γiyi+∑i=1|𝒢|γ[i](∑j=1ih[j])
We use the same reasoning in the previous cut. Let 𝒢′={i∣for allj∈𝒢′
and
j≠i,wehavehi+hj>Hh}. The following constraints are valid inequalities:
(3.12)li,j+lj,i=1∀i,j∈𝒢′,j≠i,bi,j+bj,i=0∀i,j∈𝒢′,j≠i.Let(γi)1≤i≤|𝒢′| be a vector of fictitious weights. [i]1≤i≤|𝒢′| represents the
ith item in the set 𝒢′ when it is sorted in the nondecreasing order of wi/γi. The following constraint is a valid inequality:
(3.13)∑i∈𝒢′γi(xi+wi)≥∑i=1|𝒢′|γ[i](∑j=1iw[j]).
The following constraint is also a valid inequality:
(3.14)W∑i∈𝒢′γi≥∑i∈𝒢′γixi+∑i=1|𝒢′|γ[i](∑j=1iw[j]).


### 3.8. Inequalities with Identical Fictitious Weights

It is obvious that all the previous cuts remain valid for the special case when the fictitious weights are equal to 1. However, it is more advantageous in this case to apply theShortest Processing Time (SPT) rule instead of the Eastman bound.We established a simple procedure to apply this rule to our problem in which we consider items as jobs.


### 3.9. Valid Constraints Avoiding the Overlapping of Items in the Bottom of the Strip

When we tested the previous cuts, we noticed in some obtained solutions that items overlap in the bottom of the strip (yi=0) while the sum of their widths exceeds the width of the strip W. Therefore, we introduced a special cut to avoid this situation for which a constraint of the initial problem is violated.Let𝒮 be the real solution violated and 𝒱={i∣yi=0in𝒮}. We have ∑i∈𝒱wi>W. We apply for the items of this set 𝒱 a cut of the same type of the first one with fictitious weights equal to 1 (Section 3.3). Obviously, we do not use the bound of Eastman but the generalized SPT mentioned previously. Let SPT(𝒱) be the value of this bound calculated for the set 𝒱. The following constraint is a valid cut:
(3.15)∑i∈𝒱wi(yi+hi)≥SPT(𝒱).We observed that, in some solutions, items overlap on the other sides of the strip. Using the same approach, we can see that this cut can be immediately generalized for the items on the top, on the right edge, and the left edge of the strip.


### 3.10. Valid Constraints Based on Precedence Considerations

For allj≤n, the following relations hold due to the precedence considerations:
(3.16)yj≥∑i=1∩i≠ji=nhiwibi,jW,xj≥∑i=1∩i≠ji=nhiwili,jHh,yj+hj≤HH-∑i=1∩i≠ji=nhiwibj,iW,xj+wj≤W-∑i=1∩i≠ji=nhiwilj,iHh.


## 3.1. The MIP Formulation for the Two-Dimensional Bin Packing Problem  (Pisinger and Sigurd [18])

The model which we used is adapted from the one presented by Pisinger and Sigurd [18] for the two-dimensional bin packing problem. The latter is based on the modeling technique proposed by Onodera et al. [19] and Chen et al. [20] described as follows.LetJ denote the set of items. (W,H) are, respectively, the width and the length of the bin.Decision Variables
Consider the following variables.(i)
(xi,yi),for alli∈J: the lower-left coordinates of item i.(ii)
mi,for alli∈J: the index of the bin containing rectangle i.(iii)
lij∈{0,1},for alli,j∈J is equal to 1 if rectangle i is located left of rectangle j, that is, lij=1 if xi+wi≤xj.(iv)
bij∈{0,1},for alli,j∈J is equal to 1 if rectangle i is located below rectangle j, that is, bij=1 if yi+hi≤yj.
(3.1)(MIP1){Minvs.t.lij+lji+bij+bji+pij+pji≥1,i,j∈J,i<j,(1)xi-xj+Wlij≤W-wi,i,j∈J,(2)yi-yj+Hbij≤H-hi,i,j∈J,(3)mi-mj+npij≤n-1,i,j∈J,(4)0≤xi≤W-wi,i∈J,(5)0≤yi≤H-hi,i∈J,(6)1≤mi≤v,i∈J,(7)lij,bij,pij∈{0,1},i,j∈J,(8)xi,yi∈R,i∈J,(9)mi,v∈N,i∈J,(10)(v)
pij∈{0,1},for alli,j∈J: pij=1 if mi+1≤mj, that is, pij=1 if rectangle i is packed in a bin before the bin where rectangle j is packed (the index of the bin containing i is less than the bin containing j).(vi)
v is the number of used bins.Constraints (1) avoids the overlapping between items, so item i should be in the left or the right side of item j, and, in the same time, it should be located above or below item j. In constraint (2), if lij=1, we have: xj≥xi+wi, which means that item i is located left to item j. If bij=1 in constraint (3), we deduce that item i is located below item j. In constraint (4), we determine if item i is packed “before” item j, pij=1 (the index of the bin containing i is less than the index of the bin containing j). These three constraints determine the position of item i relative to the position of item j. Constraints (5) and (6) ensure that the items do not exceed the edges of the bins.


## 3.2. MIP Formulation for the Two-Dimensional Strip Packing Problem 2SP

We adapted the model of Pisinger and Sigurd [18] for the 2SP problem. Constraints (4), (7), and (10) are eliminated since they concern the bin packing problem. The length of the bin H is replaced by an upper bound Hh corresponding to the length of the strip.The2SP problem can be formulated in the following MIP model, denoted (MIP2):
(3.2)(MIP2){MinHHs.t.lij+lji+bij+bji≥1,i,j∈J,i<j,(1)xi-xj+Wlij≤W-wi,i,j∈J,(2)yi-yj+Hhbij≤Hh-hi,i,j∈J,(3)0≤xi≤W-wi,i∈J(4)0≤yi≤Hh-hi,i∈J(5)HH≥yi+hi,i∈J(6)lij,bij∈{0,1},i,j∈J,(7)HH,xi,yi∈R,i∈J.(8)The valid inequalities are added toMIP2 in which we relax the integrity constraint (constraints (7) are replaced by the constraints 0≤li,j≤1 and 0≤bi,j≤1, resp.).In the following, we propose a series of valid inequalities to improve the lower bound of the2SP problem.


## 3.3. Inequalities Related to the Parallel-Machine Scheduling Problem andyi

This bound is inspired from the principle proposed in Kacem [21] applied to the tardiness minimization on a single machine. Kacem [21] associates fictitious weights to jobs to be scheduled and computes a lower bound on the weighted flow-time of the optimal solution. Therefore, for each vector of fictitious weights, he obtained a valid inequality. For the studied problem, we consider the items as a set of jobs (i.e., each item i is a set of wi jobs of duration hi) to be scheduled on W identical parallel machines. Hence, the variables (yi+hi) represents the completion time of the item i (all the jobs corresponding to this item). Clearly, feasible packing can be viewed as a schedule of these fictitious jobs. To each item i, we associate a fictitious weight γi. We use an iterative method to calculate different values of weights. For each vector of fictitious weights, we obtain a valid inequality. We deduce the following valid inequality based on the lower bound of Eastman et al. [22] for the problem of minimizing the weighted flow-time on identical parallel machines(Pm∥∑wiCi):
(3.3)∑i=1nγiwi(yi+hi)≥1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi,
where [i] is the item in position i when the set J is sorted in non-decreasing order of hi/γi. This constraint is valid for any positive vector of fictitious weight γ=(γi)1≤i≤n. We generated several constraints of this type.Recall that the bound of Eastman et al. [22] for the Pm∥∑‍wiCi problem is given by the following equation:
(3.4)LBM=LB1M+M-12M∑j=1Nwjpj,
where LB1 is the optimal solution of the problem on a single machine. M is the number of machines, and N is the number of jobs. wj and pj are, respectively, the weight and the duration of the job j.


## 3.4. Inequalities Related to the Parallel-Machine Scheduling Problem andxi

This inequality consists in the same principle. We consider items as jobs; each itemi is considered as a set of hi jobs of duration wi. These jobs are to be scheduled on Hh identical machines. Therefore, the variables (xi+wi) represent the completion time of the item i. It is obvious that any feasible packing can be viewed as a scheduling of fictitious jobs.To each jobi, a fictitious weight γi is associated. Hence, we deduce the following valid inequalities that used the bound of Eastman et al. [22] for the problem Pm∥∑wiCi:
(3.5)∑i=1nγihi(xi+wi)≥1Hh∑i=1nγ[i](h[i]∑j=1i-1w[j]h[j]+∑j=1h[i]jw[i])+Hh-12Hh∑i=1nγiwihi,
where [i] is the ith item when the set J is sorted in nondecreasing order of wi/γi.This constraint is valid for any vectorγ=(γi)1≤i≤n of fictitious weights. For this reason, we generate several constraints of this family.


## 3.5. Inequalities Linkingyi and HH

By solving the model with the previous cuts (Sections3.3 and 3.4), we noticed that in the obtained solutions items are in the bottom and in the right of the strip to respect these inequalities. To avoid this problem, we adopted the solution which consists in bounding the weighted sum of yi.We apply the same reasoning used in the previous inequality, and then we can obtain a valid inequality able to linkyi and HH. Indeed, by replacing (yi′=HH-yi, i.e., yi=HH-yi′) and using a similar notation as in the first family (Section 3.3), we can introduce the following inequality:
(3.6)∑i=1nγiwiyi′≥1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi,
or
(3.7)H∑i=1nγiwi≥∑i=1nγiwiyi+1W∑i=1nγ[i](w[i]∑j=1i-1w[j]h[j]+∑j=1w[i]jh[i])+W-12W∑i=1nγiwihi.


## 3.6. Inequalities Bounding the Weighted Sum onxi

This inequality is similar to the previous one. It is based on the following transformation of variables:xi′=W-xi. It is described as follows:
(3.8)W∑i=1nγihi≥∑i=1nγihixi+1Hh∑i=1nγ[i](h[i]∑j=1i-1‍w[j]h[j]+∑j=1h[i]‍jw[i])+Hh-12Hh∑i=1nγiwihi.


## 3.7. Inequalities for large items and high items

For the set of large items such that each pair cannot be packed side by side, we can consider it as items of widthW. Indeed, let 𝒢={i∣for allj∈𝒢 and j≠i, we have wi+wj>W}. The following constraints are valid inequalities:
(3.9)li,j+lj,i=0∀i,j∈𝒢,j≠i,bi,j+bj,i=1∀i,j∈𝒢,j≠i
Let (γi)1≤i≤|𝒢| be a vector of fictitious weights. [i]1≤i≤|𝒢| represents the ith item of the set 𝒢 by sorting the items in nondecreasing order of hi/γi. The following constraint defines a valid inequality:
(3.10)∑i∈𝒢γi(yi+hi)≥∑i=1|𝒢|γ[i](∑j=1ih[j]).
Obviously, the  following constraint is also a valid inequality:
(3.11)HH∑i∈𝒢γi≥∑i∈𝒢γiyi+∑i=1|𝒢|γ[i](∑j=1ih[j])
We use the same reasoning in the previous cut. Let 𝒢′={i∣for allj∈𝒢′
and
j≠i,wehavehi+hj>Hh}. The following constraints are valid inequalities:
(3.12)li,j+lj,i=1∀i,j∈𝒢′,j≠i,bi,j+bj,i=0∀i,j∈𝒢′,j≠i.Let(γi)1≤i≤|𝒢′| be a vector of fictitious weights. [i]1≤i≤|𝒢′| represents the
ith item in the set 𝒢′ when it is sorted in the nondecreasing order of wi/γi. The following constraint is a valid inequality:
(3.13)∑i∈𝒢′γi(xi+wi)≥∑i=1|𝒢′|γ[i](∑j=1iw[j]).
The following constraint is also a valid inequality:
(3.14)W∑i∈𝒢′γi≥∑i∈𝒢′γixi+∑i=1|𝒢′|γ[i](∑j=1iw[j]).


## 3.8. Inequalities with Identical Fictitious Weights

It is obvious that all the previous cuts remain valid for the special case when the fictitious weights are equal to 1. However, it is more advantageous in this case to apply theShortest Processing Time (SPT) rule instead of the Eastman bound.We established a simple procedure to apply this rule to our problem in which we consider items as jobs.


## 3.9. Valid Constraints Avoiding the Overlapping of Items in the Bottom of the Strip

When we tested the previous cuts, we noticed in some obtained solutions that items overlap in the bottom of the strip (yi=0) while the sum of their widths exceeds the width of the strip W. Therefore, we introduced a special cut to avoid this situation for which a constraint of the initial problem is violated.Let𝒮 be the real solution violated and 𝒱={i∣yi=0in𝒮}. We have ∑i∈𝒱wi>W. We apply for the items of this set 𝒱 a cut of the same type of the first one with fictitious weights equal to 1 (Section 3.3). Obviously, we do not use the bound of Eastman but the generalized SPT mentioned previously. Let SPT(𝒱) be the value of this bound calculated for the set 𝒱. The following constraint is a valid cut:
(3.15)∑i∈𝒱wi(yi+hi)≥SPT(𝒱).We observed that, in some solutions, items overlap on the other sides of the strip. Using the same approach, we can see that this cut can be immediately generalized for the items on the top, on the right edge, and the left edge of the strip.


## 3.10. Valid Constraints Based on Precedence Considerations

For allj≤n, the following relations hold due to the precedence considerations:
(3.16)yj≥∑i=1∩i≠ji=nhiwibi,jW,xj≥∑i=1∩i≠ji=nhiwili,jHh,yj+hj≤HH-∑i=1∩i≠ji=nhiwibj,iW,xj+wj≤W-∑i=1∩i≠ji=nhiwilj,iHh.


## 4. Upper Bounds for the 2SP Problem

### 4.1. The Two-Dimensional Level Algorithms

Many papers proposed  approximation algorithms for 2D Strip Packing Problem, but few of them consider the guillotine constraint, citing from this category: Fernandez de la Vega and Zissimopoulos [5], Lesh et al. [6], Kenyon and Rémila [7], Zhang et al. [8], and Cui et al. [13]To maintain this constraint, most of the proposed approaches are level algorithms, that is, the strip packing is obtained by placing the items, from left to right, in rows forming levels. The set of items is sorted in decreasing order of their heights. The first item packed in the bottom-left of the strip initializes the first level. The remaining items are packed in the initialized levels according to the used strategy (Best Fit (BFDH), First Fit (FFDH), Next Fit (NFDH), etc.). If no initialized level can contain the current item, a new level is initialized.


### 4.2. The Best Shelf Heuristic Filling (BSHF)

The Shelf Heuristic Filling (SHF) algorithm was proposed previously by Ben Messaoud et al. [23]. It is a generalization of the two-dimensional level algorithms (for more details about level algorithms like Floor Ceiling, see Lodi et al. [24]).The main idea of SHF algorithm is to exploit the nonused area in each shelf. It makes it possible to pack items one over the other in the same shelf, which is not permitted in the level algorithms. This packing is achieved by respecting the guillotine constraint. For this purpose, SHF uses the definition of the available rectangle: the rectangle which has its bottom left corner as anavailable point. The available point can be the down-right or the top-left corner of an item already packed. Items are sorted in nonincreasing order of heights. The first item (the tallest one) is packed into the first available rectangle (the lowest). The leftmost item initializes a shelf with a height equal to the height of this item. After every item-packing, the set of available rectangles is updated in order to maintain the guillotine constraint. The updating consists in reducing the dimensions of available rectangles which overlap with the packed items. The item-packing creates two new available rectangles. This procedure is repeated until the last item is packed.In Bekrar et al. [14], we proposed some strategies to improve the SHF algorithm. We called this new heuristic BSHF (Best SHF). We tested different rules of sorting items. We used the Best Fit rule to pack items, and we proposed a new way to update the list of available rectangles. The Best Fit rule consists in packing items in the available rectangle that minimizes the unused surface. This algorithm gives good results on large instances in few seconds. The average waste rate is estimated at 9%.


### 4.3. A New Heuristic for Solving the 2D Strip Packing Problem

In this subsection we present a new heuristic that is able to solve approximately the 2SP problem with guillotine cuts. Unlike previous heuristics (BSHF and BFDH), the items are not packed according to levels.The items are sorted in different orders (decreasing heights, decreasing widths, decreasing areas).The items are then packed in available rectangle as it is done in BSHF. However, the set of available rectangles is not updated in the same manner. When the current item can fill in an available rectangle, we check if the obtained pattern is guillotine using the procedure proposed by Ben Messaoud et al. [23]. If this pattern is guillotine, then the packing is validated and the next item is treated; otherwise, we try with another available rectangle.During the packing, no shelf is created, hence the name of the algorithm: Nonshelf Heuristic Filling. The heuristic is adapted to the two-dimensional bin packing problem; when the current item cannot be packed in the open bins, a new bin is initialized.The updating procedure in the BSHF heuristic aims to maintain the guillotine property of the patterns. In the NSHF heuristic, the updating procedure aims tocorrect the dimension of the available rectangles that are overlapping with the packed item.LetRi(xi,yi,wi,hi) be an available rectangle that has a width wi and a height hi and position (xi,yi). The bottom-left point coordinates of Ri are xi and yi. Let an item p with a width wp and a height hp be packed in the position (xp,yp). We distinguish two possibilities.(1)
Case  1. xp≥xi, the item p is located in the right side of Ri. If p overlaps with Ri, (i.e., yp+hp>yi) then the width of Ri is reduced (Figure 2(a)): Ri(xi,yi,xp-xi,hi).(2)
Case  2. xp≤xi, the item p is located in the left side of Ri. If p overlaps with Ri (i.e., xp+wp>xi), then the height of Ri is reduced (Figure 2(b)): Ri(xi,yi,wi,yp-yi).Updating the set of available rectangles inNSHF.
(a)
The item is located in the right side ofRi(b)
The item is located in the left side ofRi


## 4.1. The Two-Dimensional Level Algorithms

Many papers proposed  approximation algorithms for 2D Strip Packing Problem, but few of them consider the guillotine constraint, citing from this category: Fernandez de la Vega and Zissimopoulos [5], Lesh et al. [6], Kenyon and Rémila [7], Zhang et al. [8], and Cui et al. [13]To maintain this constraint, most of the proposed approaches are level algorithms, that is, the strip packing is obtained by placing the items, from left to right, in rows forming levels. The set of items is sorted in decreasing order of their heights. The first item packed in the bottom-left of the strip initializes the first level. The remaining items are packed in the initialized levels according to the used strategy (Best Fit (BFDH), First Fit (FFDH), Next Fit (NFDH), etc.). If no initialized level can contain the current item, a new level is initialized.


## 4.2. The Best Shelf Heuristic Filling (BSHF)

The Shelf Heuristic Filling (SHF) algorithm was proposed previously by Ben Messaoud et al. [23]. It is a generalization of the two-dimensional level algorithms (for more details about level algorithms like Floor Ceiling, see Lodi et al. [24]).The main idea of SHF algorithm is to exploit the nonused area in each shelf. It makes it possible to pack items one over the other in the same shelf, which is not permitted in the level algorithms. This packing is achieved by respecting the guillotine constraint. For this purpose, SHF uses the definition of the available rectangle: the rectangle which has its bottom left corner as anavailable point. The available point can be the down-right or the top-left corner of an item already packed. Items are sorted in nonincreasing order of heights. The first item (the tallest one) is packed into the first available rectangle (the lowest). The leftmost item initializes a shelf with a height equal to the height of this item. After every item-packing, the set of available rectangles is updated in order to maintain the guillotine constraint. The updating consists in reducing the dimensions of available rectangles which overlap with the packed items. The item-packing creates two new available rectangles. This procedure is repeated until the last item is packed.In Bekrar et al. [14], we proposed some strategies to improve the SHF algorithm. We called this new heuristic BSHF (Best SHF). We tested different rules of sorting items. We used the Best Fit rule to pack items, and we proposed a new way to update the list of available rectangles. The Best Fit rule consists in packing items in the available rectangle that minimizes the unused surface. This algorithm gives good results on large instances in few seconds. The average waste rate is estimated at 9%.


## 4.3. A New Heuristic for Solving the 2D Strip Packing Problem

In this subsection we present a new heuristic that is able to solve approximately the 2SP problem with guillotine cuts. Unlike previous heuristics (BSHF and BFDH), the items are not packed according to levels.The items are sorted in different orders (decreasing heights, decreasing widths, decreasing areas).The items are then packed in available rectangle as it is done in BSHF. However, the set of available rectangles is not updated in the same manner. When the current item can fill in an available rectangle, we check if the obtained pattern is guillotine using the procedure proposed by Ben Messaoud et al. [23]. If this pattern is guillotine, then the packing is validated and the next item is treated; otherwise, we try with another available rectangle.During the packing, no shelf is created, hence the name of the algorithm: Nonshelf Heuristic Filling. The heuristic is adapted to the two-dimensional bin packing problem; when the current item cannot be packed in the open bins, a new bin is initialized.The updating procedure in the BSHF heuristic aims to maintain the guillotine property of the patterns. In the NSHF heuristic, the updating procedure aims tocorrect the dimension of the available rectangles that are overlapping with the packed item.LetRi(xi,yi,wi,hi) be an available rectangle that has a width wi and a height hi and position (xi,yi). The bottom-left point coordinates of Ri are xi and yi. Let an item p with a width wp and a height hp be packed in the position (xp,yp). We distinguish two possibilities.(1)
Case  1. xp≥xi, the item p is located in the right side of Ri. If p overlaps with Ri, (i.e., yp+hp>yi) then the width of Ri is reduced (Figure 2(a)): Ri(xi,yi,xp-xi,hi).(2)
Case  2. xp≤xi, the item p is located in the left side of Ri. If p overlaps with Ri (i.e., xp+wp>xi), then the height of Ri is reduced (Figure 2(b)): Ri(xi,yi,wi,yp-yi).Updating the set of available rectangles inNSHF.
(a)
The item is located in the right side ofRi(b)
The item is located in the left side ofRi


## 5. The Dichotomic Algorithm

In this section we present an exact method to solve the problem to optimality. The principle of this method was introduced first by Hifi [12]. Its effectiveness has been shown on other packing problems.The algorithm starts by computing the lower boundLB using the cutting plane method described in Section 3. An upper bound, UB, is then computed by the heuristic BSHF and NSHF described in Section 4. If the upper bound is equal to the lower bound, then this is the optimal solution. If it is not the case, we search the optimal length included in the interval [LB,UB] for which the items can be packed.To reduce the search space, we use a dichotomic search. The Dichotomic Algorithm is sketched in Algorithm1. The principle of this method was exploited in a previous work of Bekrar et al. [14].When a heightS is chosen from the interval [LB,UB], a decision problem is generated: could the set of items be packed in the bin of width W and height S? The problem of determining if a set of rectangles can be packed in a larger rectangle of fixed size is well known as the two-dimensional orthogonal packing problem (2OPP).Several papers were interested in this problem. Fekete et al. [25] proposed an exact algorithm based on the graph theory. Clautiaux et al. [26, 27] proposed two approaches to solve 2OPP to optimality. The first one is a two-step algorithm where they determined the x-coordinates of items in the first step, then they checked the feasibility of the obtained configurations in the second step Clautiaux et al. [26]. In Clautiaux et al. [27], they used another approach based on constraint programming. The constraint programming approach was also used by Pisinger and Sigurd [18].We choose to use the last approach in our algorithm, because it maintains the guillotine constraint, and we have experimentally checked that it has less computational time.The (2OPP) is solved by a constraint satisfaction program (CSP). Constraint Satisfaction Programming (CSP) is a field of Artificial Intelligence that looks to solve problems modeled by a set of constraints imposed on a finite set of variables. The set of variables is defined in a domain: a finite set of values for each variable. A solution to CSP is a complete assignment of variables satisfying all the constraints.For each pair of itemsi,j the domain Mij is associated. Mij={left,right, below,above} determines the possible relative placements among which we should choose at least one. rij is the variable that determines the position of item i according to the position of item j. The different relations between items can be defined asrij∈Mij,i,j∈{1,…,n}, i≠j,rij=left⇒xi+wi≤xj,i,j∈{1,…,n}, i≠j,rij=right⇒xj+wj≤xi,i,j∈{1,…,n}, i≠j,rij=below⇒yi+hi≤yj,i,j∈{1,…,n}, i≠j,rij=above⇒yj+hj≤yi,i,j∈{1,…,n}, i≠j,0≤xi≤W-wi,i∈{1,…,n},0≤yi≤H-hi,i∈{1,…,n}.Initially all relationsrij are set to undefined.In each iteration of the algorithm, two rectanglesi and j are considered, and a value is assigned to rij from Mij. It is then checked whether a feasible assignment of coordinates exists by respecting the current relations rij. If the coordinate check fails, the algorithm backtracks. Otherwise a recursive call is done.


## 6. Computational Results

To evaluate the proposed algorithms, we compare them to some literature algorithms. The heuristicsNSHF and BSHF are compared to the best of the algorithm proposed by Hifi [28] and BFDH heuristic (Chung et al. [1]). The dichotomic algorithm is compared with the branch and bound of Bekrar et al. [16] and the algorithm of Hifi [12].All our algorithms were coded in C++ and tested on a Pentium Xeon with 2.7 GHz of RAM.


### 6.1. Computational Results for Heuristics

We test our heuristicsBSHF and NSHF to literature heuristics. Hifi [12] proposed four heuristics: FIA, SIA, HC/FIA, and HC/SIA. We compare the best values of those algorithms to our heuristics on the large instances studied by Hifi [12].In Table1, we present the results. The following information is given:Table 1
Comparison ofBSHF and NSHF heuristics and literature heuristics.
NamenWLBBestHBestHLBBFDHBFDHLBXSHFXSHFLBSCPL111042549571.16621.26541.10SCPL21201271271651.291701.331541.21SCPL3842251561811.161821.161781.14SCPL410235659671.13771.30671.13SCPL51021651291471.141481.141401.08SCPL65665719241.26281.47221.15SCPL71393571211261.041971.621351.11SCPL815647564771.20781.21711.10SCPL9117175901021.13991.10991.10Average90.44105.111.17115.661.29102.221.12(i)
n and W: respectively, the number of items and the strip width,(ii)
LB: the value of the linear lower bound,(iii)
BestH: the best value obtained by Hifi's heuristics (FIA, SIA, HC/FIA, HC/SIA),(iv)
XSHF: the best value obtained by our heuristics NSHF and BSHF(v)
BFDH: results of BFDH heuristic, and(vi)
A/LB: the ratio of each heuristic by the lower bound (A represents the value of solution obtained by the heuristic). As we can see in Table 1, our algorithms allow to obtain satisfactory solutions on the tested instances. It improves generally the existing solutions. Note that Hifi's algorithm remains the best for instance (SCPL7). This confirms the interest of our heuristics.


### 6.2. Computational Results on Hifi’s Instances

The first tests are carried out on the instances of Hifi [12]. The dichotomic algorithm is compared to the branch and bound of Bekrar et al. [14] and to the best-first search MVB algorithm of Hifi [12]. The 25 instances are of various sizes and are available at http://www.laria.u-picardie.fr/hifi/OR-Benchmark/Strip-cutting/Strip-cutting.html.In Table2, we give for each problem instance the following:Table 2
Results of exact algorithms on Hifi’s instances.
NamenWLminLBUBOPTTDichThTbSCP110513131313<0.01<0.1<0.01SCP211440404040<0.011.2<0.01SCP315614141914403.8319.447.07SCP41161920222041.224.18.75SCP582020202020<0.010.1<0.01SCP673032383838<0.013.4<0.01SCP7815121315140.031.40.23SCP812151717201710.452.39.57SCP91227686869680.010.10.14SCP10850807980800.010.50.12SCP111027474749480.120.714.89SCP121881343438340.012.7—SCP13770425056500.116.82.38SCP141010063638369126.6548.727.57SCP15144534343534445.94165.7—SCP1614632333533201.83181.4—SCP1794234393939<0.01323.6<0.01SCP181070909110410114.74327.836.43SCP1912525262626<0.01473.0<0.01SCP201015192022210.69673.942.73SCP21113013513514514512.342001.8654.31SCP222290343443341597.91757.8—SCP2312152833353510.031031.9401.97SCP2410501051051231145.265585.7329.34SCP25152536364136116.112662.9—(i)
the widthW of the strip and the number of items n,(ii)
values of upper boundUB and lower bound LB computed by the methods described previously,(iii)
values of lower boundLmin computed by Hifi [12],(iv)
values of the optimal solutionOPT, and(v)
the computational time of Hifi [12] Th, that of our branch and bound Tb, and that of the dichotomic algorithm TDich (in seconds).Note that we carry out our algorithms for one hour, and if the optimal solution was not found (marked by “—”), we take the best solution found. Table2 shows that the dichotomic algorithm could optimally solve all the tested instances of Hifi [12] and outperform our previous branch-and-bound algorithm in computational time, and on only few instances from 25 the dichotomic algorithm was not better. Note that Hifi used a Sparc-Server20 (module 712 MP) to test his algorithm. For this reason, it is not possible to make a reliable comparison in terms of the computation time. However, we prefer to report these results for information completeness.


### 6.3. Computational Results on Martello’s Instances

The second tests were carried out on a series of instances from literature. All instances are available athttp://www.or.deis.unibo.it/research.html.We compare the dichotomic algorithm to the branch and bound of Bekrar et al. [14]. For each problem, Table 3 gives the following information:Table 3
Results of exact algorithms on literature instances.
NamenWLmmv2LBUBSDichSB&BTDichTB&Bht1162020202020200.01<0.01ht21720202023202067.45TLht316202020252020197.53353.10ht425401515171515874.05TLht525401515161515571.65TLht6254015151515150.00<0.01ht7286030303331332045.34TLht8296030313632342101.33TLht9286030303030300.00<0.00cgcut116102323252323323.54TLcgcut2237063648267722012.24TLcgcut36270636637714647676TLTLgcut110250101610161016101610160.00<0.00gcut22025011331133134912841349TLTLgcut33025018031803181018101810TLTLgcut45025029342934321429563214TLTLngcut11010232123232316.732.58ngcut2171030303130301112.61TLngcut321102828332929724.31TLngcut471020172020200.100.01ngcut514103636373636120.120.01ngcut6151031303631311091.33TLngcut782020202020200.00<0.00ngcut813203332383333188.64TLngcut9182049495951531531.20TLngcut1013308058808080970.02TLngcut111530525060525255.84TLngcut122230878796878721.04TLbeng120253030353030608.41TLbeng240255758605960TLTLbeng360258485898889TLTLbeng48025107108112111112TLTLbeng510025134134138138138TLTLbeng6404036373938393152.27TLbeng780406767727072TLTLbeng812040101101108108108TLTLbeng916040126126130130130TLTLbeng1020040156156158158158TLTL(i)
problem name and values ofn and W,(ii)
values of the our lower boundLB and values of the upper bound UB,(iii)
values of lower boundLmmv2 computed by Martello et al. [4],(iv)
values of the solutions: branch and bound (SB&B) and dichotomic algorithm (SDich), and(v)
the computation time of the branch and boundTB&B and that of the dichotomic algorithm TDich (in seconds).As we can see in Table3, the dichotomic algorithm often outperforms the Branch and Bound both in the number of solved instances and in the computation time.


### 6.4. Computational Results on Randomly Instances

To further analyze the performance of the algorithms, we compare the branch-and-bound method and the dichotomic algorithm on instances randomly generated. We adapt the classes of instances proposed by Berkey and Wang [2] and Martello and Vigo [24] for the two-dimensional bin packing problem to the strip packing problem. These instances consist of ten classes of problems. For each class, there are 40 instances: 10 with 10 rectangles, 10 with 15 rectangles, 10 with 20 rectangles, and 10 with 25 rectangles. The first six classes have been proposed by Berkey and Wang [2]:j=1,…,n. n=10,15,20,25,Class I: wjandhjuniformly random in[1,10],W=10;Class II: wjandhjuniformly random in[1,10],W=30;Class III: wjandhjuniformly random in[1,35],W=40;Class IV: wjandhjuniformly random in[1,35],W=100;Class V: wjandhjuniformly random in[1,100],W=100;Class VI: wjandhjuniformly random in[1,100],W=300.The remainder four classes were inspired from Martello and Vigo [24]. The items are classified into four types:Type 1: wj uniformly random in[2/3W,W],hj uniformly random in[1,W/2];Type 2: wj uniformly random in[1,W/2],hj uniformly random in[2/3W,W];Type 3: wj uniformly random in[W/2,W],hj uniformly random in[W/2,W];Type 4: wj uniformly random in[1,W/2],hj uniformly random in[1,W/2].The strip widths are equal to 100 for all these classes, while the items are as follows:Class VII: type 1with probability of70%,type2,3,4with probability of10%each;Class VIII: type 2with probability of70%,type1,3,4with probability of10%each;Class IX: type 3with probability of70%,type1,2,4with probability of10%each;Class X: type 4with probability of70%,type1,2,3with probability of10%each.In Table3, we present the results obtained by testing the two algorithms on random generated instances (TL denotes the time limit). For each 10 instances, we present the average values of(i)
LB: lower bound,(ii)
UB: upper bound,(iii)
SDich and Sbb: the best solution obtained by each algorithm. Each run instance was carried out for 3600 seconds (if no optimal solution was achieved, we take the best one),(iv)
#Opt: the number of found optimum, and(v)
T: the average time spent for solving the instance.The results shown in Table4 confirm the results obtained previously. The dichotomic algorithm outperforms the branch-and-bound method in the number of optimal solutions found and in the average time to compute a solution.Table 4
Results obtained by dichotomic and branch-and-bound algorithms on random instances.
ProblemBoundDichotomicB&BClassWnLBUBSDich#OptT(sec)Sbb#OptT (sec)I101035.503635.50100.0135.5010112.321545.9049.1046.9010221.6046.709999.672063.5066.7065101112.2565.7062151.812582.1084.8084101758.088531854.33Avg56.8659.1557.8810.00772.9958.2371279.53II301010.2011.3010.70100.0110.7010301.211516.4019.4017.1010137.7818.3051267.742019.6021.7020.8010612.8220.9032921.282526.9029.4028.2010955.1429.3032663.98Avg18.2820.4519.2010.00426.4419.805.251788.55III401031.9034.9033.80100.0734.4010516.5415147153.60147.5010171.80149.3051592.4220169176.20172.8010810.37175.4043004.1425220.20232.60227.2081008.5323221518.21Avg142.03149.33145.339.50497.69147.785.251657.83IV100103741.7040.80101.0140.8010960.261549.4059.9054.5010465.6055.504968.762060.8067.6063.6010854.6368.2041975.872584.6098.8090.606937.7397.2042980.43Avg57.9567.0062.389.00564.7465.433600 5.502381.27V10010320.92330321.40101.98321.4010111.0415403.50434.40419.5010319.54421.505812.2220569.90593.00581.1081213.285835722.1925624.17694.6766513489.31689.1703600Avg478.37513.02496.757.251256.03503.7751311.36VI30010108.10122.70118.30100.17118.3010429.4515121.20144.10128.6010231.44136.7022512.2120168.03195.80179.2092012.20193.501360025220261.6024813512.89250.1012851.1Avg154.33181.05168.537.501439.17174.653.502348.19VII10010337.30338.70338.40103.56338.4010515532532.20532.10102.20542.30103.620731.30738.10738.1010466.15738.1010332.825707.70715.20714.6061735.13710.8071342.76Avg577.08581.05580.809.00551.76582.409.25421.04VIII10010247.10285.50267.60102.94263.9010752.915396.32435.10421.80101153.48433.1062821.220507.50571.7555973086.11561.502360025635.17771693.6763475.83701.7011880.4Avg446.52485.52485.528.251929.59490.054.752263.63IX10010543.70544.50543.70100.54543.701030.715871.20871.20871.20100.10871.201059.8201155.501159.801155.50100.011159.709432.3251476.9014791477100.2614798754.1Avg1011.831013.651011.8510.000.231013.409.25319.23X10010163.40174.90170.60100.12170.510343.215253.01268.90258.5010243.07265.1042500.320345.60378.40365.10101637.0537542871.225388.22416408.8952581.66419.6713600Avg287.56309.55300.778.751115.47307.574.752328.68


## 6.1. Computational Results for Heuristics

We test our heuristicsBSHF and NSHF to literature heuristics. Hifi [12] proposed four heuristics: FIA, SIA, HC/FIA, and HC/SIA. We compare the best values of those algorithms to our heuristics on the large instances studied by Hifi [12].In Table1, we present the results. The following information is given:Table 1
Comparison ofBSHF and NSHF heuristics and literature heuristics.
NamenWLBBestHBestHLBBFDHBFDHLBXSHFXSHFLBSCPL111042549571.16621.26541.10SCPL21201271271651.291701.331541.21SCPL3842251561811.161821.161781.14SCPL410235659671.13771.30671.13SCPL51021651291471.141481.141401.08SCPL65665719241.26281.47221.15SCPL71393571211261.041971.621351.11SCPL815647564771.20781.21711.10SCPL9117175901021.13991.10991.10Average90.44105.111.17115.661.29102.221.12(i)
n and W: respectively, the number of items and the strip width,(ii)
LB: the value of the linear lower bound,(iii)
BestH: the best value obtained by Hifi's heuristics (FIA, SIA, HC/FIA, HC/SIA),(iv)
XSHF: the best value obtained by our heuristics NSHF and BSHF(v)
BFDH: results of BFDH heuristic, and(vi)
A/LB: the ratio of each heuristic by the lower bound (A represents the value of solution obtained by the heuristic). As we can see in Table 1, our algorithms allow to obtain satisfactory solutions on the tested instances. It improves generally the existing solutions. Note that Hifi's algorithm remains the best for instance (SCPL7). This confirms the interest of our heuristics.


## 6.2. Computational Results on Hifi’s Instances

The first tests are carried out on the instances of Hifi [12]. The dichotomic algorithm is compared to the branch and bound of Bekrar et al. [14] and to the best-first search MVB algorithm of Hifi [12]. The 25 instances are of various sizes and are available at http://www.laria.u-picardie.fr/hifi/OR-Benchmark/Strip-cutting/Strip-cutting.html.In Table2, we give for each problem instance the following:Table 2
Results of exact algorithms on Hifi’s instances.
NamenWLminLBUBOPTTDichThTbSCP110513131313<0.01<0.1<0.01SCP211440404040<0.011.2<0.01SCP315614141914403.8319.447.07SCP41161920222041.224.18.75SCP582020202020<0.010.1<0.01SCP673032383838<0.013.4<0.01SCP7815121315140.031.40.23SCP812151717201710.452.39.57SCP91227686869680.010.10.14SCP10850807980800.010.50.12SCP111027474749480.120.714.89SCP121881343438340.012.7—SCP13770425056500.116.82.38SCP141010063638369126.6548.727.57SCP15144534343534445.94165.7—SCP1614632333533201.83181.4—SCP1794234393939<0.01323.6<0.01SCP181070909110410114.74327.836.43SCP1912525262626<0.01473.0<0.01SCP201015192022210.69673.942.73SCP21113013513514514512.342001.8654.31SCP222290343443341597.91757.8—SCP2312152833353510.031031.9401.97SCP2410501051051231145.265585.7329.34SCP25152536364136116.112662.9—(i)
the widthW of the strip and the number of items n,(ii)
values of upper boundUB and lower bound LB computed by the methods described previously,(iii)
values of lower boundLmin computed by Hifi [12],(iv)
values of the optimal solutionOPT, and(v)
the computational time of Hifi [12] Th, that of our branch and bound Tb, and that of the dichotomic algorithm TDich (in seconds).Note that we carry out our algorithms for one hour, and if the optimal solution was not found (marked by “—”), we take the best solution found. Table2 shows that the dichotomic algorithm could optimally solve all the tested instances of Hifi [12] and outperform our previous branch-and-bound algorithm in computational time, and on only few instances from 25 the dichotomic algorithm was not better. Note that Hifi used a Sparc-Server20 (module 712 MP) to test his algorithm. For this reason, it is not possible to make a reliable comparison in terms of the computation time. However, we prefer to report these results for information completeness.


## 6.3. Computational Results on Martello’s Instances

The second tests were carried out on a series of instances from literature. All instances are available athttp://www.or.deis.unibo.it/research.html.We compare the dichotomic algorithm to the branch and bound of Bekrar et al. [14]. For each problem, Table 3 gives the following information:Table 3
Results of exact algorithms on literature instances.
NamenWLmmv2LBUBSDichSB&BTDichTB&Bht1162020202020200.01<0.01ht21720202023202067.45TLht316202020252020197.53353.10ht425401515171515874.05TLht525401515161515571.65TLht6254015151515150.00<0.01ht7286030303331332045.34TLht8296030313632342101.33TLht9286030303030300.00<0.00cgcut116102323252323323.54TLcgcut2237063648267722012.24TLcgcut36270636637714647676TLTLgcut110250101610161016101610160.00<0.00gcut22025011331133134912841349TLTLgcut33025018031803181018101810TLTLgcut45025029342934321429563214TLTLngcut11010232123232316.732.58ngcut2171030303130301112.61TLngcut321102828332929724.31TLngcut471020172020200.100.01ngcut514103636373636120.120.01ngcut6151031303631311091.33TLngcut782020202020200.00<0.00ngcut813203332383333188.64TLngcut9182049495951531531.20TLngcut1013308058808080970.02TLngcut111530525060525255.84TLngcut122230878796878721.04TLbeng120253030353030608.41TLbeng240255758605960TLTLbeng360258485898889TLTLbeng48025107108112111112TLTLbeng510025134134138138138TLTLbeng6404036373938393152.27TLbeng780406767727072TLTLbeng812040101101108108108TLTLbeng916040126126130130130TLTLbeng1020040156156158158158TLTL(i)
problem name and values ofn and W,(ii)
values of the our lower boundLB and values of the upper bound UB,(iii)
values of lower boundLmmv2 computed by Martello et al. [4],(iv)
values of the solutions: branch and bound (SB&B) and dichotomic algorithm (SDich), and(v)
the computation time of the branch and boundTB&B and that of the dichotomic algorithm TDich (in seconds).As we can see in Table3, the dichotomic algorithm often outperforms the Branch and Bound both in the number of solved instances and in the computation time.


## 6.4. Computational Results on Randomly Instances

To further analyze the performance of the algorithms, we compare the branch-and-bound method and the dichotomic algorithm on instances randomly generated. We adapt the classes of instances proposed by Berkey and Wang [2] and Martello and Vigo [24] for the two-dimensional bin packing problem to the strip packing problem. These instances consist of ten classes of problems. For each class, there are 40 instances: 10 with 10 rectangles, 10 with 15 rectangles, 10 with 20 rectangles, and 10 with 25 rectangles. The first six classes have been proposed by Berkey and Wang [2]:j=1,…,n. n=10,15,20,25,Class I: wjandhjuniformly random in[1,10],W=10;Class II: wjandhjuniformly random in[1,10],W=30;Class III: wjandhjuniformly random in[1,35],W=40;Class IV: wjandhjuniformly random in[1,35],W=100;Class V: wjandhjuniformly random in[1,100],W=100;Class VI: wjandhjuniformly random in[1,100],W=300.The remainder four classes were inspired from Martello and Vigo [24]. The items are classified into four types:Type 1: wj uniformly random in[2/3W,W],hj uniformly random in[1,W/2];Type 2: wj uniformly random in[1,W/2],hj uniformly random in[2/3W,W];Type 3: wj uniformly random in[W/2,W],hj uniformly random in[W/2,W];Type 4: wj uniformly random in[1,W/2],hj uniformly random in[1,W/2].The strip widths are equal to 100 for all these classes, while the items are as follows:Class VII: type 1with probability of70%,type2,3,4with probability of10%each;Class VIII: type 2with probability of70%,type1,3,4with probability of10%each;Class IX: type 3with probability of70%,type1,2,4with probability of10%each;Class X: type 4with probability of70%,type1,2,3with probability of10%each.In Table3, we present the results obtained by testing the two algorithms on random generated instances (TL denotes the time limit). For each 10 instances, we present the average values of(i)
LB: lower bound,(ii)
UB: upper bound,(iii)
SDich and Sbb: the best solution obtained by each algorithm. Each run instance was carried out for 3600 seconds (if no optimal solution was achieved, we take the best one),(iv)
#Opt: the number of found optimum, and(v)
T: the average time spent for solving the instance.The results shown in Table4 confirm the results obtained previously. The dichotomic algorithm outperforms the branch-and-bound method in the number of optimal solutions found and in the average time to compute a solution.Table 4
Results obtained by dichotomic and branch-and-bound algorithms on random instances.
ProblemBoundDichotomicB&BClassWnLBUBSDich#OptT(sec)Sbb#OptT (sec)I101035.503635.50100.0135.5010112.321545.9049.1046.9010221.6046.709999.672063.5066.7065101112.2565.7062151.812582.1084.8084101758.088531854.33Avg56.8659.1557.8810.00772.9958.2371279.53II301010.2011.3010.70100.0110.7010301.211516.4019.4017.1010137.7818.3051267.742019.6021.7020.8010612.8220.9032921.282526.9029.4028.2010955.1429.3032663.98Avg18.2820.4519.2010.00426.4419.805.251788.55III401031.9034.9033.80100.0734.4010516.5415147153.60147.5010171.80149.3051592.4220169176.20172.8010810.37175.4043004.1425220.20232.60227.2081008.5323221518.21Avg142.03149.33145.339.50497.69147.785.251657.83IV100103741.7040.80101.0140.8010960.261549.4059.9054.5010465.6055.504968.762060.8067.6063.6010854.6368.2041975.872584.6098.8090.606937.7397.2042980.43Avg57.9567.0062.389.00564.7465.433600 5.502381.27V10010320.92330321.40101.98321.4010111.0415403.50434.40419.5010319.54421.505812.2220569.90593.00581.1081213.285835722.1925624.17694.6766513489.31689.1703600Avg478.37513.02496.757.251256.03503.7751311.36VI30010108.10122.70118.30100.17118.3010429.4515121.20144.10128.6010231.44136.7022512.2120168.03195.80179.2092012.20193.501360025220261.6024813512.89250.1012851.1Avg154.33181.05168.537.501439.17174.653.502348.19VII10010337.30338.70338.40103.56338.4010515532532.20532.10102.20542.30103.620731.30738.10738.1010466.15738.1010332.825707.70715.20714.6061735.13710.8071342.76Avg577.08581.05580.809.00551.76582.409.25421.04VIII10010247.10285.50267.60102.94263.9010752.915396.32435.10421.80101153.48433.1062821.220507.50571.7555973086.11561.502360025635.17771693.6763475.83701.7011880.4Avg446.52485.52485.528.251929.59490.054.752263.63IX10010543.70544.50543.70100.54543.701030.715871.20871.20871.20100.10871.201059.8201155.501159.801155.50100.011159.709432.3251476.9014791477100.2614798754.1Avg1011.831013.651011.8510.000.231013.409.25319.23X10010163.40174.90170.60100.12170.510343.215253.01268.90258.5010243.07265.1042500.320345.60378.40365.10101637.0537542871.225388.22416408.8952581.66419.6713600Avg287.56309.55300.778.751115.47307.574.752328.68


## 7. Concluding Remarks

In this paper we considered the strip packing problem under the guillotine constraint. The main contribution consists in the elaboration of new tight lower and upper bounds. The upper bounds are based on new rules for solving the problem under the above constraint. The lower bounds are based on a linear formulation using a set of various valid inequalities with a connection to scheduling on parallel machines. Such bounds were very useful to build an efficient dichotomic method which we compared to an existing branch-and-bound method. Based on the experimental results, several concluding remarks are worthy to note.On the instances of Hifi our dichotomic algorithm was able to solve all the instances generally in a shorter computation time compared to our previous branch-and-bound method. Indeed, for the same instances our previous branch-and-bound algorithm cannot solve 5 instances of them. The dichotomic algorithm was faster in 16 instances among the 25, where the branch-and-bound algorithm was more efficient only on a few instances (four instances). These results show the effectiveness of the introduction of the new valid inequalities and the new heuristics for computing the bounds. Moreover, our heuristics allow to improve the existing approximate solutions for several instances of the studied benchmark.For the instances introduced by Martello et al. [4] the same observation remains valid. Here, one can note that the average gap between the solution obtained by the dichotomic algorithm and the lower bound is estimated to 1.5%, which represents a good performance on the various and difficult instances.Finally, the performance of the dichotomic algorithm is confirmed on the random instances. Such an algorithm is more effective and rapid for solving some instances to optimality. In average, this algorithm yielded an optimal solution for 9 instances on 10, where the branch-and-bound algorithm solves only 6 instances on 10.As for the bin packing problem, the instances of classes V, VI, and VIII were the most difficult to solve. For example, for Class VI, with 25 items the two algorithms were not able to solve more than only one instance on the 10 generated. The other classes are easier since our dichotomic algorithm yielded generally the optimal solution (classes I, II, III, IX) within a short computation time (less than 10 minutes in average). The branch-and-bound algorithm needs more time, and it is less effective to solve optimally the problem (6.6 on 10). The easiness of these instances can be explained by the fact that they are constituted of many small items, which enables the algorithms to compute tight bounds. The classes IX and X are composed of 70% of items having widths greater than the half of the bin width. The bounds computed for this type of instances are very tight. Indeed, the introduction of the inequalities concerning the high and large items (inequalities in Section 3.7) allowed us to obtain a good performance.As future research, we aim to extend our approach to other variants of packing problems.Algorithm 1:Dichotomic Algorithm (Bekrar et al. [14]).
input:n: number of items;listP: list of items with their dimensions;W: the width of the strip;TL: the limit of the algorithm running time;output:H, the optimal height to pack all items1//Functions;2UBF(n, listP, W) : the function computing the upper bounds;3LBF(n, listP, W) : the function computing the lower bounds;4OPP(n, S, W1, H1) : this procedure returns TRUE if the set of items S can be packed ina bin of width W1 and height H1;5//initialization;6LB:=LBF(n,listP,W);7UB:=UBF(n,listP,W);8if(LB==UB)then9Return LB; STOP;10else11if OPP (n,listP,W,LB)==TRUEthen12Return LB; STOP;13else14while((LB<UB)and(Time<TL))do15if(UB-LB==1)then16Return UB; STOP;17else18S:=⌊(UB+LB)/2⌋;19if OPP (n,listP,W,S)==TRUEthen20UB:=S;21else22LB:=S;



---

*Source: 732010-2009-07-21.xml*