A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems
- Title
- A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems
- Author
- 강맹규
- Keywords
- Cutting problem; Optimization; Branch and bound; Two-dimensional
- Issue Date
- 2003-07
- Publisher
- ELSEVIER SCIENCE BV
- Citation
- OPERATIONS RESEARCH LETTERS, v. 31, issue. 4, page. 301-307
- Abstract
- This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.
- URI
- https://www.sciencedirect.com/science/article/pii/S0167637703000026https://repository.hanyang.ac.kr/handle/20.500.11754/156023
- ISSN
- 0167-6377
- DOI
- 10.1016/S0167-6377(03)00002-6
- Appears in Collections:
- COLLEGE OF ENGINEERING SCIENCES[E](공학대학) > INDUSTRIAL AND MANAGEMENT ENGINEERING(산업경영공학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML