고객지원
기술문의
IP : column generation
- 황준하
- 2002.01.25
- 조회수 2,285
부산대학교 컴퓨터공학과 황준하입니다.
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 관련)도 추가해야 하는데 구현이 좀 어려운 것 같습니다.
도움이 될만한 방법이나 자료가 있으면 알려주시면 감사하겠습니다.
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 관련)도 추가해야 하는데 구현이 좀 어려운 것 같습니다.
도움이 될만한 방법이나 자료가 있으면 알려주시면 감사하겠습니다.
댓글 4
-
- 소경철2002-01-25
- 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 관련)도 추가해야 하는데 구현이 좀 어려운 것 같습니다.
:
:도움이 될만한 방법이나 자료가 있으면 알려주시면 감사하겠습니다.
:
:
-
- 유환주2002-01-26
- :첫번째는 예제에는 IP 문제인데도 불구하고 branch & bound 를 하지 않고 root node에서 column generation을 이용하여 LP를 푼 다음 IloConversion을 사용하여 integer 값으로 변환하고 있습니다. IP를 풀기 위해서는 branch & bound를 써야 할 것 같은데(아마도 Goal을 사용?) 어떻게 해야 하는지 궁금합니다.
IloConversion(env, vars, ILOINT); 처럼 사용하면 vars는 모두 integer 변수로 형변환 됩니다. 따라서 이 이후에는 CPLEX에 정수변수를 부여한 것과 같으므로 기동이 되면 자동적으로 branch & bound가 동작 합니다.
:두번째는 예제에는 LP를 풀 때 column을 생성하기 위해 cplex를 사용하고 있는데 (즉, cplex 객체 두 개를 사용) 저는 column을 생성할 때 제약조건들이 linear하게 표현되지 않기 때문에 solver를 사용할려고 하는데 solver를 사용하여 최적화도 해야 하고 중간에 새로운 제약(reduced cost 관련)도 추가해야 하는데 구현이 좀 어려운 것 같습니다.
풀려고 하는 문제의 구조에 따라 약간씩 다르겠지만, 그러나 결국은 위의 예제와 같이 메인 문제의 풀이 결과로 부터 Dual Value를 가지고 와서 그것을 이용해서 Minimize 문제를 풀어서 Column을 생성하는 밥법 입니다.다만 CPLEX 대신에 Solver를 사용하여 비선형 제약을 추가하면 되겠죠.
문제에 따라서는 변수의 구조를 위의 논리에 맞도록 만들어 주는 것이 그리 간단한 문제는 아닙니다
건투를 빕니다.
-
- 비회원2023-12-19
- <a href=https://levitr.mom>cost of levitra at savon pharmacy</a> Such modifications include, for example, labels, methylation, substitution of one or more of the naturally occurring nucleotides with an analog, internucleotide modifications such as uncharged linkages e
-
- 비회원2024-07-23
- <a href=http://cialis.lat/discover-the-best-prices-for-cialis>buy cialis professional</a> It tells one of the most controversial stories in movie history; how and why Linda Lovelace got into the adult entertainment industry, and what she was forced to sacrifice for success
목록
확인