Publications
Detailed Information
Integer programming models and exact algorithms for the two-dimensional two-staged knapsack problem : 2차원 2단계 배낭문제에 대한 정수계획모형 및 최적해법
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 이경식 | - |
dc.contributor.author | 강수호 | - |
dc.date.accessioned | 2021-11-30T02:09:22Z | - |
dc.date.available | 2021-11-30T02:09:22Z | - |
dc.date.issued | 2021-02 | - |
dc.identifier.other | 000000164006 | - |
dc.identifier.uri | https://hdl.handle.net/10371/175194 | - |
dc.identifier.uri | https://dcollection.snu.ac.kr/common/orgView/000000164006 | ko_KR |
dc.description | 학위논문 (석사) -- 서울대학교 대학원 : 공과대학 산업공학과, 2021. 2. 이경식. | - |
dc.description.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. | - |
dc.description.abstract | 본 논문은 2단계 길로틴 절단(two-staged guillotine cut)을 사용하여 이윤을 최대화하는 2차원 2단계 배낭 문제(two-dimensional two-staged knapsack problem: 이하 2TDK)에 대한 정수최적화 모형과 최적해법을 다룬다. 우선, 본 연구에서는 스트립패킹모형, 단계패턴모형, 레벨패킹모형, 그리고 호-흐름모형과 같은 정수최적화 모형들을 소개한다. 그 뒤, 각각의 모형의 선형계획완화문제에 대해 상한강도를 이론적으로 분석하여 상한강도 관점에서 모형들 간 위계를 정립한다. 또한, 본 연구에서는 2TDK의 다항크기(polynomial-size) 모형의 존재성을 처음으로 증명한다. 다음으로 본 연구는 2TDK의 최적해를 구하는 알고리즘으로써 패턴기반모형들에 대한 분지평가 알고리즘과 레벨패킹모형을 기반으로 한 분지절단 알고리즘을 제안한다. 단계패턴모형이 이론적으로도 가장 좋은 상한강도를 보장할 뿐만 아니라, 계산 분석을 통해 단계패턴모형을 기반으로 한 분지평가 알고리즘이 제한된 시간 내 좋은 품질의 가능해를 찾음을 확인하였다. | - |
dc.description.tableofcontents | Abstract i
Contents iv List of Tables vi List of Figures vii Chapter 1 Introduction 1 1.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 8 Chapter 2 Integer Programming Models for 2TDK 9 2.1 Pattern-based Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Arc-flow Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Level Packing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Chapter 3 Theoretical Analysis of Integer Programming Models 20 3.1 Upper Bounds of AF and SM(1;1) . . . . . . . . . . . . . . . . . . 20 3.2 Upper Bounds of ML, PM(d), and SM(d; d) . . . . . . . . . . . . . . 21 3.3 Polynomial-size Model . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Chapter 4 Exact Methods 33 4.1 Branch-and-price Algorithm for the Strip Packing Model . . . . . . . 34 4.2 Branch-and-price Algorithm for the Staged-pattern Model . . . . . . 39 4.2.1 The Standard Scheme . . . . . . . . . . . . . . . . . . . . . . 39 4.2.2 The Height-aggregated Scheme . . . . . . . . . . . . . . . . . 40 4.3 Branch-and-cut Algorithm for the Modified Level Packing Model . . 44 Chapter 5 Computational Experiments 46 5.1 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2 Upper Bounds Comparison . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.1 A Group of Small Instances . . . . . . . . . . . . . . . . . . . 49 5.2.2 A Group of Large Instances . . . . . . . . . . . . . . . . . . . 55 5.2.3 Class 5 Instances . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.3 Solving Instances to Optimality . . . . . . . . . . . . . . . . . . . . . 65 5.3.1 A Group of Small Instances . . . . . . . . . . . . . . . . . . . 65 5.3.2 A Group of Large Instances . . . . . . . . . . . . . . . . . . . 69 5.3.3 Class 5 Instances . . . . . . . . . . . . . . . . . . . . . . . . . 72 Chapter 6 Conclusion 77 Bibliography 79 국문초록 83 | - |
dc.format.extent | vii, 83 | - |
dc.language.iso | eng | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | Integer Programming | - |
dc.subject | Two-dimensional two-staged knapsack problem | - |
dc.subject | Dantzig-Wolfe decomposition | - |
dc.subject | Branch-and-price algorithm | - |
dc.subject | 정수최적화 모형 | - |
dc.subject | 2차원 2단계 배낭 문제 | - |
dc.subject | 분지평가 알고리즘 | - |
dc.subject | 분지절단 알고 리즘 | - |
dc.subject | 비교분석 | - |
dc.subject.ddc | 670.42 | - |
dc.title | Integer programming models and exact algorithms for the two-dimensional two-staged knapsack problem | - |
dc.title.alternative | 2차원 2단계 배낭문제에 대한 정수계획모형 및 최적해법 | - |
dc.type | Thesis | - |
dc.type | Dissertation | - |
dc.contributor.AlternativeAuthor | Suho Kang | - |
dc.contributor.department | 공과대학 산업공학과 | - |
dc.description.degree | Master | - |
dc.date.awarded | 2021-02 | - |
dc.identifier.uci | I804:11032-000000164006 | - |
dc.identifier.holdings | 000000000044▲000000000050▲000000164006▲ | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.