검색 상세

리프트 및 프로젝트 방법론 연구

초록/요약

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

more