|
|
제 목 |
순수 LP 문제의 변수 갯수와 풀이속도와의 관계 |
|
작성자 |
소경철 |
작성일 |
2002-02-20 |
조회수 |
1892 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
일단 결론부터 말씀드리겠습니다.
저희가 주로 다루는 문제는 이런 순수 LP문제가 아니라 대부분 MIP문제이기 때문에 단정지을 수는 없지만 이 정도의 제약만 있는 문제라면 변수의 개수가 이렇게 많더라도 풀이시간이 몇시간씩 걸리지는 않을 것 같군요.
저희가 접해본 문제 중에서, 정수변수를 포함하여 2만개 정도되는 MIP 문제의 경우(물론 제약은 매우 복잡하고 많았습니다.)에도 해를 구하는데 걸리는 시간은 평균 10분 정도 소요되었습니다.
물론 데이터에 따라서 정수해를 구하기 위해 B&B 하는 시간이 꽤 많이 걸리는 경우도 발생하구요.
만약 정수 변수가 없는 순수 LP 문제였다면 결과를 도출하는데 걸리는 시간은 5분 이내였겠죠..
만약, 실제 데이터를 저희에게 보내주실 수 있으시다면, 저희가 풀이시간을 알려드릴 수도 있습니다.
감사합니다.
:kimkeesung님의 글입니다.
:첫 질문에 말했듯이 순수 LP 문제입니다.
:IP나 MIP아닙니다.
:모델은
:min sigma(j = 0 to m) p * yj
:s.t sigma(i=0 to n) v* xi - yj <= K j=0 to m
:
: sigma(i=0 to n)b* xi = bi
: xi< ui i = o to n
:
:입니다...-.-
:게시판이라 수식 적기가 쉽지 않네요.
:결정변수는 yj 가 m개, xi가 n개 입니다.
:
:보시다시피, 간단한 LP문제입니다.
:총 결정변수가 m + n인데, 5만개~7만개 정도됩니다.
:
:LP라서 그다지 오래 걸릴꺼 같지는 않고,
:cplex 7.0이 상당히 빨라졌다고 하니깐,
:몇 시간 안에 풀지 않을까 싶은데....
:이 정도 사이즈 문제를 풀어보신 경험이 있으시면
:답변주세요....
:
:미리 감사합니다.
:
:
:
:
::조한민님의 글입니다.
:
:::kimkeesung님의 글입니다.
::
:::
:::cplex로 풀 수 있는 LP의 변수 개수는 몇 개인가요?
:::
:::7~8만개의 결정변수를 가지는 모델을
:::concert를 이용해서 코딩해서 풀때,
:::실행 시간은 얼마나 걸리나요?
:::경험상으로 몇시간정도일꺼라는 정도가 있을 꺼 같은데..
:::알려주세요...
:::
:::
:::
:::
::안녕하십니까.
::
::같은 LP 문제여도 각 변수들이 정수형 변수인지(IP)
::실수형 변수인지에 따라 문제 푸는 시간이 현저하게 달라지고
::LP 문제중에서도 모델에 따라 pre-solve 과정에서
::대부분의 변수 값이 정해져 버리는경우
::시간이 예상보다 짧아 질수 있습니다.
::
::어떠한 문제인지 예를 들어 주시면 좀더 정확한
::답변을 해 드릴수 있겠지만
::문제를 풀기위한 코딩도 제약의 종류나 제약이 포함하는
::변수의 패턴에 따라 개발시간이 달라집니다.
::
::어떤 종류의 문제를 푸실것인지 예를 들어 주시면
::좀더 자세한 답변해 드리겠습니다.
::
::수고하십시오.
::
:: |
|
|
|
