Jinwoo Naa, Byung-In Kima,*
aDepartment of Industrial and Management Engineering, Pohang University of Science and Technology (POSTECH), Pohang, Gyeongbuk, 37673, Republic
of Korea
*Corresponding author. E-mail address: bkim@postech.ac.kr (B.-I. Kim)
Benchmark Instances (Click)
Last updated: 2026/03/09
1.
Introduction
We introduce a variant of the 1.5D-CSP with intermediate rolls and usable leftovers in
stainless steel coil slitting. The main features of this problem are as
follows:
(1)
1.5D-CSP with
intermediate rolls.
(2)
Usable leftovers
generated from intermediate rolls.
(3)
Strong
heterogeneity in sizes of available stocks.
In stainless steel coil slitting, a raw coil may
either be processed as a whole or first split into two intermediate rolls, each
serving different groups of orders with distinct characteristics. This
flexibility fundamentally changes the structure of the optimization problem
because it eliminates the separability typically assumed in classical CSP
problems, which allows optimization to be
decomposed by material characteristics.
Furthermore, the widths of intermediate rolls depend on cutting patterns
determined by order widths, slit losses, and leftover management, and usable
leftovers may arise from both intermediate rolls. As a result, integrating
these decisions significantly increases both the complexity and the practical
relevance of the problem.
2.
Benchmark instances
The random instances were generated based on
real-world setting summarized in Table 1. The instances were categorized into
three size groups: small (S), medium (M), and large (L). The classification was
determined according to the number of orders, the number of order groups, the
total demand, the number and total weight of eligible inventory and candidate
coils (both hot rolled and cold rolled). The detailed characteristics of the
instances are summarized in Table 2.
Table 1. Real-world setting for generating instances
|
Category |
Description |
Value |
|
Width |
Minimum rolling width (mm) |
580 |
|
|
Maximum
normal rolling width (mm) |
1200 |
|
|
Maximum
narrow rolling width (mm) |
700 |
|
|
Minimum cold-rolled
split part width (mm) |
200 |
|
|
Maximum
cold-rolled split part width (mm) |
1600 |
|
|
Minimum
hoop width (mm) |
50 |
|
|
Maximum
hoop width (mm) |
300 |
|
Capacity |
Total
rolling capacity (ton) |
5100 |
|
|
Narrow
width rolling capacity (ton) |
1050 |
Table 2. Characteristics of instances.
|
|
Small |
|||||||||
|
Instance set |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
S8 |
S9 |
S10 |
|
# order |
3 |
3 |
3 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
|
# groups |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
5 |
5 |
5 |
|
Total demand (t) |
51 |
43 |
98 |
138 |
114 |
128 |
115 |
69 |
121 |
145 |
|
Inventory hot-rolled coils |
24 |
24 |
22 |
17 |
27 |
36 |
24 |
40 |
27 |
37 |
|
Inventory hot-rolled coils weight (t) |
410 |
410 |
379 |
279 |
454 |
613 |
410 |
673 |
454 |
629 |
|
# Inventory cold-rolled coils |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
Inventory cold-rolled weight (t) |
15 |
15 |
15 |
0 |
15 |
0 |
10 |
15 |
10 |
15 |
|
# Candidate hot-rolled coils |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Candidate hot-rolled coils weight (t) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
# Candidate cold-rolled coils |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Candidate cold-rolled coils weight (t) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
Medium |
Large |
||||||||
|
Instance set |
M1 |
M2 |
M3 |
M4 |
M5 |
L1 |
L2 |
L3 |
L4 |
L5 |
|
# order |
17 |
15 |
15 |
16 |
25 |
119 |
119 |
119 |
119 |
114 |
|
# groups |
16 |
11 |
11 |
14 |
19 |
56 |
59 |
62 |
58 |
60 |
|
Total demand (t) |
506 |
646 |
735 |
508 |
1130 |
3822 |
4088 |
4170 |
4333 |
3318 |
|
Inventory hot-rolled coils |
262 |
174 |
177 |
262 |
274 |
558 |
586 |
569 |
599 |
565 |
|
Inventory hot-rolled coils weight (t) |
4273 |
2773 |
2828 |
4273 |
4465 |
9094 |
9562 |
9429 |
9805 |
9235 |
|
# Inventory cold-rolled coils |
89 |
0 |
0 |
89 |
89 |
95 |
95 |
146 |
84 |
103 |
|
Inventory cold-rolled weight (t) |
1599 |
0 |
0 |
1599 |
1599 |
1699 |
1699 |
2617 |
1501 |
1843 |
|
# Candidate hot-rolled coils |
10 |
5 |
5 |
10 |
10 |
21 |
21 |
21 |
21 |
21 |
|
Candidate hot-rolled coils weight (t) |
179 |
90 |
90 |
179 |
179 |
369 |
369 |
369 |
369 |
369 |
|
# Candidate cold-rolled coils |
4 |
0 |
1 |
4 |
5 |
9 |
9 |
9 |
9 |
9 |
|
Candidate cold-rolled coils weight (t) |
68 |
0 |
18 |
68 |
86 |
158 |
158 |
158 |
158 |
158 |
|
*Inventory and candidate coils include only those
eligible for at least one order in the corresponding instance. |
||||||||||
3. Computational results
The proposed matheuristic was evaluated via a
series of computational experiments by comparing it with three baseline
methods: (1) the exact MILP model, (2) a heuristic constructor, and (3) a standard ALNS algorithm. All algorithms
were implemented in C++, with IBM ILOG CPLEX 22.1 as the MILP solver, on a
computer equipped with an Intel(R) Core (TM) i9-10900K 3.7-GHz processor and 64
GB RAM. The parameter settings for the MILP model and all algorithms are
summarized in Table 3.
Table 3. Parameter settings for MILP and all algorithms.
|
Category |
Description |
Value |
|
Objective weight factor |
Unusable leftover ( |
5 |
|
|
Usable leftover ( |
1 |
|
|
Candidate coil usage ( |
1 |
|
Destroy size |
Destroy
ratio |
0.1 ~ 0.4 |
|
|
Destroy
size for sub-MILP repair |
10 ~ 30 |
|
Acceptance |
Initial temperature
( |
|
|
|
Cooling
factor ( |
0.99 |
|
Operator weight adaptation |
Reaction
factor |
0.1 |
|
|
Score for
finding best solution |
5 |
|
|
Score for
improving current solution |
3 |
|
|
Score for
accepted new solution |
1 |
|
Time limit |
MILP time
limit |
600(s) |
|
|
Algorithm time limit |
600(s) |
|
|
Sub-MILP repair time limit |
20(s) |
Table 4 presents the comparison of results with
MILP and proposed matheuristic algorithm. For each method, the CPU time
(in seconds), objective function value (OFV), and gap are provided. The definition of the gap is
given in Equation (1).
|
|
(1) |
Table 4. Comparison of results with MILP and proposed matheuristic.
|
Instances |
MILP |
|
Proposed matheuristic |
Gap (%) |
||
|
|
CPU(s) |
OFV |
|
CPU(s) |
OFV |
|
|
S1 |
0.13 |
24597.8* |
|
0.03 |
24597.8* |
0.0 |
|
S2 |
0.11 |
25355.3* |
|
0.04 |
25355.3* |
0.0 |
|
S3 |
0.18 |
38425.4* |
|
0.16 |
38425.4* |
0.0 |
|
S4 |
0.34 |
102161.7* |
|
0.18 |
102161.7* |
0.0 |
|
S5 |
0.18 |
49581.8* |
|
0.13 |
49581.8* |
0.0 |
|
S6 |
0.18 |
78619.7* |
|
0.14 |
78619.7* |
0.0 |
|
S7 |
0.14 |
40529.7* |
|
0.05 |
40529.7* |
0.0 |
|
S8 |
0.17 |
46095.3* |
|
0.10 |
46095.3* |
0.0 |
|
S9 |
0.21 |
54274.9* |
|
0.09 |
54274.9* |
0.0 |
|
S10 |
0.54 |
46142.2* |
|
0.48 |
46142.2* |
0.0 |
|
Average |
0.22 |
50578.4 |
|
0.14 |
50578.4 |
0.0 |
|
M1 |
600.0 |
164442.6 |
|
600.0 |
164442.6 |
0.0 |
|
M2 |
600.0 |
196314.0 |
|
204.4 |
196309.8 |
0.0 |
|
M3 |
236.9 |
505462.6* |
|
52.9 |
505462.6* |
0.0 |
|
M4 |
51.7 |
195139.4* |
|
42.3 |
195139.4* |
0.0 |
|
M5 |
600.0 |
648224.7 |
|
170.9 |
645856.1 |
0.4 |
|
Average |
417.7 |
341916.7 |
|
214.1 |
341442.1 |
0.1 |
|
L1 |
600.0 |
1730285.6 |
|
600.0 |
1402704.1 |
19.0 |
|
L2 |
600.0 |
- |
|
600.0 |
1835475.5 |
- |
|
L3 |
600.0 |
3380527.5 |
|
600.0 |
1746365.9 |
48.3 |
|
L4 |
600.0 |
1929067.8 |
|
600.0 |
1744303.0 |
9.6 |
|
L5 |
600.0 |
2245805.1 |
|
600.0 |
1583572.7 |
29.5 |
|
Average |
600.0 |
2321421.5 |
|
600.0 |
1662484.2 |
26.6 |
We compare the proposed method with a standard
ALNS without the sub-MILP repair operator. The results are shown in Table 8.
The definitions of the gaps in the table are given in Equations (2-5).
|
|
(2) |
|
|
(3) |
|
|
(4) |
|
|
(5) |
Table 5. Comparison of results with the constructor, standard ALNS,
and proposed matheuristic.
|
Instances |
Constructor |
|
Standard ALNS |
|
Proposed
matheuristic |
Gap1 |
Gap2 |
Gap3 |
Gap4 |
|||
|
|
CPU(s) |
OFVa |
|
CPU(s) |
OFVb |
|
CPU(s) |
OFVc |
|
|
|
|
|
S1 |
0.02 |
35163.3 |
|
0.03 |
24597.8* |
|
0.03 |
24597.8* |
0.0 |
30.1 |
30.1 |
0.0 |
|
S2 |
0.03 |
32906.3 |
|
0.04 |
25355.3* |
|
0.04 |
25355.3* |
0.0 |
23.0 |
23.0 |
0.0 |
|
S3 |
0.03 |
129292.4 |
|
0.86 |
38425.4* |
|
0.16 |
38425.4* |
0.0 |
70.3 |
70.3 |
0.0 |
|
S4 |
0.03 |
135349.8 |
|
0.61 |
102161.7* |
|
0.18 |
102161.7* |
0.0 |
24.5 |
24.5 |
0.0 |
|
S5 |
0.03 |
68964.4 |
|
0.13 |
49581.8* |
|
0.13 |
49581.8* |
0.0 |
28.1 |
28.1 |
0.0 |
|
S6 |
0.03 |
181695.5 |
|
0.14 |
78619.7* |
|
0.14 |
78619.7* |
0.0 |
56.7 |
56.7 |
0.0 |
|
S7 |
0.03 |
62237.9 |
|
0.05 |
40529.7* |
|
0.05 |
40529.7* |
0.0 |
34.9 |
34.9 |
0.0 |
|
S8 |
0.03 |
58501.0 |
|
0.07 |
46095.3* |
|
0.10 |
46095.3* |
0.0 |
21.2 |
21.2 |
0.0 |
|
S9 |
0.03 |
58419.9 |
|
0.06 |
54274.9* |
|
0.09 |
54274.9* |
0.0 |
7.1 |
7.1 |
0.0 |
|
S10 |
0.03 |
103291.1 |
|
1.44 |
46142.2* |
|
0.48 |
46142.2* |
0.0 |
55.3 |
55.3 |
0.0 |
|
Average |
0.03 |
86582.2 |
|
0.34 |
50578.4 |
|
0.14 |
50578.4 |
0.0 |
35.1 |
35.1 |
0.0 |
|
M1 |
0.07 |
303386.2 |
|
600.0 |
172966.2 |
|
600.0 |
164442.6 |
-5.2 |
43.0 |
45.8 |
4.9 |
|
M2 |
0.04 |
370514.8 |
|
600.0 |
196698.7 |
|
204.4 |
196309.8 |
-0.2 |
46.9 |
47.0 |
0.2 |
|
M3 |
0.04 |
678356.0 |
|
600.0 |
507613.5 |
|
52.9 |
505462.6* |
-0.4 |
25.2 |
25.5 |
0.4 |
|
M4 |
0.04 |
414394.5 |
|
600.0 |
195953.1 |
|
42.3 |
195139.4* |
-0.4 |
52.7 |
52.9 |
0.4 |
|
M5 |
0.05 |
821515.3 |
|
600.0 |
654293.6 |
|
170.9 |
645856.1 |
-0.9 |
20.4 |
21.4 |
1.3 |
|
Average |
0.05 |
517633.4 |
|
600.0 |
345505.0 |
|
214.1 |
341442.1 |
-1.4 |
37.6 |
38.5 |
1.4 |
|
L1 |
0.09 |
1947612.7 |
|
600.0 |
1568495.6 |
|
600.0 |
1402704.1 |
9.4 |
19.5 |
28.0 |
10.6 |
|
L2 |
0.10 |
2283341.0 |
|
600.0 |
1945298.7 |
|
600.0 |
1835475.5 |
- |
14.8 |
19.6 |
5.7 |
|
L3 |
0.09 |
2291673.6 |
|
600.0 |
1883129.9 |
|
600.0 |
1746365.9 |
44.3 |
17.8 |
23.8 |
7.3 |
|
L4 |
0.09 |
2202330.2 |
|
600.0 |
1849406.9 |
|
600.0 |
1744303.0 |
4.1 |
16.0 |
20.8 |
5.7 |
|
L5 |
0.12 |
1978322.0 |
|
600.0 |
1631463.5 |
|
600.0 |
1583572.7 |
27.4 |
17.5 |
20.0 |
2.9 |
|
Average |
0.10 |
2140655.9 |
|
600.0 |
1775558.9 |
|
600.0 |
1662484.2 |
21.3 |
17.1 |
22.4 |
6.4 |