Abstract
In this paper, we consider the (additive integrality) gap of the cutting stock problem (CSP) and the skiving stock problem (SSP). Formally, the gap is defined as the difference between the optimal values of the ILP and its LP relaxation. For both, the CSP and the SSP, this gap is known to be bounded by 2 if, for a given instance, the bin size is an integer multiple of any item size, hereinafter referred to as the divisible case. In recent years, some improvements of this upper bound have been proposed. More precisely, the constants 3/2 and 7/5 have been obtained for the SSP and the CSP, respectively, the latter of which has never been published in English language. In this article, we introduce two reduction strategies to significantly restrict the number of representative instances which have to be dealt with. Based on these observations, we derive the new and improved upper bound 4/3 for both problems under consideration.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 General introduction
Let a capacity (bin size) \( L \in \mathbb {N} \) and \( m \in \mathbb {N} \) items, characterized by their sizes \( l_i \in \mathbb {N} \) and quantities \( b_i \in \mathbb {N} \), \( i \in I:=\lbrace 1,\ldots ,m \rbrace \), be given. More compactly, we will refer to these input data by a tuple \( E=(m,l,L,b) \) with \( l:=(l_1,\ldots ,l_m)^\top \in \mathbb {N}^m \) and \( b:=(b_1,\ldots ,b_m)^\top \in \mathbb {N}^m \), termed as an instance. In this paper, we consider the following two combinatorial optimization problems:
-
Cutting stock problem (CSP): Find the minimum number of bins (of capacity L) that is able to accommodate all items without exceeding the capacity of any bin.
-
Skiving stock problem (SSP): Find the maximum number of bins (of capacity L) that can be filled using the given items, so that the total load of any bin at least reaches the capacity.
Note that, usually, the CSP and the SSP are introduced from the perspective of cutting large items into smaller ones or combining small objects to obtain larger ones. However, to overcome the difficulty that the input parameters of an instance would partly have different meanings for the CSP and the SSP, we decided to choose the bin packing terminology throughout this article, so that both problems can suitably be addressed by the same vocabulary.
Obviously, the above optimization tasks are united by an economic component (i.e., lower costs in a broad sense) and the idea of sustainability (i.e., restricting the waste of resources). Nevertheless, from a historical point of view, there is a quite remarkable difference. While the CSP already started to attract scientific interest several decades ago, see (Gilmore and Gomory 1961; Kantorovich 1939) for early publications, the SSP is a rather young field of research which was introduced as a natural counterpart of the CSP in a specific application (Johnson et al. 1997; Zak 2003). In recent years, according to the constantly growing importance of the CSP, see particularly (Delorme et al. 2015, Figure 1), also a larger body of work has been established with respect to the SSP. For a more detailed introduction to both optimization problems and possible areas of application, here we recommend the survey articles (Delorme et al. 2016; Valério de Carvalho 2002) for the CSP, the papers (Martinovic et al. 2020; Martinovic and Scheithauer 2016a) for the SSP, as well as the book Scheithauer (2018) for a general overview on cutting and packing. Observe that although the CSP and the SSP form an obviously related pair of minimization and maximization problems, they are not dual formulations in the sense of mathematical optimization. Consequently, both problems have to be considered as theoretically independent. However, it is worth noting that the CSP and the SSP also appear side-by-side in holistic cutting-and-skiving scenarios within different fields of industry (Chen et al. 2019; Johnson et al. 1997).
Over time, many different integer linear programming (ILP) formulations have been presented for the two problems. Starting with assignment models Kantorovich (1939) or pattern-based approaches (Gilmore and Gomory 1961; Zak 2003), nowadays more and more research deals with pseudo-polynomial alternative frameworks like onecut models (Dyckhoff 1981; Martinovic and Scheithauer 2016a) or flow-based formulations (Delorme and Iori 2020; Martinovic et al. 2020; Valério de Carvalho 2002), the latter of which actually showed the most competitive performances so far. Besides structural parameters (like the numbers of variables and constraints or the sparsity of the system matrices), the strength of the corresponding LP relaxation is one of the most important indicators for an efficient solution procedure. More precisely, research has shown, and it became widely accepted, that the quality of the bound provided by the LP relaxation of an ILP model is a crucial factor in the size of the branch-and-bound search trees. In the next section, this aspect shall be introduced more thoroughly.
2 The additive integrality gap: preliminaries and literature review
Let \( E=(m,l,L,b) \) denote an instance (of the CSP or the SSP). To appropriately quantify the tightness of the LP bound, the additive integrality gap (or briefly gap), i.e., the difference between the optimal values of the LP relaxation and the original ILP formulation, is considered in this paper. In what follows, we will introduce this concept with respect to the pattern-based formulations presented by Gilmore and Gomory (1961) and Zak (2003). Due to well known equivalence results, see (Martinovic et al. 2018, Theorem 10) or Delorme and Iori (2020) for the CSP and (Martinovic and Scheithauer 2016a, Section 3) for the SSP, the gap is independent of the fact whether the pattern-based model or alternative formulations like flow-based or onecut approaches are considered.
Definition 1
Let \( E=(m,l,L,b) \) denote an instance (of the CSP or the SSP). Then, any vector \( a \in \mathbb {Z}^m_+ \) with
-
\( l^\top a \le L \) is called a cutting pattern,
-
\( l^\top a \ge L \) is called a packing pattern,
-
\( l^\top a = L \) is called an exact pattern.
We will refer to the respective sets by \( P_{\le }:=P_{\le }(E) \), \( P_{\ge }:=P_{\ge }(E) \), and \( P_{=}:=P_{=}(E) \). Moreover, in order to address a specific pattern, we will use the notation \( a^j=(a_1^j,\ldots ,a_m^j)^\top \in \mathbb {Z}^m_{+} \), where j can belong to one of the index sets \( J_{\le }:=J_{\le }(E) \), \( J_{\ge }:=J_{\ge }(E) \), or \( J_{=}:=J_{=}(E) \).
Based on these definitions, we can formulate the
and the
where \( x_j \) counts how many bins are filled according to the (cutting or packing) pattern \( a^j \), while the respective sets of constraints manage that at least (or at most) \( b_i \) items of type \( i \in I \) are used. In both cases, the LP relaxation can be obtained by replacing the condition \( x_j \in \mathbb {Z}_{+} \) with \( x_j \ge 0 \).
Definition 2
Let \( E=(m,l,L,b) \) denote an instance (of the CSP or the SSP). Then, the differences
are called the (additive integrality) gap of E, depending on whether the CSP or SSP is referred to. Here, the index “LP” stands for the continuous relaxation, whereas the superscript “\( \star \)” indicates the optimal value of the respective formulation.
Besides only considering one single instance, frequently the gap of a whole class \( \mathcal {T} \) of instances is of interest, too. In these situations, the gap of \( \mathcal {T} \) shall be understood in the following way:
Remark 1
It is worth mentioning that there is no “dominance” between both gaps. By way of example, consider the instances
-
\( E = (3,(21,14,6), 42,(1,2,6)) \) with \(\varDelta ^{CSP}(E) = 41/42< 1 \) and \( \varDelta ^{SSP}(E) = 43/42 > 1 \), or
-
\( E=(9,(62,40,37,32,29,16,9,6,4),81,(1,1,1,1,1,1,1,2,1)) \) with \( \varDelta ^{CSP}(E)=1 \) and \( \varDelta ^{SSP}(E)=20/21<1 \), see (Kartak et al. 2015, Table 2).
For the purpose of a clearer presentation, let us briefly mention the patterns used in the optimal solutions corresponding to the first instance from the above list. For both, the CSP and the SSP, the optimal LP value results to 85/42, and it is obtained by taking the exact patterns
As for the integer optimization problems, in the CSP scenario three bins are required to pack all the items (e.g., by using \( (1,1,1)^\top \), \( (0,1,4)^\top \), and \( (0,0,1)^\top \) precisely once), while in the SSP case it is not possible to pack more than one bin. Hence, there is no obvious relationship between these two concepts, even though the corresponding optimization problems possess a similar structure.
As regards the CSP, a significant body of work on the additive integrality gap has been employed in recent decades. At the beginning of these investigations, it was conjectured that the gap of the CSP can be bounded from above by the constant 1. A first counterexample to this claim was presented by Marcotte (1986), but it required very large (thus practically irrelevant) input data. Some years later, Fieldhouse (1990) and Nica (1994a) constructed further counterexamples of moderate sizes, so that finally \( \varDelta ^{CSP}(E)<2 \), the so called modified integer round-up property (MIRUP), was conjectured for all instances E, see Scheithauer and Terno (1995). With respect to the SSP, a similar claim (the modified integer round-down property (MIRDP) \( \varDelta ^{SSP}(E)<2 \)) was introduced by Zak (2003). Even nowadays, it is still an open question whether these inequalities hold or not. Moreover, there are only very few discrete optimization problems, whose additive integrality gap is known to be bounded by a small constant (being independent of the instance); see Nemhauser and Park (1991) for an example in edge coloring. Due to these reasons, particularly in the last years, research on the gap (of both, the CSP and the SSP) was further intensified, mainly with respect to
-
The construction of instances having large gaps (Caprara et al. 2015; Kartak and Ripatti 2019; Rietz and Dempe 2008; Rietz and Scheithauer 2002),
-
Upper bounds for the maximum gap (Martinovic and Scheithauer 2016b; Rietz 2003b; Rietz et al. 2002),
-
The investigation of special cases (Martinovic and Scheithauer 2017, 2018a).
One of the most important special cases for which the MIRUP and the MIRDP could successfully be proved is given by the divisible caseFootnote 1.
Definition 3
Let \( E=(m,l,L,b) \) denote an instance (of the CSP or the SSP). Then, E belongs to the divisible case (\( E \in \mathcal {DC} \) for short) if \( L/l_i \in \mathbb {N} \) holds for all \( i \in I \).
Note that (in a slight abuse of our initial assumption \( l \in \mathbb {N}^m \)) for the sake of simplicity, we will always represent an instance \( E \in \mathcal {DC} \) by its normalized form with \( L=1 \) and \( l_i=1/q_i \in \lbrace 1/q \, : \, q \in \mathbb {N} \rbrace \) for all \( i \in I \). Besides this convenient structure, one main advantage of the divisible case is given by the following result about the optimal LP value:
Lemma 1
Let \( E=(m,l,1,b) \in \mathcal {DC} \). Then, we have
Proof
Let \( l_1=1/q_1 \) for some \( q_1 \in \mathbb {N} \). Then, the exact pattern \( a^1:=(q_1,0,\ldots ,0)^\top \in P_{=}(E) \) can be used \( x_1=b_1/q_1 \) times in the LP relaxation. In the same manner, we can proceed with the further items and obtain the objective value \( \sum _{i \in I} b_i/q_i = l^\top b \). This value is optimal, for the CSP as well as for the SSP, since we did not waste any material. \(\square \)
Hence, only one optimization problem needs to be solved when investigating the gap of the divisible case.
From a theoretical point of view, the following key results have already been obtained in the literature:
-
We have \( \varDelta ^{CSP}(E)<2 \), see e.g. (Marcotte 1983, Theorem 2.16), and \( \varDelta ^{SSP}(E)<2 \), see e.g. (Martinovic and Scheithauer 2016b, Theorem 9), for all \( E \in \mathcal {DC} \).
-
Meanwhile, these upper bounds could be improved to \( \varDelta ^{CSP}(E)<1.4 \), see (Rietz 2003b, Satz 1), and \( \varDelta ^{SSP}(E)<3/2 \), see Martinovic and Scheithauer (2017). Observe that the first result has never been published in English language, and, unfortunately, its documentation in the German dissertation Rietz (2003b) was not established thoroughly enough to understand and reconstruct all the arguments. Hence, we will not make active use of this inequality here.
-
The largest known gaps for the divisible case are \( \varDelta ^{CSP}(E)=137/132 \) provided by \( E=(3,(44,33,12),132,(2,3,6)) \), see (Scheithauer 2018, Section 4.11.6), and \( \varDelta ^{SSP}(E) = 22/21 \) approximated by an infinite sequence of instances, see (Martinovic and Scheithauer 2016b, Corollary 16). Actually, it is even conjectured that 22/21 represents the best possible upper bound for the divisible case of the SSP, see (Martinovic and Scheithauer 2018b, Conjecture 1).
-
Upper bounds for the gap of the divisible case can directly be used to formulate upper bounds for the gap of arbitrary instances, see (Martinovic and Scheithauer 2019, Theorem 4) for an example. Hence, any improvement that is achieved for this special case can be transferred to more general instances, too.
Note that, besides being of theoretical importance, the divisible case sometimes also appears in practically relevant scenarios, especially when there is a high degree of standardization such as in bin-packing based (multiprocessor) scheduling applications (Bar-Noy et al. 2007; Coffman et al. 1987).
Given the aforementioned observations, the main contributions of the present article can be summarized as follows:
-
We introduce two new reduction strategies that allow to only focus on a considerably restricted set of (somewhat homogeneous) instances (\(\rightarrow \) Sect. 3).
-
We derive the improved upper bound \( \varDelta ^{CSP}(E)<4/3 \) for all \( E \in \mathcal {DC} \) (\(\rightarrow \) Sect. 4).
-
We transfer the previous result to the SSP, i.e., we show \( \varDelta ^{SSP}(E)<4/3 \) for all \( E \in \mathcal {DC} \) (\(\rightarrow \) Sect. 5).
On the one hand, we significantly improve the currently best upper bounds for the gap of the divisible case for both, the CSP and the SSP. Moreover, we highlight the fact that our underlying theoretical approach is very general, so that a much more extensive analysis of the applied arguments could potentially lead to further improvements of these upper bounds.
3 Reduction strategies
The following definition will be required to decompose the set of all instances of the divisible case.
Definition 4
Let \( \delta \in \mathbb {N} \) with \( \delta \ge 2 \) be given. For any \( n \in \mathbb {N} \), we define the sets
Remark 2
In fact, the integrality of the parameter \( \delta \) is not required for the definition here, and also most of the general arguments used during this article could be modified to become applicable to \( \delta \in \mathbb {R} \), too. However, since integer values are sufficient for our main contributions and slightly simplify the corresponding formulas and calculations, we will restrict ourselves to the integrality assumption, but not without pointing out at the corresponding places, which changes would be necessary in case of real numbers or which challenges (e.g., in the proofs) would result from that.
For fixed \( \delta \ge 2 \), the sets \( \mathcal {DC}^{-}(n,\delta ) \), \( n \in \mathbb {N}\), will be used for the CSP, whereas the sets \( \mathcal {DC}^{+}(n,\delta ) \), \( n \in \mathbb {N}\), will later be important for the SSP case. Observe that, due to Lemma 1, the optimal LP value of an instance \( E \in \mathcal {DC}^{-}(n,\delta ) \) is known to satisfy
while \( E \in \mathcal {DC}^{+}(n,\delta ) \) directly implies
In the following, we first concentrate on the CSP case. To this end, let \( \delta \ge 2 \) be fixed to some appropriate value (which is specified later).
Lemma 2
If for any \( n \in \mathbb {N} \) and any instance \( \widetilde{E} \in \mathcal {DC}^{-}(n,\delta ) \), the items of \( \widetilde{E} \) can be assigned to (at most) n bins (cutting patterns), then we have
for all \( E \in \mathcal {DC} \).
Proof
For any instance \( E=(m,l,1,b) \in \mathcal {DC} \) there is some \( n:=n(E) \in \mathbb {N} \) with \( l^\top b \in [n-1,n) \):
-
If \( E \in \mathcal {DC}^{-}(n,\delta ) \), then we have \( z^{CSP,\star }(E) \le n \) by hypothesis and, finally,
$$\begin{aligned} \varDelta ^{CSP}(E) = z^{CSP,\star }(E) - z^{CSP,\star }_{LP}(E) \le n - l^\top b \le 1 < 1+ \frac{1}{\delta }. \end{aligned}$$ -
If \( E \notin \mathcal {DC}^{-}(n,\delta ) \), then we first have
$$\begin{aligned} z^{CSP,\star }_{LP}(E)=l^\top b \in \left( n- \frac{1}{\delta }, n \right) . \end{aligned}$$On the other hand, given that MIRUP holds for the entire divisible case, we obtain \( z^{CSP,\star }(E) \in \lbrace n, n+1 \rbrace \). Both observations lead to
$$\begin{aligned} \varDelta ^{CSP}(E) = z^{CSP,\star }(E) - z^{CSP,\star }_{LP}(E) < (n+1) - \left( n- \frac{1}{\delta }\right) = 1 + \frac{1}{\delta }. \end{aligned}$$
\(\square \)
Remark 3
In an analogous manner, proving that the items of any instance \( \widetilde{E} \in \mathcal {DC}^{+}(n,\delta ) \), \( n \in \mathbb {N} \), can be used to build (at least) n bins (packing patterns) is sufficient to show
for all \( E \in \mathcal {DC} \). Indeed, let us consider an instance \( E \in \mathcal {DC} \) (of the SSP) with \( l^\top b \in (n,n+1] \) for some \( n \in \mathbb {N} \), then one of the two cases appears:
-
For \( E \in \mathcal {DC}^+(n,\delta ) \), we have \( z^{SSP,\star }(E) \ge n \) by hypothesis, leading to
$$\begin{aligned} \varDelta ^{SSP}(E) = z^{SSP,\star }_{LP}(E) - z^{SSP,\star }(E) \le l^\top b - n \le (n+1)-n =1< 1+ \frac{1}{\delta }. \end{aligned}$$ -
For \( E \notin \mathcal {DC}^+(n,\delta ) \), we have \( z^{SSP,\star }(E) \in \lbrace n-1,n \rbrace \) by MIRDP (which holds for the entire divisible case), leading to
$$\begin{aligned} \varDelta ^{SSP}(E) = z^{SSP,\star }_{LP}(E) - z^{SSP,\star }(E) \le l^\top b - (n-1) < \left( n+\frac{1}{\delta } \right) -(n-1) = 1+ \frac{1}{\delta }. \end{aligned}$$
We refer the reader to Sect. 5 for more details concerning the SSP case.
Obviously, for fixed \( \delta \), the sets \( \mathcal {DC}^{-}(n,\delta ) \), \( n \in \mathbb {N} \), contain an infinite number of instances to be checked with respect to Lemma 2. Moreover, these instances can be considered to be very heterogeneous since neither the sizes \( l_i \) nor the quantities \( b_i \), \( i \in I \), of an instance \( E \in \mathcal {DC}^{-}(n,\delta ) \) are restricted. To overcome these issues, we will introduce two reduction strategies leading to
-
(1)
an upper bound for the quantities \( b_i \), \( i \in I \),
-
(2)
a lower bound for the sizes \( l_i \), \( i \in I \),
so that coping with only finitely many cases (each of which offering some structural information) will be sufficient to prove the result for all possible instances of the divisible case.
Before explaining these steps in more details, the following definition is required:
Definition 5
An instance \( E=(m,l,1,b) \in \mathcal {DC} \) is called irreducible, if two or more items (not necessarily having different sizes) cannot be used to build a unit fraction. More formally, an irreducible instance is characterized by
for any vector \( a \in \mathbb {Z}_{+}^m \). Otherwise, E is called reducible.
Remark 4
In particular, any irreducible instance \( E \in \mathcal {DC} \) has the following properties:
-
E does not possess any exact pattern \( a \in P_{=}(E) \) with \( a \le b \) (in a componentwise sense), since this would contradict to the above definition for \( k=1 \).
-
Let t(q) denote the smallest prime divisor of \( q \in \mathbb {N} \) with \( q \ge 2 \). Then, any item of size 1/q can appear at most \( t(q)-1 \) times in E. (Otherwise, t(q) items of size 1/q would sum up to a unit fraction).
-
In addition to the previous observation, item combinations like \( 1/3+1/6=1/2 \) or \( 1/4+1/12=1/3 \) cannot appear in E.
In order to implement the first reduction mentioned above, we now proceed as follows:
Reduction 1
If \( z^{CSP,\star }(E) \le n \) can be shown for all irreducible instances \( E \in \mathcal {DC}^{-}(n,\delta ) \), then it also holds for any reducible instance in \( \mathcal {DC}^{-}(n,\delta ) \).
Proof
Consider a reducible instance \( E \in \mathcal {DC}^{-}(n,\delta ) \). Then, we can find a subset (containing at least two items) summing up to some value 1/k, \( k \in \mathbb {N} \). By replacing this subset of items with one artificial item of size 1/k, we obtain an instance \( E' \) with fewer items but the same optimal LP value. After a finite number of such steps, we end up with an irreducible instance whose items can be packed into at most n bins (cutting patterns) by hypothesis. In this feasible packing, any artificial item of size 1/k can be replaced by the corresponding subset of original items (of E) which was used to build the item of size 1/k. Consequently, also the items of E can be packed into at most n bins and we are done. \(\square \)
While this method can mainly be used to restrict the quantities \( b_i \), \( i \in I \), of an instance, the second reduction strategy is useful to only focus on the “large items” of E.
Definition 6
Let \( \delta \ge 2 \), \( n \in \mathbb {N} \), and an instance \( E \in \mathcal {DC} \) be given. Then, the set of large items (of E) is defined by
All other items will be termed as small.
Remark 5
When dealing with real-valued parameters \( \delta \), the definition has to be adjusted, so that an item \( i \in I \) is called large, whenever it satisfies
Then, we obtain the following observation.
Reduction 2
Let \( E \in \mathcal {DC}^{-}(n,\delta ) \) be irreducible. If it is possible to assign all large items of E to at most n bins (cutting patterns), then we have \( z^{CSP,\star }(E) \le n \), i.e., all items actually fit into those n bins.Footnote 2
Proof
Let us assume that, after having assigned the large items of E to at most n bins, it is not possible to put one of the remaining small items, say one item of size \( l^\star :=l_i \) for some \( i \in I \setminus \varLambda _E \), into the existing bins without exceeding the bin size. This can only happen, if for any bin \( B_j \), \( j \in \lbrace 1,\ldots ,n \rbrace \), the total load C(j) (of the items already allocated to \( B_j\)) is greater than \( 1-l^\star \). Consequently, we have
Rearranging the terms leads to
where the last equivalence is true since any item size is a unit fraction. However, this would imply that the item of size \( l^\star \) is a large item which already has been feasibly assigned to a bin by hypothesis. Hence, we obtain a contradiction and the statement is proved.\(\square \)
This second reduction strategy allows to only consider the large items of an instance \( E \in \mathcal {DC}^{-}(n,\delta ) \), where the term large is specified by Condition (1). Moreover, it implicitly states that, after having distributed these objects, the small items can be assigned in an arbitrary manner, as long as the capacities are respected. By way of example, one appropriate strategy to assign the small items is based on the best-fit decreasing heuristic, as described in (Martinovic and Scheithauer 2017, Algorithm 1). In that algorithm, the (remaining) items are sorted with respect to non-increasing sizes and processed separately. More precisely, in a given iteration, the currently largest object is taken and it is assigned to the least filled bin (where ties are broken by choosing the lowest-indexed bin).
4 The CSP case: improved upper bounds for the gap
As a first contribution, we consider the case \( \delta =2 \) which would lead to the upper bound \( \varDelta ^{CSP}(E) < 3/2 \) for \( E \in \mathcal {DC} \) according to Lemma 2. The reasons for presenting this auxiliary result are twofold:
-
Remember that the proof for the currently best upper bound \( \varDelta ^{CSP}(E)<1.4 \) has never been published in English language, and so it is hardly known in the scientific community. Hence, instead of using a result that cannot easily be verified, it is more convenient to briefly prove an upper bound of nearly the same quality.
-
Later, we can apply this preliminary observation to appropriately deal with some subcases appearing in our main theorem.
Theorem 1
Let \( n \in \mathbb {N} \) be given, and let us consider an irreducible instance \( E \in \mathcal {DC}^{-}(n,2) \). Then, these items can be assigned to at most n bins (cutting patterns). In particular, we have \( \varDelta ^{CSP}(E)<3/2 \) for all \( E \in \mathcal {DC} \).
Proof
It is sufficient to consider the large items of E, meaning that we focus on those items with
Since E is irreducible, for any fixed \( k=1,\ldots ,n-1 \) we have at most one item of size 1/(2k) and at most \( 2k-2 \) items of size \( 1/(2k-1) \). Due to
these items would fit into one bin. Hence, the large items of E can be assigned to at most n binsFootnote 3 which concludes the proof thanks to Reduction 2. \(\square \)
Note that also this proof is constructive since it contains a precise method to obtain a feasible solution using n bins. More precisely, the large items of E are grouped according to the instructions in the previous proof, whereas the small items can exemplarily be distributed by the best-fit decreasing heuristic from (Martinovic and Scheithauer 2017, Algorithm 1).
Now we intend to show an analogous result for \( \delta =3 \) which would lead to the improved upper bound \( \varDelta ^{CSP}(E)<4/3 \) for all \( E \in \mathcal {DC} \). To this end, let us consider an irreducible instance \( E=(m,l,1,b) \in \mathcal {DC}^{-}(n,3) \) for some \( n \in \mathbb {N} \). Note that for \( n=1 \) it is obvious that all items can be packed into one bin. Consequently, we can assume \( n \ge 2 \). Moreover, due to Reduction 2, it is sufficient to consider the large items of E, meaning that we only have to show that all items with
can be assigned to (at most) n bins (cutting patterns). To prove the latter, Theorem 1 can be applied. More formally, for \( \delta =3 \), let \( T_E(n):=T_E(n,\delta ) \) denote the total size of all large items appearing in E, i.e.,
and let us define
Then it sufficesFootnote 4 to verify that
holds for all \( n \ge 2 \). To prove this claim, observe that for \( N:=3n-4 \) we have
where \( U(N)=U(3n-4) \) sums up at most \( t(q)-1 \) items of size 1/q for any large item \( q=2,\ldots ,N=3n-4 \) (again with t(q) representing the smallest prime divisor of q), and \( R(N) \ge 0 \) is a correction term that possibly subtracts some item sizes that we obtain from forbidden item combinations, see Remark 4. Hence, our main strategy in the following proofs consists of showing
for an appropriately defined term \( R(3n-4)\ge 0 \), which directly implies Condition (2).
Theorem 2
Condition (2) is true for all \( n\in \lbrace 2,3,\ldots ,24 \rbrace \).
Proof
At first note that the values \( U(3n-4)\) given in (3) can be easily computed, see Table 1.
Based on these data and the choice \( R(N)=R(3n-4)=0 \), we can directly see that (3) is true for \( n \in \{2,3,4\} \cup \lbrace 10,11,\ldots ,24 \rbrace \). The remaining cases can be dealt with separately:
-
For \( n=5 \) we have \( 3n-4=11 \) and \( U(11) \approx 4.5968 > 5-1/2 \). However, since \( 1/6+1/3=1/2 \) holds, we can at least subtract \( R(11)=1/6 \) from U(11) , so that we end up with
$$\begin{aligned} T(5) \le U(11)-\frac{1}{6} \le 5- \frac{1}{2}. \end{aligned}$$ -
For \( n=6 \) we have \( 3n-4=14 \) and \( U(14) \approx 5.6746 > 6-1/2 \). However, since additionally \( 2/5+1/10=1/2 \) holds, we can at least subtract \( R(14)=1/6+1/10 \) from U(14) , so that we end up with
$$\begin{aligned} T(6) \le U(14)-\frac{1}{6}-\frac{1}{10} \le 6- \frac{1}{2}. \end{aligned}$$ -
For \( n=7 \) we have \( 3n-4=17 \) and \( U(17) \approx 6.8116 > 7-1/2 \). However, since additionally \( 1/4+1/12=1/3 \) holds, we obtain
$$\begin{aligned} T(7) \le U(17)-\frac{1}{6}-\frac{1}{10}- \frac{1}{12} \le 7- \frac{1}{2}. \end{aligned}$$ -
For \( n=8 \) we have \( 3n-4=20 \) and \( U(20) \approx 7.8646 > 8-1/2 \). However, since additionally \( 3/7+1/14=1/2 \) holds, we obtain
$$\begin{aligned} T(8) \le U(20)-\frac{1}{6}-\frac{1}{10}- \frac{1}{12} - \frac{1}{14} \le 8- \frac{1}{2}. \end{aligned}$$ -
For \( n=9 \) we have \( 3n-4=23 \) and \( U(23) \approx 8.9618 > 9-1/2 \). However, since additionally \( 1/9+1/18=1/6 \) holds, we obtain
$$\begin{aligned} T(9) \le U(23)-\frac{1}{6}-\frac{1}{10}- \frac{1}{12} - \frac{1}{14} - \frac{1}{18} \le 9- \frac{1}{2}. \end{aligned}$$
\(\square \)
Obviously, we cannot compute the true values T(n) for all \( n \in \mathbb {N} \), and neither the upper bound \( U(3n-4) \) can always be used since, depending on n, we would possibly have to find more and more forbidden item combinations (which can contribute to \( R(3n-4) \)). The next lemma helps us to establish an upper bound for T(n) based on some well known properties of prime numbers.
Lemma 3
For \( N \ge 8 \) (with \( N=3n-4 \) for some \( n \in \mathbb {N} \)) we have
Proof
Let \( N \ge 8 \) be fixed. At first we define the set
for every prime \( p \in \mathbb {P} \) with \( 2 \le p \le N \). Note that \( U_p(N) \) contains all integers from \( \lbrace 2,\ldots ,N \rbrace \) having p as the smallest prime divisor. The main calculation of this proof requires some inequalities which we are going to mention beforehand:
-
(A)
Let \( N:=3n-4 \ge 8 \) (meaning that we have \( n \ge 4 \)) and \( R(N)=1/6 \), then we obtain
$$\begin{aligned} T(n) \le U(N)- \frac{1}{6} = \sum _{q=2}^N \frac{t(q)-1}{q} - \frac{1}{6}, \end{aligned}$$since only one of the items 1/3 and 1/6 can be part of an irreducible instance.
-
(B)
Since every \( q \in U_p(N) \) has p as the smallest prime divisor, we can state
$$\begin{aligned} \sum _{q \in U_p(N)} \frac{1}{\frac{q}{p}} < \sum _{k=0}^{\infty } \frac{1}{p^k} = \frac{1}{1- \frac{1}{p}} = 1+ \frac{1}{p-1} \end{aligned}$$due to the well known convergence properties of the geometric series.
-
(C)
Due to \( N\ge 8 \), we have
$$\begin{aligned} \sum _{p \in \mathbb {P}, p \le N} \frac{1}{p-1} - \sum _{q=2}^N \frac{1}{q} \le 1- \frac{1}{3}- \frac{1}{5} - \frac{1}{7} - \frac{1}{8} < \frac{1}{5}. \end{aligned}$$(4)For \( N=8 \) this can be verified by a direct calculation. Beyond that, we can see the correctness of this inequality in an inductive way. More precisely, the difference on the left hand side definitely decreases until we reach the next prime number \( N=p \) because the first sum stays constant while the second sum gathers more and more unit fractions. Hence, for the induction, we only need to focus on those steps referring to prime numbers. Having arrived at \( N=p \in \mathbb {P} \), the first sum receives an additional term \( 1/(N-1) \). However, since (for \( N \ge 8 \)) we do not find two consecutive prime numbers, the second sum at least increased by \( 1/(N-1)+1/N \) compared to the previous prime number (where we noticed the last increase of the first sum), meaning that the overall difference stays below 1/5.
-
(D)
Let \( \pi (N) \) count the number of primes in \( \lbrace 2,\ldots ,N \rbrace \), then we can state
$$\begin{aligned} \pi (N) \le \frac{N}{\ln (N)}\cdot \left( 1+\frac{1}{\ln (N)}+\frac{2}{(\ln (N))^2}+ \frac{7.59}{(\ln (N))^3}\right) \end{aligned}$$by means of (Dusart 2018, Theorem 5.1). This inequality even holds for \( N \ge 2 \).
Based on these ingredients, we can proceed as follows
and the proof is complete. \(\square \)
Note that \( N \ge 8 \) is required in the proof to obtain the additional term \( -1/8 \) when subtracting the two sums in (4).
For the sake of simplicity, let us use
as an abbreviation. Then it can be verified that:
Theorem 3
Condition (2) is true for all \( n \ge 25 \).
Proof
Let \( n \ge 25 \) and \( N:=3n-4 \) be fixed, then we have \( T(n) < \widetilde{U}(N) \le n- \frac{1}{2} \), i.e., Condition (2) is true. For all the details, we refer the interested reader to the “Appendix”. \(\square \)
Putting Theorems 2 and 3 together, we can conclude that:
Theorem 4
We have \( \varDelta ^{CSP}(E)< 4/3 \) for all \( E \in \mathcal {DC} \).
Consequently, we have found a new and improved upper bound for the gap of divisible case instances of the CSP.
5 A transfer to the SSP case
Let us now consider an instance \( E=(m,l,1,b) \in \mathcal {DC} \) of the skiving stock problem. In analogy to the CSP case we can focus on irreducible instances.
Lemma 4
Let \( E \in \mathcal {DC}^{+}(n,3) \) be irreducible, then the items of E can be assigned to n bins (packing patterns).
Proof
Let us consider the large items of E, i.e., those items satisfying
In the proofs of the previous section, we have shown that (for given n and \( \delta =3 \)) all large items (of any irreducible instance \( \widetilde{E} \in \mathcal {DC} \)) can always be assigned to n cutting patterns. Hence, the same is true for the large items contained in the considered instance E, so that they possess a total size of at most n. Thus, some items of the SSP instance are still to be distributed. Note that all of them are small items, i.e., they have a size
Let us assign the remaining items based on the best-fit decreasing heuristic presented in (Martinovic and Scheithauer 2017, Algorithm 1), meaning that the current item is allocated to a bin \( B_j \), \( j \in \lbrace 1,\ldots , n \rbrace \), whose total item load C(j) is the smallest. Then, it is clear that a bin \( B_j \) with \( C(j) \ge 1 \) will receive an additional item only in those cases when all bins actually satisfy \( C(j) \ge 1 \).
For the sake of contradiction, let us assume that after having assigned the last item of E, there is some \( k \in \lbrace 1,\ldots ,n \rbrace \) with \( C(k)< 1 \), i.e., we did not end up with a feasible solution for the SSP. This would mean that no item was assigned to a bin which already represented a packing pattern, i.e., any filled bin satisfies
since only small items are distributed in this phase. This would lead to
giving the contradiction. Hence, we have constructed n bins (for the SSP) and the proof is complete. \(\square \)
Given this observation, a direct consequence is the following:
Theorem 5
We have \( \varDelta ^{SSP}(E)< \frac{4}{3} \) for any \( E \in \mathcal {DC} \).
Hence, we have also improved the best upper bound for the SSP case to 4/3. Note that a much more detailed analysis of the arguments applied in the CSP case could also directly influence the quality of the upper bound of the SSP.
Remark 6
In fact, the strategy from the previous proof is much more general. In the CSP case, we have not only proved that the large items of a given instance \( E \in \mathcal {DC}^{-}(n,\delta ) \) would fit into at most n cutting patterns; the proofs of Theorems 2 and 3 actually show that all large items of any(!) irreducible instance \( E \in \mathcal {DC} \) can be assigned to at most n binsFootnote 5. In the proof of the previous lemma, we used this observation to easily transfer the upper bound from the CSP to the SSP. Effectively, this means that we can apply the same proof also for some larger values of \( \delta \), as long as we can verify that all large items \( i \in \varLambda _E(n,\delta ) \) of any irreducible instance \( E \in \mathcal {DC} \) can feasibly be assigned to (at most) n bins without exceeding their capacities.
Finally, it is important to note again that improved upper bounds for the divisible case directly influence the upper bounds for more general instances. By way of example, given the results of this section, the constant term in (Martinovic and Scheithauer 2019, Theorem 4) can now be reduced from 3/2 to 4/3 for any arbitrary instance E of the SSP.
6 Conclusions
In this article, we investigated the additive integrality gap of both, the CSP and the SSP, from a theoretical point of view. In particular, we focussed on the well known divisible case, where the bin size is assumed to be an integer multiple of any item size \( l_i \), \( i\in I \). For such instances we first developed two reduction strategies to considerably limit the number of instances that has to be considered. More precisely, one of these reductions aims at restricting the quantities \( b_i \), while the second one implements a lower bound on the item sizes \( l_i \), \( i \in I \). Based on these two observations, we were able to state the improved upper bound 4/3 for the CSP and the SSP. Moreover, our approach potentially offers the possibility of further improvements if a much more extensive analysis is conducted. Another aspect of future research deals with narrowing the interval between the currently best upper bounds and the largest known gaps provided by concrete instances, as mentioned at the end of Sect. 2.
Notes
An exemplary instance is given in the first part of the previous remark.
Actually, \( z^{CSP,\star }(E) \le n \) for an instance \( E \in \mathcal {DC}^{-}(n,\delta ) \) already shows the optimality of the value n. However, as the feasibility of the assignment is sufficient for our purposes, we do not specifically stress this fact.
Actually, we have shown a bit more, namely that already \( n-1 \) bins are sufficient.
Indeed, then the large items of E either form an instance of \( \mathcal {DC}(n,2) \) (if \( T_E(n) \ge n-1 \) holds), so that they can be assigned to at most n bins by the previous theorem. Or we have \( T_E(n)<n-1 \) also meaning that at most n bins are sufficient to accommodate all large items as a direct consequence of MIRUP for the divisible case.
References
Bar-Noy A, Ladner RE, Tami T (2007) Windows scheduling as a restricted version of bin packing. ACM Trans Algorithms 3(3), Article 28
Caprara A, Dell’Amico M, Diaz-Diaz JC, Iori M, Rizzi R (2015) Friendly bin packing instances without integer round-up property. Math Program 150:5–17
Chen Y, Song X, Ouelhadj D, Cui Y (2019) A heuristic for the skiving and cutting stock problem in paper and plastic film industries. Int Trans Op Res 26(1):157–179
Coffman EG, Garey MR, Johnson DS (1987) Bin packing with divisible item sizes. J Complex 3(4):406–428
Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J Comput 32(1):101–119
Delorme M, Iori M, Martello S (2015) Bin packing and cutting stock problems: mathematical models and exact algorithms. Research report OR-15-1, University of Bologna
Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur J Op Res 255:1–20
Dusart P (2018) Explicit estimates of some functions over primes. Ramanujan J 45:227–251
Dyckhoff H (1981) A new linear approach to the cutting stock problem. Op Res 29(6):1092–1104
Fieldhouse M (1990) The duality gap in trim problems. SICUP Bull 5:4–5
Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem (part I). Op Res 9:849–859
Johnson MP, Rennick C, Zak EJ (1997) Skiving addition to the cutting stock problem in the paper industry. SIAM Rev 39(3):472–483
Kantorovich LV (1939) Mathematical methods of organizing and planning production. Manag Sci 6:366–422 (1939 Russian, 1960 English)
Kartak V, Ripatti A (2019) Large proper gaps in bin packing and dual bin packing problems. J Glob Optim 74:467–476
Kartak V, Ripatti A, Scheithauer G, Kurz S (2015) Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl Math 187:120–129
Marcotte O (1983) Topics in combinatorial packing and covering. Technical report No. 568, Cornell University
Marcotte O (1986) An instance of the cutting stock problem for which the rounding property does not hold. Op Res Lett 4(5):239–243
Martinovic J, Delorme M, Iori M, Scheithauer G, Strasdat N (2020) Improved flow-based formulations for the skiving stock problem. Comput Op Res 113, Article 104770
Martinovic J, Scheithauer G (2016) Integer linear programming models for the skiving stock problem. Eur J Op Res 251(2):356–368
Martinovic J, Scheithauer G (2016) Integer rounding and modified integer rounding for the skiving stock problem. Discrete Optim 21:118–130
Martinovic J, Scheithauer G (2017) An upper bound of \( \Delta (E)<3/2 \) for skiving stock instances of the divisible case. Discrete Appl Math 229:161–167
Martinovic J, Scheithauer G (2018) Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory. Optimization 67(10):1797–1817
Martinovic J, Scheithauer G (2018) Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case. Ann Op Res 271(2):811–829
Martinovic J, Scheithauer G (2019) New theoretical investigations on the gap of the skiving stock problem. Pesquisa Operacional 39(1):1–35
Martinovic J, Scheithauer G, Valério de Carvalho JM (2018) A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems. Eur J Op Res 266(2):458–471
Nemhauser GL, Park S (1991) A polyhedral approach to edge coloring. Op Res Lett 10:315–322
Nica V (1994) A general counterexample to the integer round-up property. Working paper, Department of Economic Cybernetics, Academy of Economic Studies, Bucharest
Rietz J (2003) Untersuchungen zu MIRUP für Vektorpackprobleme. PhD thesis, TU Bergakademie Freiberg
Rietz J, Dempe S (2008) Large gaps in one-dimensional cutting stock problems. Discrete Appl Math 156(10):1929–1935
Rietz J, Scheithauer G (2002) Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl Math 121:229–245
Rietz J, Scheithauer G, Terno J (2002) Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. Optimization 51(6):927–963
Scheithauer G (2018) Introduction to cutting and packing optimization-problems, modeling approaches, solution methods. International series in operations research and management science 263, vol 1. Springer, Berlin
Scheithauer G, Terno J (1995) The modified integer round-up property of the one-dimensional cutting stock problem. Eur J Op Res 84:562–571
Valério de Carvalho JM (2002) LP models for bin packing and cutting stock problems. Eur J Op Res 141(2):253–273
Zak EJ (2003) The skiving stock problem as a counterpart of the cutting stock problem. Int Trans Op Res 10:637–650
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The author declares that he has no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A Proof of Theorem 3
A Proof of Theorem 3
Let \( n \ge 25 \) and \( N:=3n-4 \). Remember that we have to show \( \widetilde{U}(N){\le }n-\frac{1}{2} \) or equivalently
-
First of all, note that for \( n=25 \) (i.e., \( N=71 \)) we have \( \widetilde{U}(71) \approx {24.0625} \), so that (5) holds by a direct calculation.
-
Now let us interpret both sides of (5) as a function of \( n \in \mathbb {R} \), i.e., we set
$$\begin{aligned} f_1(3n-4):= & {} \frac{3n-4}{\ln (3n-4)}\cdot \\&\quad \left( 1+\frac{1}{\ln (3n-4)}+\frac{2}{(\ln (3n-4))^2}+ \frac{7.59}{(\ln (3n-4))^3}\right) {+\frac{1}{30}}, \\ f_2(n):= & {} n- \frac{1}{2}. \end{aligned}$$Given the previous observation \( \widetilde{U}(71) {\le } 25-\frac{1}{2} \), it suffices to show that
$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {dn}} f_1(3n-4)< \frac{\mathrm {d}}{\mathrm {dn}} f_2(n) \Longleftrightarrow \frac{\mathrm {d}}{\mathrm {dn}} f_1(3n-4) < 1 \end{aligned}$$(6)holds for all \( n \ge 25 \). By a direct calculation, it can be verified that
$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {dn}} f_1(3n-4) = \frac{3\cdot \left( (\ln (3n-4))^4+1.59\cdot \ln (3n-4)-30.36 \right) }{(\ln (3n-4))^5} \end{aligned}$$holds for any \( n>4/3 \). Consequently, since \(n \ge 25 \) (and thus \( \ln (3n-4)>0 \)) is true, we have
$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {dn}} f_1(3n-4)< & {} 1\\&\Longleftrightarrow 3\cdot \left( (\ln (3n-4))^4+1.59\cdot \ln (3n-4)-30.36 \right) <(\ln (3n-4))^5. \end{aligned}$$Setting \( x:=\ln (3n-4) \) it remains to show
$$\begin{aligned} x^5-3x^4-4.77x+91.08 > 0, \end{aligned}$$where \( x>4 \) can be assumed due to \( x \ge \ln (3\cdot 25 -4) \approx 4.26 \). Now, we end up with
$$\begin{aligned} x^5-3x^4-4.77x+91.08> & {} x^5-3x^4-5x = x(x^4-3x^3-5)>0\Longleftrightarrow x^4-3x^3 >5\nonumber \\ \end{aligned}$$(7)because \( x>4 \) is true. But the final condition in (7) is satisfied since we can state
$$\begin{aligned} x^4-3x^3=x^3(x-3)> 4^3\cdot (4-3)>5 \end{aligned}$$for \( x> 4 \). This finally shows
$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {dn}} f_1(3n-4) < 1 \end{aligned}$$for all \( n\ge 25 \), so that the left hand side of (5) grows more slowly than the right hand side. Together with \( \widetilde{U}(71) \le 25-\frac{1}{2} \) this shows (5) for any \( n \ge 25 \) and we are done.
Remark 7
Note that this proof strategy cannot simply be overtaken for the case of real-valued parameters \( \delta \) since we would be confronted with the non-differentiable term \( \lceil \delta (n-1)-1 \rceil \), so that the chain rule cannot be applied to \( f_1 \).
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Martinovic, J. A note on the integrality gap of cutting and skiving stock instances. 4OR-Q J Oper Res 20, 85–104 (2022). https://doi.org/10.1007/s10288-020-00469-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-020-00469-4