고객지원
기술문의
root relaxation 에대해 질문있습니다
- 강경환
- 2003.12.10
- 조회수 1,635
MIP를 푸는과정에서 제시되는 "root relaxation"방법이
어떠한 방법으로 relaxation 되는지 궁금하군요.
ILOG Document상에는 사용방법은 나와있는데, 그 원리가 무엇인지는
설명이 안되어 있습니다.
ILOG의 정책상 공개하기 곤란하시면, 관련 논문이나 Document라도
부탁을 드리겠습니다.
귀사의 무궁한 발전을 기원합니다.
어떠한 방법으로 relaxation 되는지 궁금하군요.
ILOG Document상에는 사용방법은 나와있는데, 그 원리가 무엇인지는
설명이 안되어 있습니다.
ILOG의 정책상 공개하기 곤란하시면, 관련 논문이나 Document라도
부탁을 드리겠습니다.
귀사의 무궁한 발전을 기원합니다.
댓글 1
-
- 장용성2003-12-10
- MIP는 우선 정수변수를 모두 실수변수로 바꿔서 LP로 한번 푼 후에 branch&bound 나 branch&cut으로 탐색트리를 구성해서 최종적으로 정수해를 도출합니다.
여기서 root relaxation이라고 하는 것은 branch&cut의 탐색 전에 먼저 LP로 한번 풀어내는 초기상태를 얘기하는 겁니다.
LP푸는 방법은 여러가지가 있겠구요.. 그건 알고리즘을 선택하기 나름이겠죠(rootAlg : primal, dual, network, barrier, sifting, concurrent).
이 중 몇몇 알고리즘에 대한 기본 원리는 대부분 OR(경영과학) 책에 나와 있는 걸로 알고 있습니다..
또한 ILOG에서 추천하는 아래의 책들을 참조하셔도 될 것 같습니다.
<< Williams, H. P. Model Building in Mathematical Programming, 4th ed. New York: John Wiley & Sons, 1999. This textbook includes many examples of how to design mathematical models, including linear programming formulations. (How you formulate your model is at least as important as what ILOG CPLEX does with it.) It also offers a description of the branch & bound algorithm. In fact, Williams's book inspired some of the models delivered with ILOG CPLEX. >>
<< Wolsey, Laurence A., Integer Programming, New York: John Wiley & Sons, 1998. This book explains branch and cut, including cutting planes, in detail. >>
<< Nemhauser, George L. and Laurence A. Wolsey, Integer and Combinatorial Optimization, New York: John Wiley & Sons, 1999. A reprint of the 1988 edition. This book is a widely cited and comprehensive reference about integer programming. >>
<< Gill, Philip E., Walter Murray, and Margaret H. Wright, Practical Optimization. New York: Academic Press, 1982 reprint edition. This book covers, among other topics, quadratic programming. >>
참고로, rootAlg는 초기에 LP를 풀때 동작하는 알고리즘을 말하고, nodeAlg은 branch&cut을 실행할때 동작하는 알고리즘을 말합니다.
수고하세요..
목록
확인