Publications
Detailed Information
Integer programming models and exact algorithms for the two-dimensional two-staged knapsack problem : 2차원 2단계 배낭문제에 대한 정수계획모형 및 최적해법
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 이경식
- Issue Date
- 2021-02
- Publisher
- 서울대학교 대학원
- Keywords
- Integer Programming ; Two-dimensional two-staged knapsack problem ; Dantzig-Wolfe decomposition ; Branch-and-price algorithm ; 정수최적화 모형 ; 2차원 2단계 배낭 문제 ; 분지평가 알고리즘 ; 분지절단 알고 리즘 ; 비교분석
- Description
- 학위논문 (석사) -- 서울대학교 대학원 : 공과대학 산업공학과, 2021. 2. 이경식.
- Abstract
- In this thesis, we study integer programming models and exact algorithms for the two-dimensional two-staged knapsack problems, which maximizes the profit by cutting a single rectangular plate into smaller rectangular items by two-staged guillotine cuts. We first introduce various integer programming models, including the strip-packing model, the staged-pattern model, the level-packing model, and the arc-flow model for the problem. Then, a hierarchy of the strength of the upper bounds provided by the LP-relaxations of the models is established based on theoretical analysis. We also show that there exists a polynomial-size model that has not been proven yet as far as we know. Exact methods, including branch-and-price algorithms using the strip-packing model and the staged-pattern model, are also devised. Computational experiments on benchmark instances are conducted to examine the strength of upper bounds obtained by the LP-relaxations of the models and evaluate the performance of exact methods. The results show that the staged-pattern model gives a competitive theoretical and computational performance.
본 논문은 2단계 길로틴 절단(two-staged guillotine cut)을 사용하여 이윤을 최대화하는 2차원 2단계 배낭 문제(two-dimensional two-staged knapsack problem: 이하 2TDK)에 대한 정수최적화 모형과 최적해법을 다룬다. 우선, 본 연구에서는 스트립패킹모형, 단계패턴모형, 레벨패킹모형, 그리고 호-흐름모형과 같은 정수최적화 모형들을 소개한다. 그 뒤, 각각의 모형의 선형계획완화문제에 대해 상한강도를 이론적으로 분석하여 상한강도 관점에서 모형들 간 위계를 정립한다. 또한, 본 연구에서는 2TDK의 다항크기(polynomial-size) 모형의 존재성을 처음으로 증명한다. 다음으로 본 연구는 2TDK의 최적해를 구하는 알고리즘으로써 패턴기반모형들에 대한 분지평가 알고리즘과 레벨패킹모형을 기반으로 한 분지절단 알고리즘을 제안한다. 단계패턴모형이 이론적으로도 가장 좋은 상한강도를 보장할 뿐만 아니라, 계산 분석을 통해 단계패턴모형을 기반으로 한 분지평가 알고리즘이 제한된 시간 내 좋은 품질의 가능해를 찾음을 확인하였다.
- Language
- eng
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.