Families of non-IRUP instances of the one-dimensional cutting stock problem.
In case of the one-dimensional cutting stock problem (CSP) one can observe for any instance a very small gap between the integer optimal value and the continuous relaxation bound. These observations have initiated a series of investigations. An instance possesses the integer roundup property (IRUP) if its gap is smaller than 1. In the last 15 years, some few instances of the CSP were published possessing a gap greater than 1.In this paper, various families of non-IRUP instances are presented and methods to construct such instances are given, showing in this way, there exist much more non-equivalent non-IRUP instances as computational experiments with randomly generated instances suggest. Especially, an instance with gap equal to 10/9; is obtained. Furthermore, an equivalence relation for instances of the CSP is considered to become independent from the real size parameters.
Introduction
The one-dimensional cutting stock problem (CSP) is as follows: Given an unlimited number
of pieces of identical stock material of length L (e.g. wooden length, paper reels, etc.) the
task is to cut b i pieces of length ' i for while minimizing the number of
stock material pieces needed.
Throughout this paper we will use the abbreviation E := (m; L; '; b) for an instance of
the CSP with loss of generality we will
assume L
The classical solution approach is due to Gilmore and Gomory [5]. A non-negative
integer vector a
is called a (feasible) cutting pattern of
cutting pattern (shortly: pattern) a is said to be maximal if ' T a+'m ? L;
a is proper if a  b, i.e. a i  b i , ng denote the index set of all
maximal patterns a If the integer variable x j denotes the times
pattern a j is used, the CSP can be modelled as follows:
Now the common solution approach consists of solving the corresponding continuous (LP)
relaxation
where IR is the set of real numbers. Then, based on an optimal solution of (2), integer
solutions for (1) are constructed by means of suitable heuristics (cf. [5], [13]).
Let z  denote the optimal value of (1) and (2) for an instance
E, respectively. Practical experience and many computational tests have shown (cf. e.g.
[13], [16]) there is only a small gap \Delta(E) := z   (E) \Gamma z c (E) for any instance E.
These observations have initiated a number of investigations. A set P of instances E has
the integer round-up property (IRUP) if \Delta(E) ! 1 for all
\Delta(E)  1 is called non-IRUP instance in the following. It is well-known that the CSP
does not possess the IRUP. In [6] a first counter-example was given with gap equal to 1. In
the last decade instances were found having a gap larger then 1 ([3], [12]). Since the gaps
of these instances are less than 2, the modified integer round-up property (MIRUP) was
defined in [14]: a set P of instances E possesses the MIRUP if \Delta(E) ! 2 for all
It is conjectured in [12] that the one-dimensional CSP possesses the MIRUP.
Since in the numerical tests non-IRUP instances occur relatively rarely, the impression
could arise that there exist only a limited number of non-IRUP instances. In this paper
we will present families with an infinite number of non-equivalent non-IRUP instances.
These investigations could be helpful for developing and testing of exact solution approaches
for the one-dimensional CSP. Especially if existing exact solution algorithms
(branch-and-bound algorithms are presented e.g. in [13] for the CSP and in [7] for the
bin packing problem) are applied to non-IRUP instances then computational difficulties
can arise. Moreover, they could have importance also for higher dimensional CSPs. For a
comprehensive overview of recent work in connection with cutting and packing problems
we refer to [2].
Throughout this paper we will use some common notations. Let M   denote the set of
instances possessing IRUP. Especially for theoretical investigations, a special case of the
CSP is of interest which is named divisible case. An instance E belongs to the set D of
'divisible case'-instances if L is an integer multiple of any piece length. For example, the
instance
(presented in [11]) belongs to D and has gap \Delta(E D which is the
largest for D ever found.
In our investigations we allow also rational sizes, i.e. we assume ' 2 IQ m
and
IQ is the set of rational numbers. In the most cases we will consider equivalent instances
with integer sizes.
In the next section we will introduce an equivalence relation for instances of the CSP in
order to characterize different instances in a better way and to become independent from
the real sizes. Then in section 3, we will consider families of non-IRUP instances in the
divisible case. Families of non-IRUP instances not restricted to the divisible case will
be presented in section 4. Constructive methods to obtain non-IRUP instances will be
discussed in the fifth section followed by some concluding remarks.
2 Equivalence of Cutting Stock Problems
Among some possibilities of defining equivalence relations for instances of CSPs we will
consider here only the kind of equivalence which is based on the cutting patterns. Through-out
this section we assume all input-data to be integral.
2.1 Pattern equivalence
Let the instances
cutting patterns, respectively.
Without loss of generality the cutting patterns are assumed to be sorted lexicographically
decreasing.
are called equivalent (pattern-equivalent) if
Hence, any feasible pattern a j of E is also feasible for E and vice versa.
For example, the following instances E are equivalent to the instance
26  ' 3  30,
for all d; d
Let A(E) denote the m \Theta n-matrix containing all maximal patterns of E. Hence, E and
are equivalent if and only if
Then the class K(E) of instances equivalent to E can be characterized as follows:
Obviously,
K(E). For that
reason, K(E) can be viewed as the intersection of ZZ m+1 and a cone which is induced by
A(E).
2.2 Characterization by system of inequalities
Let e i denote the i-th unit vector of ZZ m (i 2 I).
Assertion 1 Let a denote the maximal cutting patterns of instance
b). Then the instance is equivalent to E if and only if ('; L) 2 ZZ m+1 is
feasible for
Proof: ")" E is equivalent to E, that means A(E) is pattern matrix of E. Hence, (4),
(5) and (6) are fulfilled.
"(" Let ('; L) 2 ZZ m+1 fulfill (4), (5) and (6). Because of (6) it follows
1. Because of (4) any maximal cutting pattern of E is also feasible with respect to
E. Because of (5) any maximal cutting pattern of E is also maximal with respect to E.
Assume there exists a maximal cutting pattern a of E which is not feasible or is not
maximal with respect to E.
If a is not maximal but feasible with respect to E then a with respect
to E and there exists a  2 ZZ such that a with respect to E .
occurs in (4) a contradiction arises to a is maximal with respect to E.
If a is not feasible with respect to E , i.e. '
a there exists a pattern ea with
which is maximal with respect to E . Hence, ' T ea  L (because of
(because of (5)). This leads to a contradiction to a is feasible
with respect to E.
2.3 Dominance
Let a pattern matrix In order to get an instance of the cutting
stock problem with pattern matrix A, one has to determine a solution of (4) - (6).
Because of the condition numerous constraints in (4) and (5), respectively,
will automatically be fulfilled if other constraints are fulfilled as the following example
shows. Let
From ' T a 1  L and 9. That means, at most
the constraint ' T a 1  L is active in (4). Analogously, if ' T (a 9
8. Hence, again only one of the inequalities in (5) is
needed.
Definition 2 The cutting pattern a dominates the cutting pattern a if ' T a  ' T a for all
fulfilling
For a
Assertion 2 Let the patterns a and a be given. Then:
a ? d a
Proof: ")" If s 1 (a) ! s 1 (a) then a 1 ! a 1 and hence, a 6? d a.
f1g such that s j (a)  s j (a) for
We define the vector ' 2 ZZ m
such that ' T a
Then
-z
=: ff
-z
-z
-z
It follows
sufficiently large since ff, fi and fl are independent of ' 0 .
"(" Now we assume s i (a)  s i (a) for all i and
-z
-z
-z
0:
A pattern a is said to be dominant if there does not exist any (feasible) pattern a, a 6= a,
with a ! d a. If ' and L are fixed then a pattern a can easily be identified to be dominant.
Let
Assertion 3 The pattern a is dominant if and only if
ffi(a). Then there exists i 2 I n fmg with a
the pattern a dominates a, a cannot be dominant.
If a is not dominant then there exists a pattern a, a 6= a, with a ! d a. The following
procedure can be applied at least once:
Let j be the index determined by a
-z
Otherwise the pattern ea is defined by
a i otherwise.
Then
Furthermore, a ! d ea since s i
because of (7), we have ' T
Otherwise the procedure has to be repeated with ea instead of a.
Let J d ae ng denote the index-set of dominant cutting patterns in A. Then:
Assertion 4 ('; L) 2 ZZ m+1
fulfills (4) if and only if ('; L) is feasible for
Proof: Since for any cutting pattern a j there exists a column a k with k 2 J d and a j ! d a k ,
Furthermore, a maximal pattern a is said to be non-dominant if there does not exist any
maximal pattern a, a 6= a, with a ! d a. Non-dominant patterns can be identified similar
to Assertion 3. Let J nd ae ng be the index-set of non-dominant cutting patterns in
A. Then:
Assertion 5 ('; L) 2 ZZ m+1
fulfills (5) if and only if ('; L) is feasible for
Proof: Since for any cutting pattern a j there exists a column a k with k 2 J nd and a j ? d a k ,
In order to illustrate the usage of dominance let us consider the instance
presented in [4] with \Delta(E G 1:0667. The instance EG has 41 feasible patterns.
Among them are 20 maximal, 7 dominant and 5 non-dominant patterns. Hence, the class
K(EG ) of equivalent instances can be described as solution set of the system of inequalities:
5:
is such a solution, EG is equivalent to
3 Divisible Case
In 1994 Nica ([9]) proposed a first infinite family of non-equivalent non-IRUP instances
of the CSP which belongs to D. For the sake of completeness we repeat here his result.
be given such that 2  . The length L
of the stock material is defined to be \Pi m
. Accordingly to the divisible case, the length
' i of the ith piece equals L=k i (i 2 I).
Using proposed in [9], are as follows:
km
Note, the instance ED defined in (3) belongs to this family with
Theorem 1 (Nica 1994) Let k 2 ZZ m be given such that 2
are pairwise relatively prime. If 1  b m ! km and if the order demands
cannot be cut using less than cutting patterns, then
Proof: Because of construction we have
z c
km
km
km
and z c (E(k))+1=km ? m \Gamma 1. Since the parameters k i are assumed to be pairwise relatively
prime there does not exist any non-negative integer vector a
a i
This means, there does not exist any proper and trim-less pattern.
If represents a maximal pattern then
a i
)c
a i
a i
a i
since km
a i
If we consider any set of cutting patterns a
fulfilling
a mj  (m
Because of
e
we obtain
a
since m  3 and k 1  2 are assumed. Hence, at least one more piece of length ' m is
ordered as can be cut with cutting patterns.
Note, the gap
km
d
is asymptotically bounded by 1 1=km and tends to 1 if km is increased.
Next we show by means of an example that non-IRUP instances can also be obtained in
the divisible case if some of the assumptions in Theorem 1 are not fulfilled. For this let us
consider the instance
with
and the k i are not pairwise relatively
prime. Using the proper relaxation bound (cf. [10]) can be verified. Moreover,
Hence, separating this pattern a new instance
can be derived from E 1 with
Now we will consider another family of instances of D with be any positive
integer and let . L is defined to be the smallest common multiple
of the k i (or a multiple of it). For abbreviation, let the family of instances
9p+2
will be investigated. Notice, ED defined in (3) belongs to this family with
Theorem 2 For any integer p  1, the instance E(p) does not belong to M   .
can be assumed. Because of E(p) 2 D we have
z
Because of z c  2, the instance E(p) would belong to M   if and only if there exist any
proper pattern a
a 1
We will show that such a pattern cannot occur.
Since in the divisible case
feasible pattern a it follows
Since
the following inequality must be fulfilled:
Because of (9) we have
Furthermore, with
it follows that the pattern a has to fulfil the inequality
Summarizing (11) and (12), if E(p) 2 M   then there must exist a proper pattern a with
Note, the left-hand side is integral. In case a the interval has the form
which contains the unique integer \Gamma2q \Gamma 1. The corresponding equation
can be transformed in
and we find for a 1  q \Gamma 1, a 1 integer, there exists no non-negative integer value a 2 .
In the other case, a 3  5, because of the interval in formula (13) can be written
in form
For the interval size is less than 5
1. Hence, there is no integer contained
in the interval. Therefore, no such pattern can exist.
4 Non-Divisible Case
The family E(t) with
is considered next.
Note, the family does not contain only non-equivalent instances. For
example, instances E(t) are equivalent and
Theorem 3 The instances E(t), t 2 T , do not belong to M   .
Proof: We show z c
Because of ' T 3. On the other hand, z c (E(t))  3 since2B
Suppose z   the optimal solution must contain only proper
patterns a with ' T a = L. We consider the pattern with a because of
is the only trim-less proper pattern. But now there does not
exist any proper trim-less pattern with a 2  1 since ' 5 is already used.
Using the substitution p=q
obtain from E(t) a further family of instances by removing the smallest piece:
Theorem 4 Let p=q 2 (0; 1), then the instance E(p; q) does not belong to M   .
The proof is similar to that of Theorem 3.
In case of p ? 1 the length of the smallest piece can be reduced to q violating
the non-IRUP property. Let
we have to show z   4. Because of
an integer solution with 3 patterns has to have a total
trim-loss of units. If such a solution exists then it must contain the pattern
with the trim-loss of p units. Since any proper pattern containing at least one piece of
length ' 2 but non of ' 5 has a trim-loss of at least p units, the total trim-loss is at least 2p
which is a contradiction.
Next we will consider the family
of non-equivalent CSP instances.
Theorem 5 The instances E(p) defined in (16) do not belong to M   .
Proof: Because
1), we have
z c (E(p))
Because of ' T the total trim-loss has to be equal to
assumed. But the best proper pattern a with a
which has a trim-loss of must
hold.
Notice, lim p!1 z c which corresponds to lim p!1 k
Moreover, since the gaps are asymptotically bounded by 1 the gaps tend to
1 for p !1. The maximal gap for this family is 29/28 obtained for
The following procedure leads to further non-equivalent non-IRUP instances if p  5:
If pieces of length ' are composed to larger ones then no better integer solution
can arise. If additionally the value of the continuous relaxation does not increase then
non-IRUP instances will be constructed. Let
2), such that p
loss of generality, let . Then the non-equivalent instance E 0 (p) derived from
E(p) is as follows in case of
Using
times the pattern ' 0+ p+1
instead of
-times the pattern (1; 0; 0; 0; in (17), a feasible solution of the LP relaxation
with the same objective function value can be obtained.
For example, let 5. Then from
using
Furthermore, if p  5, odd, ld(p+1) 62 ZZ and
because of construction,
the length '
3 now can be reduced to 2p 2 since no new proper pattern gets feasible.
On the other hand, new non-proper patterns can lead to a smaller optimal value of the
continuous relaxation. In the example we obtain
with \DeltaE 00
Next we will consider a modification of E 00 (5). Let
Here we have z c 7. Thus E(b) 62 M   . (The
verification of z   done using the cutting plane algorithm proposed in [8].)
proper pattern a of
5. If a 2 the same gap arises;
for a 2 smaller gaps occur. The corresponding residual
instance of E(b) is
Residual (cf. [12]) means there exists an optimal solution x c of the LP relaxation with
components less than 1 so that x c cannot be used for a further reduction of the order
demands.
Non-IRUP instances can also be found for special classes of CSPs. Let us consider instances
with the property k
and For short we refer such instances as (1; k)-instances. It is known, all
k)-instances belong to M   for k 2 f2; 3g. But for any k  4 there exist non-IRUP
k)-instances. Such instances for are
and
A family of non-IRUP (1; k)-instances with k  6 is the following:
Theorem 6 The instances E k , k  4, do not belong to M   .
Proof for k  6: It is easy to verify that the instance E k is a (1; k)-instance. Since
at least 3 smaller pieces can be contained in a pattern a with a Because
of follows. The reduced instance E 0
k obtained form E k by omitting the
3 pieces of length ' 1 and by setting the stock length to correspond to the instance
E(t) with considered in Theorem 3. Therefore E 0
and hence, since
z c
Remember, the instance E 0
namely we
have any i. An instance is said to be a 1)-instance
if for any i k
The proof of Theorem 6 suggests the following procedure to construct non-IRUP (1; k)-
instances. Let a non-IRUP
In order to obtain a non-IRUP (1; k)-instances at first an instance
constructed. The piece lengths are increased by t (t sufficiently large), i.e. ' 0
1)t. Then, any feasible (with respect to E) pattern a with
e T a  non-feasible (with
respect to E) pattern a with e T a  tends to infinity
then
i tends to 1=(p + 1) for i 2 I. If we add dz c (E)e pieces of length ' 0(' 0sufficiently
large) and increase the stock length by ' 0
can be reached for k  2p 2. Hence, a (1; k)-instance with m+1 piece types is obtained.
Let us now consider the set of (k; k+1)-instances with k 2 ZZ
(1,2)-instances belong to M   , but for any k  2 there exist non-IRUP (k; k+1)-instances
as will be shown next. For k  2 let
1)-instance for k  2. Note, in order to make more clear the inherent
structur we do not sort the piece lengths in decreasing order.
Theorem 7 The instance does not belong to M   .
z c
If z   supposed then no trim-loss must occur. We consider patterns a with
must contain k +1
pieces. Because of construction, pattern is not proper.
Furthermore, but again this pattern is not proper since b 7 = 1.
there is no trim-less pattern a with a
z
5 Further Constructions
be an instance not belonging to M   with
1. Moreover, let q 2 IQ with q  2=' m 0 . Then the instance E is defined by
Theorem 8 If for any a 0 2 ZZ m
then E does not belong to M   too.
Proof: At first we prove dz c (E)e  dz c
We consider an optimal solution of the LP relaxation of E 0 characterized by the set
of feasible patterns and corresponding coefficients x j ,
Now we assign to any a 0 j (j 2 J   ) an m-dimensional pattern a j as follows:
a
The patterns a j are feasible with respect to E. Then,
Using (dz c ))-times the feasible pattern a 1 := e 1
a 1j x
Supplementing (p \Gamma 1)=p-times the pattern a 2 := pe 2 and
the pattern a 3 := pe 3 , a feasible solution of the continuous relaxation of E is found (which
is not-necessarily optimal). Hence,
z c (E)  z c
Next we show z   (E) ? dz c 1. Because of patterns a j with
a are needed to cut the b 1 pieces of length ' 1 . If we suppose an integer
solution for patterns then all pieces of length ' 2 must be in one
pattern a with a the total length in a not covered with ' 2 -pieces equals qL 0 +1.
all the pieces with lengths ' 4 cannot be cut with these dz c (E 0 )e
patterns a j . At least one piece (with length  q' 0
remains unpacked. Since
this piece and the piece of length ' 3 cannot be cut in pattern a. Hence, one more pattern
is needed, that means z   (E) ? dz c
Let us consider the instance
which is equivalent to that proposed by Gau ([4], cf. (8)). Here we have
If we apply the procedure corresponding to Theorem 8 with 2, the instance
results. For this instance we get z c
obtained. This is the largest gap found so far ([15]).
It is remarkable, although ' there is no way to cut the order
demands b i with 3 patterns.
If this procedure is applied to E with then the gaps 1.0741, 1.0556,
1.0444 and 1.0394 result.
Note, the repeated application of Theorem 8 is possible but does not succeed with larger
gaps.
There are some other possibilities to obtain non-IRUP instances. Let an instance
given. If the order demand of the m-th piece is increased by some units, say
three cases can occur for
If z c
If z c (E  )  dz c (E)e and z
Otherwise, E and E  have the same behavior.
The instances considered in this paper are mostly residual instances. But, if the order
demand b of a non-IRUP instance E is increased by an non-negative integer combination
of patterns occurring in an LP solution of E then a non-IRUP instance is obtained very
often. For example, if we use ED defined in (3) then we get
To verify such statements stronger relaxations of the CSP are needed as proposed in [10]
and [8].
6 Concluding Remarks
In this paper families of non-IRUP instances of the CSP are presented. Since the gaps
tend to 1 for increasing parameters counter-examples for the MIRUP-conjecture, if such
exist, have probably small ratios between stock material length and piece lengths.
There remain some open questions. Especially the efficient identification of instances to
be a non-IRUP instance is of importance for exact solution approaches.



--R


Cutting and packing.
The duality gap in trim problems.

A linear programming approach to the cutting-stock problem (Part I)
An instance of the cutting stock problem for which the rounding property does not hold.
Knapsack Problems - Algorithms and Computer Implemen- tations
Solving cutting stock problems with a cutting plane method.
General counterexample to the integer round-up property
Tighter relaxations for the cutting stock problem
About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem
Theoretical investigations on the Modified integer Round-Up Property for the one-dimensional cutting stock problem
A branch-and-bound algorithm for solving one-dimensional cutting stock problems exactly
The modified integer round-up property of the one-dimensional cutting stock problem
A new 1csp heuristic.
Heuristics for the one-dimensional cutting stock problem: A computational study
--TR
Knapsack problems: algorithms and computer implementations
Computers and Intractability
integer round-up property;continuous relaxation;one-dimensional cutting stock problem