数理解析研究所講究録 1349 巻 2004 年 36-45

38
Local Search Algorithms for the TwO-Dimensional Cutting Stock
Problem with a Given Number of Different Patterns

京都大学・情報学研究科

今堀慎治 (Shinji Imahori)
柳浦睦憲 (Mutsunori Yagiura)
信也 (Shinya Adachi)
山
茨木俊秀 (Toshihide Ibaraki)
Graduate School of Informatics,
Kyoto University$\mathrm{R}^{\backslash }\ovalbox{\tt\small REJECT}$

豊田工業大学・工学研究科 梅谷俊治 (Shunji Umetani)
Graduate School of Engineering,
Toyota Technological Institute

Abstract: We consider the twO-dimensional cutting stock problem which arises in many applications in industries. In recent industrial applications, it is argued that the setup cost forchanging patterns becomes more dominant and it is impractical to use many different cutting
patterns. Therefore, we consider the pattern restricted twO-dimensional cutting stock problem,in which the total number of applications of cutting patte rns is minimized while the number ofdifferent cutting patterns is given as a parameter . For this problem, we develop local searchalgorithms. As the size of the neighborhood plays a crucial role in determining the efficiency of
local search, we propose to use linear programming techniques for the purpose of restricting thenumber of solutions in the neighborhood. In this process, to generate a cutting pattern, it isrequired to place all the given products (rectangles) irr the stock sheet (twO-dimensional area)
without mutual overlap. For this purpose, we develop a heuristic algorithm using an existing
rectangle packing algorithm with the sequence pair coding scheme. Finally, we generate random
test instances of this problem and conduct computational experiments, to see the effectivenessof the proposed algorithms.
$n$Keywords: TwO-dimensional cutting stock problem, Linear programming, Rectangle packing,
Neighborhood, Local search.

1

Introduction

We consider the twO-dimensional cutting stock problem, which is one of the representative
combinatorial optimization problems, and arises in many industries such as steel, paper, wood,-hard, since this is a generalization of the twO-dimensional bin
glass and fiber. This problem ispacking problem and the one-dimensional cutting stock problem, which are already known to be-hard, and various heuristic algorithms have been proposed $[1, 8]$ . In recent cutting industries,
the setup cost for changing patterns becomes more significant and it is often impractical to use
many different cutting patterns. We consider the twO-dimensional cutting stock problem with, in which the total number of applications of cutting
a given number of patterns$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$$n(2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}n)$37patterns is minimized while the number of different cutting patterns is given as a parameter [7].
We assume that each product can be rotated by 90’, and do not assume any constraints on
products’ placement such as “guillotine cut”.
asks to determine a set of cutting patterns and their numbers of applications. The
problem of deciding the number of applications for each pattern becomes an integer programming
problem (IP), and we propose a heuristic algorithm based on its linear programming (LP)relaxation. We also propose a local search algorithm to find a good set of cutting patterns. As
the size of the neighborhood plays a crucial role in determining the efficiency of local search,
we propose to use linear programming techniques for the purpose of restricting the nu mberof solutions in the neighborhood. To generate a feasible cutting pattern, we have to place
all products in the twO-dimensional area without mutual overlap. For this purpose, we use a
rectangle packing algorithm with a coding scheme called sequence pair [2, 3, 5]. We conduct
some computational experiments to evaluate our algorithm.
$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}n$2Formulation of$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}n$We first define the twO-dimensional cutting stock problem. We are given a sufficientnumber of stock sheets of the same length
and width $W$ , and $m$ types of products $M=$$\{1,2, \ldots, m\}$ , where each product 2 has length, widthand demand .
$(a_{1j},a_{2j},\ldots, a_{mj})$ , where $a.[j\in Z_{+}$ (theA cutting patternis described as $p_{j}=$set ofnonnegative integers) is the number of product 2 cut from pattern . We call a pattern
feasible if its all products can be cut down from one stock sheet without overlap, and ]denotes the set of all feasible patte . A solution of
consists of a set of cutting patterns$\Pi=\{p_{1},p_{2}, \ldots ,p_{|\Pi|}\}\subseteq$ S, and their numbers of applications$X=$, where$xj\in Z_{+}$ . A typical cost function is the total number of stock sheets used in the solution.
Now we consider a variant of. As noted before, it is impractical to use many different
patterns in recent cutting industries. Hence, we consider
with an input parameter ,where is the number of different patterns
problem
We call thisthe twO-dimensional
cutting stock problem with a given number of patte rns, which is formally defined
as follows:$(2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P})$$L$$l_{i}$$d_{i}$$w_{i}$$p_{j}$$p_{j}$$p_{j}$$\mathrm{e}\mathrm{t}$$S$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$$\mathrm{r}\mathrm{n}\mathrm{s}$$(x_{1}, x_{2}, \ldots, x_{1}\mathrm{I}\mathrm{I}|)$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$

$n$

$n$

$|\mathrm{I}\mathrm{I}\mathrm{L}$$n2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}\mathrm{n}$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$n:minimizesubject to$f( \Pi, X)=\sum_{p_{\mathrm{J}}\in\Pi}x_{j}$$\sum_{p_{J}\in\Pi}a_{ij}x_{j}\geq d_{i}$, for $i\in It,$$\Pi\subseteq S,$$|$

II $|=n,$$xj\in Z_{+}$, for$p_{J}.\cdot\in$II.

asks to determine a set of cutting patterns , where a cutting pattern
is a combinatiort of products cut from one stock sheet, and their numbers of applications $X$ so thatthe total number of stock sheets used is minimized while satisfying the demands of all products. In the next section, we consider the problem of computing the numbers of applications$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}n$$\Pi$$p_{j}$

38
for a given set of patterns, whereaset of cutting patterns II in Section 4.
to
find
good
a local search algorithm. We propose$X=$$(\mathrm{x}\mathrm{i}, x_{2}, \ldots, x_{n})$3Computing the number of applications for each pattern$\Pi=\{\mathrm{p}\mathrm{i},\mathrm{p}2, \ldots,p_{n}\}$$x_{j}\in Z_{+}$,In this section, we consider the problem of computing $X=$ (xi, ,the number of applications for pattern , for a given set of patterns
problem is described as the following integer programming problem (IP):$x_{2}$$\Pi$$p_{j}$$\mathrm{I}\mathrm{P}(\Pi)$:minimizesubject to$x_{n}$$\ldots$), where$x_{j}$

denotes. This$=\{\mathrm{p}\mathrm{i},\mathrm{p}2, \ldots,p_{n}\}$$f(X)= \sum_{p_{j}\in\Pi}x_{j}$.x$j\geq d_{i}$$\sum_{\mathrm{p}_{J}\in\Pi}a_{\mathrm{z}j}$$x_{j}\in Z_{+}$, for, for $i\in M,$$\in$$p_{j},$-hard sinceThis problem is already known to be strongly
consider a heuristic algorithm for this problem.
Our heuristic algorithm first solves the LP relaxation
constraints $x_{j}\in Z_{+}$ are replaced with$\mathrm{N}\mathrm{P}$$x_{j}$

n.
must be integer, and hence weof$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$$\mathrm{I}\mathrm{P}(\Pi)$, in which the integer$x_{j}\geq 0.$$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$minimize:$f(X)=$ $1$$x_{j}$$\mathrm{p}_{\mathrm{J}}\in\Pi$subject to$\sum_{p_{J}\in\Pi}a_{ij}x_{j}\geq d_{i}$$x_{j}\geq 0,$

for, for $i\in M$ ,$p_{j}\in$

H.

. In order to obtain att integerLetdenote an optimal solution ofoforder
solution, we sort aU variables j in the descending: , and round up j to j
for thein the resulting order of until all demands are satisfied. We round down j toremaining variables.
In our local search algorithm for finding a good set of patterns, which will be explained. If LP is naively solved from scratch whenever
the next section, we must solve many
we evaluate a new set of cutting patterns in the neighborhood, the computation time becomesvery expensive. We therefore incorporate a sensitive analysis technique based on the criss-crossmethod to utilize the optimal LP solution for the current set of cutting patterns.
$\mathrm{X}$$=$$(\overline{x}_{1}, \overline{x}_{2}, \ldots,\overline{x}_{n})$$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$$\overline{x}_{J}-\lfloor\overline{x}$$\overline{x}$$j$$\overline{x}$$\rfloor$$\overline{x}$$\lceil\overline{x}$$\rceil$$\lfloor X_{\mathrm{j}}\rfloor$$\mathrm{i}\mathrm{r}\mathrm{t}$$\mathrm{L}\mathrm{P}(\Pi)$4

Local search algorithm to find a good set of patterns

andconsists of a set of patterns
As noted before, a solution of
of
set
$X=$
(xi, ,, ). Our local search (LS) generates a
the numbers of their applications
patterns in the neighborhood $N(\Pi)$ of the current set of patterns . The numbers of applications
explained in the previous section.
for the new set of patterns ’ are obtained by solving: Search space, move strategy,
The following ingredients must be specified in designinga function to evaluate solutions, an initial solution and neighborhood. In our local searchalgorithm, we define the search space as the set of all II and we adopt first admissible move$\mathrm{I}\mathrm{I}=\{\mathrm{p}\mathrm{i},\mathrm{p}2, \ldots,p_{n}\}$$n$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}\mathrm{r}\mathrm{c}$$x_{2}$$\ldots$$x_{n}$

$\Pi$

$\Pi$

$\mathrm{I}\mathrm{P}(\mathrm{I}\mathrm{I}’)$$\mathrm{L}\mathrm{S}$38strategy. A set of patterns ri is evaluated by the optimal value of. Note that, we alsoansolution
integerofcomputeheuristically, and update the best solution if its value isbetter than those obtained so far. We construct att initial solution heuristically based on thenext fit algorithm for the (one dimensional) bin packing problem, since the problem to find afeasible solution is also NP-hard.
$\mathrm{L}\mathrm{P}(\Pi)$$\mathrm{I}\mathrm{P}(\mathrm{I}\mathrm{I})$4.1

Neighborhood for local search

We use the neighborhood obtained by exchanging only one cutting pattern ill the current set ofpatterns. However, the size of this neighborhood is still too large, and most of them may notlead to improvement. We propose a heuristic method to generate a smaller set of patterns toimprove the efficiency of the local search algorithm.
The solutions in our basic neighborhood of the current solution $(\Pi, X)$ are those generated by
II by the following basic operation: Remove $t(t=0,1,2)$ products
changing one patternfrom the pattern
and add one product to the pattern. The size of this neighborhoods is$O(nm^{t+1})$ for each . We use the information of overproduction $r_{i}= \sum_{j}a_{;}jxj-d_{i}$ for eachproduct to decide which products to remove. We sort surplus products in the descendingorder of overproduction , and remove products in this order in our neighborhood search. On
the other hand, we use a dual optimal solutionof
to dete rmine
the product to be added. Larger
tends to indicate that increasing
is morein patterneffective. We sort products such as $r_{i}=0$ in the descending order of , and add a product inthis order in our neighborhood search.
We introduce other operations to make the search more effective. For each pattern, surplus
products are divided into two sets. One is the set of products which do not affect the current
LP solution even if a product is removed from the pattern (i.e., the set of products such thatfor the pattern ). The other is the set of products which affect the LPandsolution if it is removed from the pattern (i.e., the set of products such that .
and, ).
$x_{j}>r_{i}$ for the pattern
It takes only $O(m)$ time to divide the products into these sets,
and all products which do not affect the current LP solution are removed from the pattern. We
call this operation as the redundancy reduction operation, and it is applied before the basic
operation.
We explain another operation of adding products after changing a pattern by the basic
operation. We divide all products into two sets according to whether overproduction
is 0 orpositive. We first add products such that $r_{i}=0$ to the pattern as much as possible. In thisstage, we sort products in the descending order of , and add them in this order. Whenever a
product is added to the pattern, we recompute an LP optimal solution and update i. When it
becomes impossible to add such products, then products with $r_{i}>0$ are added to the pattern
as much as possible. We sort these products in the ascending order of , and add them in thisorder. Since surplus products do not affect the LP solution, we can not improve the current LP
solution by this operation and it is not necessary to solve LP problem again. However, we may
improve the current LP solution in the subsequent iteration with this operation. We call thisoperation as the filling-up operation, and it is applied after the basic operation. By thes two
operations, we can improve the quality of pattern .
If all products in pattern
are removed by the redundancy reduction and basic operations,$p_{j}\in$$p_{j}$

$t$

$i$

$ri$

$\overline{Y}=$$(\overline{y}_{1}, \overline{y}_{2}, \ldots,\overline{y}_{m})$$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$$\mathrm{r}$$\overline{y}_{i}$$a_{i\dot{g}}$$p_{j\prime}$$\overline{y}_{i}$$i$$a_{ij}\geq 1$$x_{j}\leq r_{i}$$p_{j}$$i$$a_{ij}$$\geq 1$$p_{j}$$r_{i}$$\overline{y}_{i}$$\overline{y}$$r,$$\mathrm{e}$$p_{j}$$p_{j}$

40

we must reconstruct a new pattern from scratch by the basic and filling-up operations. This
with $x_{j}=0,$ and such reconstruction may not find asituation always occurs for patternwith a new pattern in this case. For thispattern with small trim loss. Therefore, we replace
purpose, we keep $cn$ ( is a parameter and we use $c=3$ ) good cutting patterns obtained by thenin memory, and choose one from them, where we define good cutting patte rn as those having
small trim loss. We call this as the replacement operation.
Now, our new neighborhood is the set of solutions obtained from by applying the operations
proposed in this section (i.e., basic, redundancy reduction, filling-up and replacement). We callthis neighborhood as the enhanced neighborhood. Two neighborhoods, basic and enhanced, willcomputationally compared in Section 5.
$p_{j}$$p_{j}$

$c$

$\Pi$

$\})\mathrm{e}$4.2Generating feasible cutting patterns

In order to generate feasible cutting patterns, we must solve the twO-dimensional rectangle-hard. That is, to judge whether a combination of products ispacking problem, which is also
realized as a feasible cutting pattern or not, we need an algorithm to place a given set of products
into the stock sheet without mutual overlap. For this purpose, we develop a heuristic algorithm
using an existing rectangle packing algorithm $[2, 3]$ , which is based on local search with a coding
scheme called sequence pair [5]. In their algorithm, they use a pair of permutations of all given
rectangles to represent a solution, and compute positions of all rectangles with their decoding
n. We omit thealgorithm. We tailored their algorithm to our local search algorithm fordetails of this algorithm here, see [4] for more detailed explanation.
$\mathrm{N}\mathrm{P}$$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$5

Computational experiments

We conducted computational experiments to evaluate the proposed algorithms. The algorithms, 1GB
were coded in thelanguage and run on a handmade PC (Intel Pentium IV
memory).
$2.8\mathrm{G}\mathrm{H}\mathrm{z}$$\mathrm{C}$

5.1

Test instances

We generated random test instances offollowing the generation scheme described in$[6, 8]$ . The instances are characterized by the following three parameters.
$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$

Number of product types: We have four classes 20, 30, 40 and 50 of the numberof product types $m$ (e.g., $m=20$ in class 20).
Range of demands: Demand of type ( stands for small) is randomly takenfrom interval $[1, 25]$ , type (large) is taken from $[100, 200]$ , and type (variable)
is taken from either intervals $[1, 25]$ or $[100, 200]$ with the equal probability foreach product .
$d_{i}$$\mathrm{S}$$\mathrm{S}$$\mathrm{V}$$\mathrm{L}$$i$, and of the stock sheets. Class
Size of stock sheet: We have five classes ,is the smallest stock sheet which can contain six products on the average,
while class is the largest containing about 50 products.
$\alpha$$\alpha$$\epsilon$$\beta,\gamma$$\delta$$\epsilon$

41
Hence, there are 60 types of instances and we generated one instance for each type. These, . . ., “20S\"a,,instances are named like “20S\"a,, . .. ’, “also”, ..,“50V\"e. In our computational experiments, we apply our local search algorithms ten times toeach instance with different initial solutions, and report the average results of ten trials. All test
instances are electronically available from our web site(http:-or.
.kyotO-u.
imahorilpacking/).
$” 20\mathrm{V},"$$” 20\mathrm{L}\alpha"$$” 20\mathrm{S}7"$$\mathrm{J}$$//\mathrm{w}\mathrm{w}\mathrm{w}$5.2$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}l^{\sim}$$\mathrm{a}\mathrm{m}\mathrm{p}.\mathrm{i}$Comparison of basic and enhanced neighborhoods

First, basic and enhanced neighborhoods were computationally compared. For each instance,
we applied our local search algorithm with each type of neighborhood ten times, and report the
average quality of the obtained solutions and computational time, where local search halts only
when a locally optimal solution is reached. For simplicity, we set the number of different cutting
patterns to the number of product types (i.e., $n=m$ ). Results are shown in Table 1. Column

Table 1: Comparison two neighborhoods in solution quality and computational timebasicenhanced$|m$qualitytime

quality

time

20
30
40
50

15.17
14.81
11.91
10.94

13.88
41.18
221.61955.64

10.49
8.71
8.76
8.18

18.42
45.76
144.93638.86shows the number of product types. For each $m$ , we have 15 instances with different rangesof demands and different sizes of stock sheet; e.g., we have instances, .. . ’,for$m=20.$ Column “quality” shows the average of the following ratio,$” \mathrm{m}$”$20\mathrm{S}\mathrm{a}$$20\mathrm{S}\mathrm{a}$$20\mathrm{V}\epsilon$

quality $=100\cdot(f-f_{LB})/f_{LB}$ ,where is the number of stock sheets used in the solution, andis a lower bound of thenumber of required stock sheets. The smaller quality means the better performance of thealgorithm. Column “time” shows the average CPU time II seconds of one local search. These
notations are also used in Table 2.
From Table 1 we can observe that the enhanced neighborhood gives smaller quality value
than the basic neighborhood in all cases, while using similar computational time. It indicatesthat the redundancy reduction, filling-up and replacement operations proposed in Section 4.1
make the search more powerful and efficient. Based on this, we will use the enhanced neighborhood in the following experiments.
$f$$f_{LB}$$\mathrm{i}$5.3Effect of the number of patterns$n$Next, we conducted computational experiments for different number of patterns , i.e., wasset to $m$ , $0.8m$ , $0.6m$ and 0.4rn. Results are given in Table 2. The leftmost column shows the
$n$

$n$

42

Table 2: Quality and time with various number of different patterns on various classes$\underline{n=m}$
qualitytimeclass 20class 30class 40

10.4918.707
8.758

18.42445.758144.932$\underline{n=0.8m}$$\underline{n=0.6m}$$\underline{n=0.4m}$

qualitytime

qualitytime

qualitytime

12.2479.899
10.3606.308
18.53345.33014.432
12.17512.2183.753
6.424
15.63020.8101.954

16.758

3.098
7.091

16.891$. \frac{\mathrm{c}1\mathrm{a}\mathrm{s}\mathrm{s}508.177636.8619.940143.13511.50437.29215.31512.117}{\mathrm{c}1\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{S}12.531149.20014.55547.33516.37715.37320.7696.348}$

class$\mathrm{L}$

6.185

262.195

57.1787.390

12.40316.865

9.100

5.369

$\frac{\mathrm{c}1\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{V}8.384223.0879.89055.46712.26915.08619.1586.478}{\mathrm{c}1\mathrm{a}\mathrm{s}\mathrm{s}\alpha 10.51646.94412.43610.00116.3231.84328.2030.264}$

class
class
class
class

$\beta$$\gamma$$\delta$$\epsilon$

average

8.048
7.924
7.331
11.3489.033

71.712
141.175
311.113486.525
211.494

10.0279.661
8.483
12.451
10.61219.43614.912

3.388
6.258
15.82751.55915.77512.26911.5309.397
13.391
12.582

15.57928.29560.768151.9901
53.327

10.79513.87117.443

0.780
1.627
6.567
21.087
6.065

instance classes. For example, “class 20” represents 15 instances with $m=20.$ Each figure in thisrow is the average of 150 trials (that is, 10 trials with different initial solutions for each instance,
and there are 15 instances for class 20). “class ” represents 20 instances whose demand is takenfrom interval $[1, 25]$ , and each figure is the average of 200 trials. Other rows can be similarlyinterpreted. Now from the rows for classes 20 30 40 and 50 in Table 2, we can observe that as$m$ becomes larger (i.e., from class 20 to 50), computational time increases and solution quality
becomes slightly better. As becomes smaller, the size of neighborhood becomes smaler andlocal search algorithm converges to locally optimal solutions rather quickly, making the qualityof obtained solution poorer.
From the rows for different ranges of demands (i.e., , and ), we can observe that thesolution quality for class is the worst even though all classes use similar computational time.
This is due to the influence of rounding and overproduction. Namely, we compute the numbers
by rounding from the LP solution, and it introduces a little overproductionof applications
for several product types. As the total demands is smaller for class , the effect of one unit of
overproduction to the quality is larger.
From the rows for different sizes of stock sheet (i.e., class , , , artd ), we can observethat the solution qualities for classes and are worse than others. The reason for class issimilar to the previous one. For many test instances of class , we could find good solutions if thenumbers of applications
can be fractional. However, these solutions degrade after obtaining
integer solutions. On the other hand, as the size of stock sheet becomes smaller, it becomes
harder to find a placement of products with small unused area, since there are not enough small
products to fill up the stock sheet.
$\mathrm{S}$$n$$\mathrm{S}$$\mathrm{V}$$\mathrm{L}$$\mathrm{S}$$x_{j}$$\mathrm{S}$$\alpha$$\alpha$$\delta$$\epsilon$$\gamma$$\epsilon$$\epsilon$$\epsilon$$x_{j}$$\beta$43
5.4

Trade-0fF curve between$n$and solution quality

Finally, we conducted more detailed experiment to obtain the trade-0fF curve between and thequality of the obtained solutions. We used two instances
S. The area of the stock
arid
sheet ofis four times as large as that of. Results are shown in Figures 1 and 2. Inthese figures, horizontal axis is , and vertical axis shows the solution quality and CPU time inseconds.
-LP (resp.,) shows the average quality of obtained LP solution (i.e., thenumbers of applications can be fractional) for(resp.,), and-IP (resp.,shows the average quality of obtained IP solution (i.e., the numbers of applications must
be integer) for(resp.,).
time and-time show the average CPU times in$n\leq11$
seconds for ten trials. When is very small (i.e.,
forand $n\leq 2$ for), we could
not find initial feasible solutions. From Figures 1 and 2, we observe that the computational time
tends to increase and the solution quality improves as increases. For larger , the improvement
in quality becomes tiny instead of the computational time is increasing steadily. Note that, if
the numbers of applications can be fractional, it is known that an optimal solution foruses at most $m$ different patterns. Nevertheless, our obtained LP solutions for these instanceswith $n=40$ are slightly worse than those with larger . From these observations, there is stillroom for improvement in our neighborhood search. We also observe that the gap between LP
and IP solutions forare more significant than the gap for.
$n$$40\mathrm{V}$$40\mathrm{V}\mathrm{a}$$40\mathrm{V}\mathrm{S}$$40\mathrm{V}\mathrm{a}$$n$$40\mathrm{V}\alpha$$40\mathrm{V}\delta- \mathrm{L}\mathrm{P}$$40\mathrm{V}\delta$$40\mathrm{V}\mathrm{a}$$40\mathrm{V}\mathrm{a}$$40\mathrm{V}\delta-$$\mathrm{I}\mathrm{P})$$40\mathrm{V}\delta$$40\mathrm{V}\mathrm{a}$$40\mathrm{V}\mathrm{a}$$40\mathrm{V}\mathrm{S}$$40\mathrm{V}\mathrm{a}$$n$$40\mathrm{V}\mathrm{a}$

$n$

$n$

$2\mathrm{D}\mathrm{C}\mathrm{S}\mathrm{P}$$n$$40\mathrm{V}\delta$$40\mathrm{V}\mathrm{a}$

ao

30

-LIPP

$—– 40\mathrm{V}\alpha 40\mathrm{V}\alpha-$

70$\ldots+\cdots 40\mathrm{V}\alpha-.\mathrm{m}\mathrm{e}$

25

.

20

$\cdot$50$=\vee-\circ\supset 15$$.\cdot.\dagger.......,\mathrm{a}.\backslash .’.\cdot.\cdot:.\cdot.\cdot.\cdot.\cdot......\dotplus\cdot.\cdot.\cdot.\mathrm{i}.._{}....\dotplus\cdot.\cdot\cdot.\cdot\dot{}_{}..\cdot$

40$.\sim\underline{\circ}\overline{\mathrm{o}}$

:
$!$

.

$+$

30

$\dotplus\cdot.\cdot$$\mathrm{j}\mathrm{Q}$20$.\dotplus\cdot\dotplus i\cdot.i.’.\star.....\cdot\star$

5

.

$+$

$\mathrm{j}\mathrm{Q}$$\mapsto\mapsto+$

屋

010030

num

$r$

40
of di erent pa

Figure 1: Trade-Off between

6

$n$

70

$\epsilon 0^{0}$$\mathrm{e}\prime \mathrm{n}\mathrm{s}$and solution quality for$40\mathrm{V}\mathrm{a}$Conclusion

Irr this paper, we considered the twO-dimensional cutting stock problem with a given number of
cutting patterns. We proposed a local search algorithm using linear programming techniques. In

44

–

.

$l$

$-$

$\cdot$$\cdot$

ti

.

.T...

$\mathrm{L}\mathrm{P}$$\mathrm{v}\mathrm{v}-$$—–+\cdot-\cdot$$\mathrm{s}\mathrm{o}0$$\mathrm{e}$700$._{\dot{}}$

:

25

.

!. .

$.\dotplus j\cdot+_{!}...+\cdot\dotplus’\cdot+$20$\cdot$:.

6屋0$\dotplus\cdot\cdot$.

$+$$\mathrm{s}\mathrm{o}0.\vee--\sim-\Phi$$..\cdot.+.\cdot..._{}...\cdot.\dotplus\cdot.:_{}..\cdot.\cdot.\dot{}........\cdot i.+.\dotplus\cdot.\cdot+\cdot...\cdot$

1
$15$

.

$.+!......\cdot.+.....+$
$[$

400

0

.
$\supseteq 010$$.\cdot+.\cdot+^{*}+\cdot.\cdot$

5$*^{t}$$\star^{*+}.\dotplus$

00

$++$

10

40

20

so

70

80

number of diff 『en’ pattems

Figure 2: Trade-Off between$n$and solution quality for$40\mathrm{V}\delta$

our local search algorithm, we heuristicaUy compute the number of applications for each cutting
pattern from the solution of the associated LP relaxation. To realize an efficient search, we
restrict the size of the neighborhood by considering only those solutions obtained by exchanging
one pattern in the current set of patterns. First, we proposed the basic neighborhood defined byremoving products from one pattern and add one product to the pattern. Then, we improved
this basic neighborhood using two ideas: (1) We remove all products which do not affect thecurrent LP solution and we add products as much as possible to the pattern, (2) We keep goodpatterns during the search and use them when the current pattern is found to be useless. To
check the feasibility of each pattern, we proposed a rectangle packing algorithm which is basedon an effective algorithm proposed by Imahori et al. $[2, 3]$ .
We reported computational results of the local search algorithms using two different neighborhoods, and compared their performance. We confirmed the effectiveness of various ideas togenerate a new pattern. We also pointed out that our approach can provide reasonable trade-Off
curves between the number of different cutting patterns and the quality. As a future work, weare planning to improve the solution quality by introducing more efficient neighborhood searchand by incorporating advanced metaheuristic algorithms.
$t$References[1]$\mathrm{P}.\mathrm{C}$. Gilmore and$\mathrm{R}.\mathrm{E}$. Gomory, Multistage cutting stock problems of two and more dimen-

sions, Operations Research, 13, pp. 94-119, 1965.
[2] S. Imahori, M. Yagiura and T. Ibaraki, Local search algorithms for the rectangle packing
problem with general spatial costs, Mathematical Programming Series (to appear).
$\mathrm{B}$45[3] S. Imahori, M. Yagiura arrd T. Ibaraki, Improved local search algorithms for the rectangle packing problem with general spatial costs, submitted for publication (available at-or.amp.i.kyot0-u.
packing$\mathrm{h}\mathrm{t}\mathrm{t}\mathrm{p}:\oint/\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}\oint\sim \mathrm{i}\mathrm{m}\mathrm{a}\mathrm{h}\mathrm{o}\mathrm{r}\mathrm{i}\oint$[4] S. Imahori, M. Yagiura, S. Umetani, S. Adachi and T. Ibaraki, Local search algorithms forthe twO-dimensional cutting stock problem with a given number of different patterns, submitted for publication (available at http://www-0r.amp.i.ky0t0-u.ac.jp/ imahorifpacking).
$\sim$[5] H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, VLSI module placement based onrectangle-packing by the sequence-pair, IEEE Transactions on Computer Aided Design , 15,
pp.1518-1524, 1996.
[6] J. Riehme, G. Scheithauer and J. Terno, The solution of twO-stage guillotine cutting stock
problems having extremely varying order demands, European Journal of Operational Research, 91, pp. 543-552, 1996.
[7] S. Umetani, M. Yagiura and T. Ibaraki, An-based local search to the one dimensional
cutting stock problem using a given number of cutting patterns, IEICE Transactions on
Fundamentals, E86-A, pp. 1093-1102, 2003.
$\mathrm{L}\mathrm{P}$[8]. Valdes, A. Parajon, and. Tamarit, A computational study of-based heuristic
algorithms for twO-dimensional guillotine cutting stock problems, OR Spectrum , 24, pp.179192, 2002.
$\mathrm{R}.\mathrm{A}$$\mathrm{J}.\mathrm{M}$$\mathrm{L}\mathrm{P}$