|
|
제 목 |
대안최적정수해를 찾는 경우입니다. |
|
작성자 |
소경철 |
작성일 |
2002-01-09 |
조회수 |
1566 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
MIP solve 시에 사용되는 B&B는 초기 LP 해와의 Gap을 줄여나가는 방법으로 탐색을 계속하게 됩니다. 이 과정에서 발견된 정수해를 계속 업데이트 하면서, 새로 찾은 정수해가 이미 찾은 정수해와 같거나 더 좋아지는 경우에 업데이트를 하게 되는거죠... 따라서, 이 경우 19라는 값보다 더 나은 값이 없지만, 동일한 값을 갖는 경우도 있기 때문에 계속 탐색을 하게 되는거죠..
그리고, ILOG CPLEX에는 B&B의 탐색을 중간에 멈추게 하는 Parameter가 여러가지 존재합니다. (CPLEX의 Reference Manual의 부록 A를 보시면 자세하게 나와 있습니다.)
이 경우에 적용할 수 있는 것으로는, CutUp/CutLo, ObjULim/ObjLLim 등이 적당할 것 같네요...
도움이 되셨기를 바랍니다.
:황준하님의 글입니다.
:순정수계획법(pure integer programming) 문제를 CPLEX 7.0을 사용하여
:풀고자 합니다.
:문제는 최소화 문제이므로 LP Relaxation을 통한 하한값이 18.3722라면 정수해의 값이 19가 될 때 최적이 되면 더 이상의 탐색은 불필요하게 됩니다.
:그런데 아래 실행 결과와 같이 19의 값을 갖는 정수해를 찾은 후에도 계혹해서 탐색을 진행하고 있습니다(Tab이 제대로 표시가 되지 않아 알아보기 힘들 수도 있지만 ...). 최적의 정수해를 찾은 후 탐색을 멈추게 하는 다른 방법이 있는지, 아니면 프로그램 내에 또 다른 bug가 존재할 수 있는지 알고 싶습니다.
:
:-------------------------------------------------------------------
:
:MIP emphasis: optimality
:Root relaxation solution time = 4.49 sec.
:
: Nodes Cuts/
: Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B Parent Depth
:
: 0 0 18.3325 379 18.3325 2655
: 18.4848 386 Fractcuts: 47 3197
: 18.5266 376 Fractcuts: 11 3479
:* 0+ 0 19.0000 0 19.0000 18.5266 3479 2.49%
: 5 5 18.5758 363 19.0000 18.5283 4153 2.48% id16 D 4 5
: 10 10 18.5927 370 19.0000 18.5283 4544 2.48% id528 U 9 10
: 15 15 18.5964 366 19.0000 18.5283 4662 2.48%
:
:---- 중간 생략 ---
:
: 235 10 cutoff 19.0000 18.7975 18887 1.07% id327 U 120 121
: 240 5 cutoff 19.0000 18.8909 18923 0.57% id509 U 132 133
:
:Gomory fractional cuts applied: 3
:Solution status = Optimal
:Solution value = 19.000000
:
:------------------------------------------------------------------- |
|
|
|
