|
|
제 목 |
Column Generation(Solver 사용시) |
|
작성자 |
소경철 |
작성일 |
2002-01-25 |
조회수 |
1499 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
1. 예제를 잘 분석해보면, 크게 두 개의 Model(main, sub)로 구성되어 있음을 알 수 있습니다.
여기서 sub problem은 순수하게 패턴을 생성하는 일만 하게 되는거죠.
그리고, main problem은 패턴이 생성될 때마다 그 패턴을 추가해서 LP를 실행하고, 그 결과를 이용해서 더 이상 패턴을 생성할 필요가 있는지 체크하는 기능을 합니다.
그래서, 더이상 패턴을 생성할 필요가 없다고 판단되면, 현재의 패턴들을 가지고 최종적으로 가장 좋은 패턴을 선택하기 위해 MIP을 실행하게 되죠.
이 부분에서 처음 실수형 변수로 생성했던 변수(각 패턴과 일대일로 대응하는 변수)를 정수형 변수로 변환을 합니다. (IloConversion 사용)
따라서, 모든 패턴 생성 과정이 끝난 다음에 최종적으로 B&B가 사용되게 되는 것이죠...
(결정변수 중에 정수형이 있으면 자동적으로 CPLEX가 알아서 mipSolver가 동작하며, 이 과정에서 B&B가 실행됩니다.)
2. Column Generation 문제에서 패턴을 만드는 부분을 구현할 때 보통 ILOG Solver를 많이 사용하게 됩니다. 물론, 패턴을 만들기 위한 제약들 중에서 선형으로 표현하기 어려운 것이 많기 때문이죠.
하지만, Solver를 사용하면서 이 예제처럼 구현하는 것은 약간 어렵습니다. 상황에 따라서 구현하는 방법이 다양하기도 하구요..
이 예제의 경우에는 LP 실행 후 얻을 수 있는 Dual value를 가지고, Solver를 이용하여 생성된 패턴들의 Reduced Cost를 계산할 수가 있습니다. 이렇게 계산된 Reduced Cost 중에서 가장 작은 (-)값을 갖는 패턴을 선택하여 원모델에 추가하면 되겠죠..
이 과정을 반복하면 CPLEX를 이용한 Column Generation 방법과 거의 동일한 효과를 볼 수 있습니다.
Column Generation에 관한 논문이나 서적들을 참조해보시면 도움이 되실 것입니다.
감사합니다.
:황준하님의 글입니다.
:부산대학교 컴퓨터공학과 황준하입니다.
:Concert 1.0, Solver 5.0, CPLEX 7.0을 사용하여 정수계획법 문제를 풀고자 합니다.
:column generation 기법을 사용할려고 합니다. 관련 예제는 Concert User\''s Manual Chapter 5 Cutting Stock : Column Generation 이란 부분이 있어 참고를 하고 있습니다.
:이와 관련하여 두 가지 문의 사항이 있습니다.
:
:첫번째는 예제에는 IP 문제인데도 불구하고 branch & bound 를 하지 않고 root node에서 column generation을 이용하여 LP를 푼 다음 IloConversion을 사용하여 integer 값으로 변환하고 있습니다. IP를 풀기 위해서는 branch & bound를 써야 할 것 같은데(아마도 Goal을 사용?) 어떻게 해야 하는지 궁금합니다.
:
:두번째는 예제에는 LP를 풀 때 column을 생성하기 위해 cplex를 사요하고 있는데 (즉, cplex 객체 두 개를 사용) 저는 column을 생성할 때 제약조건들이 linear하게 표현되지 않기 때문에 solver를 사용할려고 하는데 solver를 사용하여 최적화도 해야 하고 중간에 새로운 제약(reduced cost 관련)도 추가해야 하는데 구현이 좀 어려운 것 같습니다.
:
:도움이 될만한 방법이나 자료가 있으면 알려주시면 감사하겠습니다.
:
: |
|
|
|
