An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
Summary :
The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1093-1102
- Publication Date
- 2003/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shunji UMETANI, Mutsunori YAGIURA, Toshihide IBARAKI, "An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 5, pp. 1093-1102, May 2003, doi: .
Abstract: The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1093/_p
Copy
@ARTICLE{e86-a_5_1093,
author={Shunji UMETANI, Mutsunori YAGIURA, Toshihide IBARAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns},
year={2003},
volume={E86-A},
number={5},
pages={1093-1102},
abstract={The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1093
EP - 1102
AU - Shunji UMETANI
AU - Mutsunori YAGIURA
AU - Toshihide IBARAKI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.
ER -
English
