고객지원
기술문의
MIP 시간이 너무 오래 걸리는데..
- 김동근
- 2002.10.29
- 조회수 1,753
지난 번 0에 가까운 수에 대한 답변에 대해 우선 감사드리고요..
같은 문제인데.. 결정변수가 총 900개이며, 제약식은 960개인, MIP 문제입니다.
그런데, Branch & Bound을 통해 값을 구하면, 최소 2시간, 오래 걸릴 때는 하루가 지나도 답이 안 나옵니다.
(컴은 pen-4 1G, 256mb에 최고 사양인데..)
Branch & Bound에서 옵션을 binary로 하나, integer로 하나, 걸리는 시간은 별 차이가 없네요. 흑.
어떤 문제 때문인지..
아니면.. Branch & bound에서 어떤 옵션을 통해서 시간을 줄일 수 있을지..
아니면.. x = 0 or 1 제약식을 다른 식으로 relax 시켜야할지..
그럼.. 답변 부탁드립니다..
같은 문제인데.. 결정변수가 총 900개이며, 제약식은 960개인, MIP 문제입니다.
그런데, Branch & Bound을 통해 값을 구하면, 최소 2시간, 오래 걸릴 때는 하루가 지나도 답이 안 나옵니다.
(컴은 pen-4 1G, 256mb에 최고 사양인데..)
Branch & Bound에서 옵션을 binary로 하나, integer로 하나, 걸리는 시간은 별 차이가 없네요. 흑.
어떤 문제 때문인지..
아니면.. Branch & bound에서 어떤 옵션을 통해서 시간을 줄일 수 있을지..
아니면.. x = 0 or 1 제약식을 다른 식으로 relax 시켜야할지..
그럼.. 답변 부탁드립니다..
댓글 1
-
- 소경철2002-10-30
MIP 문제의 풀이 속도는 절대적이지는 않지만, 일반적으로 모델의 구조나 정수형 변수의 개수에 많이 좌우됩니다.
(문제 구조를 약간만 변형시키거나, 정수형 변수가 약간만 줄어들어도 풀이 속도가 굉장히 개선되는 경우도 많이 있습니다.)
그리고, Branch & Bound에서 옵션을 binary로 하나, integer로 하나 걸리는 시간에는 별로 영향을 주지 않구요..^^
ILOG CPLEX에서는 이 경우에, 여러가지 Parameter를 이용하여, 문제 구조에 맞는 탐색 방법을 설정해 줄 수가 있습니다.
(MIPEmphasis, NodeSel, VarSel, BrDir, Probe, DiveType 등 매우 많은 Parameter가 있음)
Parameter에 대한 자세한 설명은 CPLEX Reference Manual에 나와 있습니다.
문제 구조에 맞는 절적한 Parameter를 사용해 보시거나, 결정변수를 정수형 변수에서 실수형 변수로 변환 가능한지 알아보시는 것도 좋겠네요..
목록
확인