|
|
제 목 |
[RE]root relaxation 에대해 질문있습니다 |
|
작성자 |
장용성 |
작성일 |
2003-12-10 |
조회수 |
906 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
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을 실행할때 동작하는 알고리즘을 말합니다.
수고하세요.. |
|
|
|
