|
|
제 목 |
B&B의 변수 선택 전략 |
|
작성자 |
소경철 |
작성일 |
2002-05-24 |
조회수 |
1191 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
B&B 진행을 위한 변수 선택 전략을 조정하기 위해 IloCplex 객체의 VarSel이라는 함수를 사용합니다.
이 때, 선택 전략으로 총 5가지를 제공하고 있으며, 이 전략들에 대한 설명은 Reference Manual에 있습니다.
Manaul에 설명되어 있는 부분은 다음과 같습니다.
============================================================
CPX_PARAM_VARSEL / IloCplex::VarSel
MIP STRATEGY VARIABLESELECT
-1 [CPX_VARSEL_MININFEAS] Branch on variable with minimum infeasibility
0 [CPX_VARSEL_DEFAULT] Branch variable automatically selected
1 [CPX_VARSEL_MAXINFEAS] Branch on variable with maximum infeasibility
2 [CPX_VARSEL_PSEUDO] Branch based on pseudo costs
3 [CPX_VARSEL_STRONG] Strong branching
4 [CPX_VARSEL_PSEUDOREDUCED] Branch based on pseudo reduced costs
Default: 0
Description: MIP variable selection strategy.
Used to set the rule for selecting the branching variable at the node which has been selected for branching. The maximum infeasibility rule chooses the variable with the largest fractional value; the minimum infeasibility rule chooses the variable with the smallest fractional value. The minimum infeasibility rule (-1) may lead more quickly to a first integer feasible solution, but is usually slower overall to reach the optimal integer solution. The maximum infeasibility rule (1) forces larger changes earlier in the tree, which tend to produce faster overall times to reach the optimal integer solution. Pseudo cost (2) variable selection is derived from pseudo-shadow prices. Strong branching (3) causes variable selection based on partially solving a number of subproblems with tentative branches to see which branch is the most promising. This strategy can be effective on large, difficult MIP problems. Pseudo reduced costs (4) are a computationally less-intensive form of pseudo costs. The default value (0) allows CPLEX to select the best rule based on the problem and its progress.
:김볽순님의 글입니다.
:안녕하세요..
:
:대학원에서 정수 계획법을 배우고 있는 학생입니다.
:
:며칠전에 branch and bound를 배우면서,
:
:교수님께서 MIP Strategy variable select의 5가지
:( -1: branch on variable with minimum infeasibility,
: 0: branch variable automatically selected,
: 1: branch on variable with maxmimum infeasibility,
: 2:branch based on pseudo costs,
: 3: strong branching,
: 4: branch based on pseudo reduced costs
:)를 배웠습니다.
:
:그중 다 섯번째인 pseudo reduced cost가 무슨 의미인지 알아오라고 하셨고, cplex로 테스트도 해보라고 하셨는데, 어떤 자료를 봐야 할 지 모르겠습니다.
:
:어떤 예문을 돌려야하고, 무엇을 봐야하는지..
:혹은 어떤 의미인지 설명부탁드립니다.
:
:또한 LP에서의 pseudo reduced cost를 알아보라고 하셨는데, 이도 무슨 의미인지 이해가 안됩니다. |
|
|
|
