고객지원
기술문의
branch and bound에서 노드를 볼려면
- 김볽순
- 2002.05.26
- 조회수 2,040
branch and bound 문제에서
예문>>
max
obj: 77x1+6x2+3x3+6x4+33x5+13x6+110x7+21x8+47x9
st
774x1+76x2+22x3+42x4+21x5+760x6+818x7+62x8+785x9<=1500
67x1+27x2+794x3+53x4+234x5+32x6+797x7+97x8+435x9<=1500
binaries
x1 x2 x3 x4 x5 x6 x7 x8 x9
end
문제가 있을때, 이 문제를 CPLEX 돌리면...
다음과 같은 메시지가 나옵니다.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B Parent Depth
0 0 225.6895 2 225.6895 2
187.2174 1 Cuts: 5 4
* 176.0000 0 176.0000 Covers: 1 6
GUB cover cuts applied: 1
Cover cuts applied: 3
Gomory fractional cuts applied: 2
Integer optimal solution: Objective = 1.7600000000e+002
Solution time = 0.06 sec. Iterations = 6 Nodes = 0
여기에서 cut된 노드를 보기 위해,
set -> mip -> all 에서 variable strategy selection을 합니다.
하고 난후, 노드를 보려면 어떻게 해야 하는지 모르겠습니다.
또한, 지난번 말씀해 주신 reduced cost를 보기위해
display -> solution -> reduced를 입력해서 값을 확인했는데,
맞는지요?
아...한가지 더 알고싶습니다.
mps파일 (mixed integer programming)을 만드는 notation에 대해 알고 싶습니다.
cplex reference manual의 example.mps을 봤지만 내용을 잘 모르겠습니다.
한 가지 더...
cplex로 문제를 풀면 cplex.log에 결과가 저장되는데,
틀린 결과는 저장이 안되는 것 같습니다.
log 파일에 저장되는 내용의 기준이 무엇인지 알고 싶습니다.
감사합니다.
예문>>
max
obj: 77x1+6x2+3x3+6x4+33x5+13x6+110x7+21x8+47x9
st
774x1+76x2+22x3+42x4+21x5+760x6+818x7+62x8+785x9<=1500
67x1+27x2+794x3+53x4+234x5+32x6+797x7+97x8+435x9<=1500
binaries
x1 x2 x3 x4 x5 x6 x7 x8 x9
end
문제가 있을때, 이 문제를 CPLEX 돌리면...
다음과 같은 메시지가 나옵니다.
Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B Parent Depth
0 0 225.6895 2 225.6895 2
187.2174 1 Cuts: 5 4
* 176.0000 0 176.0000 Covers: 1 6
GUB cover cuts applied: 1
Cover cuts applied: 3
Gomory fractional cuts applied: 2
Integer optimal solution: Objective = 1.7600000000e+002
Solution time = 0.06 sec. Iterations = 6 Nodes = 0
여기에서 cut된 노드를 보기 위해,
set -> mip -> all 에서 variable strategy selection을 합니다.
하고 난후, 노드를 보려면 어떻게 해야 하는지 모르겠습니다.
또한, 지난번 말씀해 주신 reduced cost를 보기위해
display -> solution -> reduced를 입력해서 값을 확인했는데,
맞는지요?
아...한가지 더 알고싶습니다.
mps파일 (mixed integer programming)을 만드는 notation에 대해 알고 싶습니다.
cplex reference manual의 example.mps을 봤지만 내용을 잘 모르겠습니다.
한 가지 더...
cplex로 문제를 풀면 cplex.log에 결과가 저장되는데,
틀린 결과는 저장이 안되는 것 같습니다.
log 파일에 저장되는 내용의 기준이 무엇인지 알고 싶습니다.
감사합니다.
댓글 3
-
- 소경철2002-05-27
답변1) CPLEX에서는 B&B를 수행하기 전에 미리 제공된 다양한 CUT을 이용해 Pre-Processing을 합니다. 이 과정은 B&B의 Root Node에서 수행되는 것이구요. 따라서 CUT된 노드라는 것은 없습니다. 그렇기 때문에 CUT된 노드를 본다는 것은 불가능하겠죠..
참고로, 이 예제에서는 단지 CUT을 수행하는 과정만으로 정수해를 구했으며, 그 해가 최적해이기 때문에 더이상 B&B를 수행하지 않고 CPLEX가 종료되었습니다.
이처럼 문제의 형태에 따라서 CUT을 수행하는 것만으로도 최적해를 구하는 경우가 있게 되는거죠.
:또한, 지난번 말씀해 주신 reduced cost를 보기위해
:display -> solution -> reduced를 입력해서 값을 확인했는데,
:맞는지요?
:
답변2) Interactive Optimizer를 사용하고 계시는것 같군요. 저희는 C++을 사용한 Concert Technology를 사용하시기를 권장합니다.
Interactive Optimizer에서 Reduced Cost를 가져오는 과정은 display -> solution -> reduced가 맞습니다.
그리고, Conceret Technology를 사용하신다면, getReducedCost() 함수를 이용하시면 됩니다.
:아...한가지 더 알고싶습니다.
:mps파일 (mixed integer programming)을 만드는 notation에 대해 알고 싶습니다.
:
:cplex reference manual의 example.mps을 봤지만 내용을 잘 모르겠습니다.
:
답변3) mps 파일은 CPLEX에서 자체적으로 정의한 파일 형식이 아니라, LP 파일과 같이 최적화 모델을 표현하는 일반적인 파일 형식입니다. 따라서, mps 파일을 만드는 방법에 대해서는 다른 참고서적을 이용하시기 바랍니다.
:한 가지 더...
:cplex로 문제를 풀면 cplex.log에 결과가 저장되는데,
:틀린 결과는 저장이 안되는 것 같습니다.
:log 파일에 저장되는 내용의 기준이 무엇인지 알고 싶습니다.
:
답변4) cplex.log 파일에는 CPLEX를 수행할 때 알고리즘이 수행되는 과정을 모두 기록합니다. 당연히 제대로 수행이 되는 경우만 기록이 되겠죠. (Infeasible Solution이거나 Unbounded Solution인 경우에도 기록됩니다.)
그런데, CPLEX의 parameter를 이용하여 출력하는 정보의 종류를 제어했다면, cplex.log 파일에는 제어한 내용에 따라 더 많은 정보가 출력됩니다.
예) set-> mip -> display에서 다른 값을 설정해 주었다면, 그 설정 상태에 따라 파일에 기록이 됩니다.
감사합니다.
-
- 김복순2002-05-27
- optimizer인것 같은데,
concert Technology가 어떤 것인지 알고 싶어, 제품정보를 봤습니다.
concert technology가 없던데....
CPLEX 내부에 포함된 것인가요??
그리고...
10개 노드를 가진 full mesh형의 tsp를 풀어봤더니...
node가 생성이 되었습니다.
이는 b&b를 했다는 말인것 같은데..
node를 볼 수 있나요?
-
- 소경철2002-05-27
:optimizer인것 같은데,
:concert Technology가 어떤 것인지 알고 싶어, 제품정보를 봤습니다.
:concert technology가 없던데....
:CPLEX 내부에 포함된 것인가요??
답변) 네.. 그렇습니다. Concert Technology는 따로 제품형태로 있는 것이 아니라, CPLEX와 함께 라이브러리 형태로 CPLEX 7.x 부터 함께 제공되고 있습니다.
이전 버전까지는 CPLEX를 사용하기 위해서는 C언어를 사용한 Callable Library를 이용하였지만, 7.x 부터는 Concert Technology를 이용한 C++ 구현이 가능하게 되었습니다.
또한, 이 Concert Technology는 LP 구현시 모델 영역과 엔진 영역을 따로 구분하여 프로그래밍할 수 있도록 해주고 있습니다.
Concert Technology의 사용법에 대해 더 자세히 알고 싶으시면, 저희 회사에서 진행하고 있는 CPLEX 정기 교육을 받아보시기 바랍니다.
:10개 노드를 가진 full mesh형의 tsp를 풀어봤더니...
:node가 생성이 되었습니다.
:이는 b&b를 했다는 말인것 같은데..
:node를 볼 수 있나요?
답변) 물론 MIP 모델로 구현한 것이겠죠?
CPLEX 실행시 B&B가 구동되었다면, 화면에 진행 과정이 출력될 것입니다.
출력 화면을 보면, 제일 앞에 현재 Node 번호가 나올 것입니다. CPLEX는 기본적으로 interval을 100으로 설정되어 있기 때문에, 100개의 Node마다 한번씩 출력을 합니다.
그런데, 모든 Node에 대해서 정보를 보고 싶으시다면, 이 설정을 1로 바꿔주시면 됩니다.
(set -> mip -> interval 에서 값을 1로 주시면 됩니다.)
질문하신 모든 내용은 ILOG Concert Technology와 ILOG CPLEX Manual에 자세히 설명되어 있으니 참고하시기 바랍니다.
목록
확인