고객지원
기술문의
Cplex stopping rule (MIP에서)
- 권성화
- 2003.02.15
- 조회수 1,527
cplex로 작업을 하던 중 다음과 같은 로그를 얻었습니다.
문제의 형식은 MIP입니다.
-------------------------------------------------------
Tried aggregator 2 times.
MIP Presolve eliminated 903 rows and 804 columns.
MIP Presolve modified 2698 coefficients.
Aggregator did 29 substitutions.
Reduced MIP has 700 rows, 4541 columns, and 40531 nonzeros.
Presolve time = 0.29 sec.
Clique table members: 2
MIP emphasis: optimality
Root relaxation solution time = 0.16 sec.
Objective is integral.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B Parent Depth
0 0 1181.0000 52 1181.0000 819
1181.0000 22 Fractcuts: 46 875
* 0+ 0 1183.0000 0 1183.0000 1181.0000 875 0.17%
Gomory fractional cuts applied: 2
-----------------------------------------------------------------
위의 문제에서 objective는 min으로 한 것입니다.
보는 것 처럼, objective값이 1183에서 멈추었습니다.
(cplex.getStatus에서, IloAlgorithm::Optimal로 나왔습니다.)
그런데, Gap을 보면 0.17%입니다.
(best integer:1183, best node:1181이므로, 이 둘의 gap이 0.17%
입니다.)
겉으로 보기엔, 이 값이 충분히 작아서 cplex가 stop을 한 것 같습니다.
그런데, IloCplex::EpGap 의 디폴트 값은 1e-4로 되어있더군요.
Gap이 0.17%이면, 1e-4보다 큰 값이라서, 이 때문에 stop한 것 같지
않습니다.
그러면, 위의 문제는 왜 멈추었는 지 궁금합니다.
즉, 어떤 stopping rule 때문에, 1183에서 멈추었는 지를 알고 싶습니다.
다른 방법으로 알아본 결과, 위 문제의 최소값은 1181이었습니다.
1181을 얻으려면 어떻게 하면 좋을 지도 알려주시면 감사하겠습니다.
문제의 형식은 MIP입니다.
-------------------------------------------------------
Tried aggregator 2 times.
MIP Presolve eliminated 903 rows and 804 columns.
MIP Presolve modified 2698 coefficients.
Aggregator did 29 substitutions.
Reduced MIP has 700 rows, 4541 columns, and 40531 nonzeros.
Presolve time = 0.29 sec.
Clique table members: 2
MIP emphasis: optimality
Root relaxation solution time = 0.16 sec.
Objective is integral.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B Parent Depth
0 0 1181.0000 52 1181.0000 819
1181.0000 22 Fractcuts: 46 875
* 0+ 0 1183.0000 0 1183.0000 1181.0000 875 0.17%
Gomory fractional cuts applied: 2
-----------------------------------------------------------------
위의 문제에서 objective는 min으로 한 것입니다.
보는 것 처럼, objective값이 1183에서 멈추었습니다.
(cplex.getStatus에서, IloAlgorithm::Optimal로 나왔습니다.)
그런데, Gap을 보면 0.17%입니다.
(best integer:1183, best node:1181이므로, 이 둘의 gap이 0.17%
입니다.)
겉으로 보기엔, 이 값이 충분히 작아서 cplex가 stop을 한 것 같습니다.
그런데, IloCplex::EpGap 의 디폴트 값은 1e-4로 되어있더군요.
Gap이 0.17%이면, 1e-4보다 큰 값이라서, 이 때문에 stop한 것 같지
않습니다.
그러면, 위의 문제는 왜 멈추었는 지 궁금합니다.
즉, 어떤 stopping rule 때문에, 1183에서 멈추었는 지를 알고 싶습니다.
다른 방법으로 알아본 결과, 위 문제의 최소값은 1181이었습니다.
1181을 얻으려면 어떻게 하면 좋을 지도 알려주시면 감사하겠습니다.
댓글 2
-
- 권성화2003-02-15
- 제가 쓴 글에 좀 잘못된 점이 있어서 수정하려고 하니,
수정이 안되는 군요.
그래서, 답글로 수정합니다.
제가, 위의 질문에서, 다른 방법으로 알아본 결과 최소값이 1181이라고
했는데, 그게 아니더군요.
다른 방법으로해도 최소값은 여전히 1181이었습니다.
제가 다른 값과 혼동을 했습니다.
위의 글에서 마지막 2줄은 무시해 주세요.
stopping rule에 대해서만 알려주시면 감사하겠습니다.
그리고, 첨가하여 하나만 더 질문하겠습니다.
위의 로그를 보면, gap이 0.17%까지만 출력되었는데,
실제로 gap 0.17%인 것인지 아니면,
0.00%인데 출력만 안된건 지 궁금합니다.
-
- 소경철2003-02-17
답변이 늦어서 죄송합니다.
이 문제에서 GAP이 0.17%인 상태에서 종료를 한 것은 CPLEX Parameter 들 중 어느 하나의 기준에 걸렸기 때문입니다.
(모든 Parameter들은 기본값을 가지고 반영되어 있습니다.)
따라서, 종료 원인이 여기서 질문하신 IloCplex::EpGap Parameter에 의해서일수도 있고, 다른 Parameter에 의해서일 수도 있습니다.
(CPLEX는 매우 많은 Parameter를 가지고 있으며, 자체적으로 각 Parameter들의 기본값이 설정되어 종료 조건을 만들고 있습니다. 따라서, MIP이 종료하는 경우, 어떤 기준에 의해서인가를 알아내는 것은 매우 어렵습니다.)
...
그리고, IloCplex::EpGap Parameter의 기본값 1e-4은 현재까지의 Best Integer 값과, 아직 탐색하지 않고 남아있는 Node 중에서 가장 Best인 Node의 값과의 Gap을 말합니다.
이미 찾은 Best Node의 값이 아니라는 거죠... (이 부분에서 착오가 있으신 것 같네요...^^)
요약해보면, 이미 찾은 Best Node값: 1183, 현재까지의 Best Integer 값: 1181, 아직 탐색하지 않고 남아있는 Node 중에서 가장 Best인 Node의 값: 알 수 없음...
따라서, 만약 이 Parameter에 의해 종료된 것이라면, 현재 남아있는 Node 중에서 Best인 값과 현재까지의 Best Integer 값과의 차이가 1e-4보다 작기 때문에 MIP이 종료한 것입니다.
도움이 되셨기를 바랍니다.
목록
확인