고객지원
기술문의
결정변수 앞에 붙는 파라미터 관련 질문
- 권순욱
- 2009.08.24
- 조회수 2,350
안녕하세요.
요즘 이 게시판을 저만 이용하는거 같아서 조금 멋쩍긴하네요.
오늘 드릴 질문은 수리식 상에서 결정변수 앞에 붙는
파라미터에 관련된 내용입니다.
현재 item과 period에 따라 결정변수의 수가 결정되는 MIP 수리식 하나를 풀고 있습니다.
타 논문에서는 CPLEX를 사용해서 똑같은 수리식에 5X5짜리 문제를 푸는데 평균 0.5초안에 해결했다고 나오는데요 제가 풀었을때는 200초 이상이 걸리더라구요.
(더 큰사이즈 문제는 시간 차이가 훨씬 더 나구요. 심지어 타 논문에서는 5초안에 해결 했다는 7X7 같은 경우는 한참돌아가다가 메모리 부족이라고 뜨기도 하더군요.)
같은 사이즈(정수변수의 개수, 제약식의 수 등이 동일)의 문제인데 시간 차이가 너무커서 원인이 뭘까 생각해봤습니다.
1. 타 논문에서는 혹시 LP파일이나 OPL로 구현하고 저는 concert를 이용한 C++로 실행시켜서? (근데 이건 솔루션 타임을 구하는 범위를 CPLEX가 모델을 받아서 푸는 부분으로만 설정했기 때문에 아닌듯 하네요)
2. 메모리 설정이나 화면에 문제푸는 과정을 보여주는 시간 때문에?
이건 코드 상에 다음의 것들을 포함해봤지만, 변화가 없었습니다.
cplex.setParam(IloCplex::WorkMem,1024);
cplex.setParam(IloCplex::MemoryEmphasis,1);
cplex.setParam(IloCplex::SimDisplay, 0);
cplex.setParam(IloCplex::MIPDisplay, 0);
3. 타 논문에서는 결정변수 앞에 붙는 파라미터가 모두 정수인 반면에 제가 푸는 문제에서는 파라미터에 소숫점 이하 네다섯자리까지 존재하는 실수값들이 많아서?
세 번째 이유 같은 경우에, 제가 임의로 파라미터를 모두 정수로 바꿔봤는데 원래 200초 이상에서 80초대로 줄긴 했습니다. 0.5초대는 어림도 없었구요.
제가 지금까지 알기론 MIP문제를 해결하는데 걸리는 시간은 정수변수의 개수나 제약식의 개수에 dependent 한걸로 알고 있는데 결정변수 앞에 붙는 파라미터가 정수냐 실수냐에 따라서도 큰 영향을 받는지 궁금합니다.(CUT 같은 걸 생성하고 넣는데 영향을 주는거 같기도 하구요.)
혹시 추정가는 원인이 있으시다면 조언 부탁드립니다.
제가 풀어야 될 문제가 훨씬 더 큰 문제도 많은데
예상치도 못했던 5X5 사이즈 부터 문제가 생겨서 당황스럽네요.
요즘 이 게시판을 저만 이용하는거 같아서 조금 멋쩍긴하네요.
오늘 드릴 질문은 수리식 상에서 결정변수 앞에 붙는
파라미터에 관련된 내용입니다.
현재 item과 period에 따라 결정변수의 수가 결정되는 MIP 수리식 하나를 풀고 있습니다.
타 논문에서는 CPLEX를 사용해서 똑같은 수리식에 5X5짜리 문제를 푸는데 평균 0.5초안에 해결했다고 나오는데요 제가 풀었을때는 200초 이상이 걸리더라구요.
(더 큰사이즈 문제는 시간 차이가 훨씬 더 나구요. 심지어 타 논문에서는 5초안에 해결 했다는 7X7 같은 경우는 한참돌아가다가 메모리 부족이라고 뜨기도 하더군요.)
같은 사이즈(정수변수의 개수, 제약식의 수 등이 동일)의 문제인데 시간 차이가 너무커서 원인이 뭘까 생각해봤습니다.
1. 타 논문에서는 혹시 LP파일이나 OPL로 구현하고 저는 concert를 이용한 C++로 실행시켜서? (근데 이건 솔루션 타임을 구하는 범위를 CPLEX가 모델을 받아서 푸는 부분으로만 설정했기 때문에 아닌듯 하네요)
2. 메모리 설정이나 화면에 문제푸는 과정을 보여주는 시간 때문에?
이건 코드 상에 다음의 것들을 포함해봤지만, 변화가 없었습니다.
cplex.setParam(IloCplex::WorkMem,1024);
cplex.setParam(IloCplex::MemoryEmphasis,1);
cplex.setParam(IloCplex::SimDisplay, 0);
cplex.setParam(IloCplex::MIPDisplay, 0);
3. 타 논문에서는 결정변수 앞에 붙는 파라미터가 모두 정수인 반면에 제가 푸는 문제에서는 파라미터에 소숫점 이하 네다섯자리까지 존재하는 실수값들이 많아서?
세 번째 이유 같은 경우에, 제가 임의로 파라미터를 모두 정수로 바꿔봤는데 원래 200초 이상에서 80초대로 줄긴 했습니다. 0.5초대는 어림도 없었구요.
제가 지금까지 알기론 MIP문제를 해결하는데 걸리는 시간은 정수변수의 개수나 제약식의 개수에 dependent 한걸로 알고 있는데 결정변수 앞에 붙는 파라미터가 정수냐 실수냐에 따라서도 큰 영향을 받는지 궁금합니다.(CUT 같은 걸 생성하고 넣는데 영향을 주는거 같기도 하구요.)
혹시 추정가는 원인이 있으시다면 조언 부탁드립니다.
제가 풀어야 될 문제가 훨씬 더 큰 문제도 많은데
예상치도 못했던 5X5 사이즈 부터 문제가 생겨서 당황스럽네요.
댓글 5
-
- 이보헌2009-08-25
- 안녕하세요 ^^
위에 말씀하신 1,2,3번 모두 영향을 줄 수도 있지만 큰 영향력이 있는 부분은 아닙니다.
display level에 따라
풀이 시간이 오래 걸리는 가장 큰 이유는 모델링에 있는 것 같습니다.
모델링 형태에 따라 탐색 영역이 크다면 시간이 오래 걸릴수가 있습니다.
소스를 보내 주셔서 저희가 검토해 보는것이 가장 정확하겠지만,
일단
MemoryEmphasis 를 사용하지 않음(0) 으로 설정하시고
변수의 min, max 를 feasible 한 영역안에서 최소화 해보시기 바랍니다.
-
- 권순욱2009-08-27
- 답변 주셔서 감사합니다.
말씀해주신 부분을 적용해서
변수의 Bound도 줄여보고 했더니 풀이시간이 어느정도 준거 같습니다.
근데 똑 같은 범위 내에서 랜덤하게 generate한 10개의 파일중
유독 풀이시간이 비상식적으로 오래 걸리는게 있습니다.
Problem1: 0.109375 sec
Problem2: 0.0625 sec
Problem3: 0.609375 sec
Problem4: 0.03125 sec
Problem5: 2728.69 sec
Problem6: 0.390625 sec
Problem7: 8.26563 sec
Problem8; 3.79688 sec
Problem9; 6.07813 sec
Problem10: 0.03125 sec
대부분의 문제가 1초도 안되서 풀리는 반면 Problem5 같은 경우는 2000초 이상이 걸리더군요. 문제 7,8,9의 8초, 3초, 6초도 왜 오래걸렸을까 고민해야 될 상황에 2000초 이상이 나온건
도무지 이유를 모르겠네요.
제가 풀고 있는 여러 사이즈 조합의 각각의 10개의 문제 중
저런 문제가 꼭 몇 개씩 생기더라구요.
위에 Problem5가 2000초가 넘게 나왔던 7X7 사이즈의 경우를
파일에 첨부하였습니다.(10개의 data 파일 중, 5번만 2000초가 넘네요. 7,8,9번도 time 측면에서 일관성은 없는거 같구요;;;)
한번 검토해주시면 감사하겠습니다.
-
- 이보헌2009-08-31
- 안녕하세요.
급한 업무로 인해 이제서야 답변을 드리게 되었네요.
5번 문제의 경우 해를 개선 시키기 위해 오랜시간 풀이되는 모습을 볼 수 있는데요.
로그를 확인해 본 결과 T변수의 bound를 결정해 주지 못하고 계속해서 풀이가 되는것으로 확인되었습니다.
목적함수에서 T변수에 대하여 priod에 따라 가중치를 높여 주었습니다.
일단, 원래 문제 데이터가 풀이하기 어려운 형태인것으로 보입니다.
Symmetry를 없애는 방법을 사용하여 풀이 시간을 단축할 수 있습니다 .
예전에 사용자 메뉴얼에서 Symmetry 관련하여 이러한 내용이 있었는데 지금은 메뉴얼에서 못찾겠네요... ^^;;
Symmetry 에 대해 간단히 설명을 드리면,
t가 1일때 T[t]가 1 증가할때와 t가 2일때 T[t]가 1 증가할때 목적값의 변화가 미미하여 T값을 bound 하지 못하고 T[t]의 값을 계속 변경 시키면서 풀이를 진행하게 되는데
이때, T[t]에 대하여 서로 간섭하지 않도록 가중치를 주어 풀이시간을 단축 할 수 있습니다.
첨부파일을 보시면
총 풀이시간이 15초 걸렸는데... 이정도로 만족이 되실지 모르겠네요.
T변수를 빨리 bound 해 줄수 있는 다양한 시도를 해 보시기 바랍니다.
-
- 권순욱2009-08-31
- 답변 감사합니다.
정말 이번 문제를 풀어보면서 여러가지를 알게되는거 같습니다.
바쁘실텐데 많은 도움 주셔서 정말 감사합니다.
답변해주신데로, Ilopower(10,t) 를 이용하니깐
Solution Time은 확실히 줄어드는 데요,
목적함수가 달라져서, 전혀 다른 답을 구해내게 된다는게
문제가 되네요.
Ilopower(10,t) 란게 밑이 10이고 t가 지수인거 같은데
목적함수에 새로운 값이 곱해져서, Solution이 그에따라 바뀌고 목적함수 값도 엄청나게 큰 값을 구해주더라구요.
수리식이 안바뀌면서 T변수의 Bound를 조정하는 방법은 없을까요?
어떻게 해결해야 될지 정말 감이 안잡힙니다.ㅜ
ps. 제가 C코드 상의 루프를 이용해서 데이터 파일을 한꺼번에
Generate를 하는데, 유독 한 두개만 저런게 생기네요. 여러 사이즈 조합의 10개의 문제들중 대체로 5번 문제의 데이터 파일이 신기할 정도로 오래걸리고 나머지 문제는 또 빨리 풀리는 등 알 수 없는 문제가 저를 괴롭히는군요.
통상 데이터에 따라 풀이시간에 당연히 차이가 있을 수는 있는데 같은 사이즈인데도 불구하고 1000배 이상의 시간이 더 걸리는 점은 원인을 추측하기가 힘듭니다. ㅠ
-
- 이보헌2009-09-07
- 안녕하세요.
갑작스런 비에 분주하던 마음도 가라앉는거 같네요.
요즘들어 왜 이리 마음만 바쁜지 모르겠네요. ^^
여러가지 데이터를 적용하다보면 문제 풀이 속도가 달라지는 경우가 많이 있지만, 현재와 같은 풀이 속도가 현저하게 차이나는것은 앞에서 말씀드린 symmetry 때문으로 보입니다.
Objective Value가 2104 정도의 정수해를 5초이내에 찾았지만 이미 그것이 Optimal이었더라도 cplex내에 default로 정의된 0.0001의 값을 개선할 수있는 해를 찾기위해 feasible 영역을 계속 탐색하게 됩니다.
내부적으로 이미 찾은 해보다 좋은 결과가 나오지 않는 탐색영역은 자동으로 제거하지만 데이터에 따라서 탐색영역이 많이 남아있는 경우에, 그리고 비슷한/또는 동일한 Objective Value를 갖는 해가 많을경우 이 문제와 같이 해의 개선없이 많은 시간을 소비할 수 있습니다.
setPriority라는 함수 또는 VarSel등의 파라미터를 사용해 변수의 bound를 유도해 줄수 있으나, 초기에 정수해를 찾을수 있게는 해 주지만 궁극적으로 풀이가 종료되는 시간은 크게 영향을 주지 않습니다.
해의개선이 없는 iteration을 줄여주기 위해 EpGap 또는 ObjDif등의 파라미터를 사용해 일정한 영역내의 해를 찾으면 종료해 줄수 있지만, 최적해를 찾고자 하는 목적과 멀어질 수 있습니다.
Objective 또는 Constraint의 변경없이 파라미터 만으로 풀이에 영향을 주는것은 그 효과에 많은 제약이 있습니다.
파라미터에 따라 일정한 경우 풀이시간을 단축시켜 줄 수있지만, 데이터 형태등에 따라 일반적으로 적용된다고 할 수 없기때문에 ,
문제풀이에 있어 발생하는 문제를 해결하는데에 가장먼저 시도해야할 방법이 수식을 변경하는 것입니다.
Objective Value를 의미있는 값으로 만들어주는 것도 좋지만 궁극적으로 찾고자 하는 값은 결정변수이기 때문에 Objective Value에 너무 큰 의미를 두지 않는것이 좋습니다.
또한,
정수형 변수라 할지라도 내부적으로 선형문제로 변경하여 풀이하기 때문에 == 과 같은 제약은 많은 시간을 소모하게 됩니다.
모델링 단계에서 == 제약보다는 >=, <= 제약을 사용하여 목적함수에서 해당변수가 수렴해 갈 수있도록 유도해 주는것이 좋습니다.
목록
확인