리프트 및 프로젝트 방법론 연구
- 주제(키워드) Lift-and-project , Separation , Interior point algorithm , Integer programming
- 발행기관 고려대학교 대학원
- 지도교수 최인찬
- 발행년도 2015
- 학위수여년월 2015. 8
- 학위구분 석사
- 학과 대학원 산업경영공학과
- 세부전공 산업시스템공학전공
- 원문페이지 50 p
- 실제URI http://www.dcollection.net/handler/korea/000000060552
- 본문언어 한국어
- 제출원본 000045841543
초록/요약
This study focuses on the cut generating linear problem(CGLP) from the lift-and- project method. First, we show that the nonlinear separation problem(CGNLP) derived from the polyhedral projection theorem can be transformed into a linear program. Moreover, we show that this CGLP is equivalent to the other existing forms of CGLP derived in the context of disjunctive programming or the lift-and-project relaxation. We suggest particular normalization constraint to solve the problem as a ball minimization problem or Karmarkar’s standard form and present a closed form solution in the updating scheme. Finally, we suggest some lifting variable selection rule. This enables to choose a variable to be lifted while considering the property of certain integer linear programming. keyword:
more목차
1 서론 1
1.1 연구 배경 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 연구목적 및 내용 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 논문 구성 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 기존 연구 고찰 및 예비지식 4
2.1 기존 연구 고찰 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 예비지식 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Karmarkar’s 알고리즘의 이해 . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 분기 절단법 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 분할 문제와 리프트 및 프로젝트 절단면 13
3.1 개요 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 절단면 생성 선형계획법의 유도와 비교 . . . . . . . . . . . . . . . . . . 13
3.3 분할 문제의 닫힌 형태의 해 유도와 갱신 방안 . . . . . . . . . . . . . . . 21
3.4 요약 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 리프트 변수 채택 기준의 연구 33
4.1 개요 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 동기 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 평가함수의 정의 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4 요약 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 결론 및 추후 연구 38
Bibliography 40
