고객지원
기술문의
pseudo reduced cost에 관하여
- 김복순
- 2002.05.24
- 조회수 1,874
안녕하세요..
대학원에서 정수 계획법을 배우고 있는 학생입니다.
며칠전에 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를 알아보라고 하셨는데, 이도 무슨 의미인지 이해가 안됩니다.
대학원에서 정수 계획법을 배우고 있는 학생입니다.
며칠전에 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를 알아보라고 하셨는데, 이도 무슨 의미인지 이해가 안됩니다.
댓글 4
-
- 소경철2002-05-24
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를 알아보라고 하셨는데, 이도 무슨 의미인지 이해가 안됩니다.
-
- 김태현2002-05-24
- Pseudo cost는 변수가 목적함수에 기여하는 정도를 평가하는 것입니다.
간단한 예를 설명을 드리면,
minimization problem에서
relax된 optimal value is 600이고, binary 변수 x 가 0.7일 때 relax optimal solution을 가진다고 가정하겠습니다.
MIP 문제에서는
x <= 0 과 x >= 1로 나누어서 문제를 풉니다.
물론, relaxed optimal 값보다 작은 solution은 나올수 없겠죠.
x <= 0 인 경우, Z = 650
x >= 1 인 경우, Z = 620
의 solution 을 얻었다고 가정하면,
pseudo cost는 위의 x 변수 one unit를 증가시켰을 때 목적함수에 미치는 영향(up pseudo cost) 또는 x 변수 one unit를 감소시켰을 때 목적함수에 미치는 영향(down pseudo cost)을 말합니다.
따라서, 위에 경우는
up pseudo cost = 20/0.3 = 66.667 이고,
down pseudo cost is 50/0.7 = 71.429입니다.
위의 방법을 이용하면, 목적함수에 영향을 많이 미치는 변수에 대해서 좋은 휴리스틱을 구현할 수 있을뿐 아니라, 보다 빨리 integer solutions을 찾을 수 있습니다.
다음과 같은 함수를 이용하시면, PseudoCost값을 얻을 수 있습니다.
IloNum IloLinConstraint::getUpPseudoCost(const IloNumVar x);
IloNum IloLinConstraint::getDownPseudoCost(const IloNumVar x);
-
- 김복순2002-05-24
- 답변 고맙습니다.
올려주신 글을보고 처음보다 많이 이해했습니다.
말씀해 주신 함수의내용을 알기위해,
CPLEX manual (online and offline)을 모두 봤습니다.
하지만 매뉴얼에는
IlogNum IlogConstraint::getUpPseudoCost(const IloNumVar x);
IlogNum IlogConstrain::getDownPseudoCost(const IloNumVar x);가 나와있질 않아 자세히 보진 못했습니다.
함수의 내용이 어떤지 알려면 어떻게 해야하나요?
또한, branch and bound의 pseudo reduced cost 부분에 관해 CPLEX로 테스트를 해보고 싶은데 어떻게 하죠?
제가 아직 초보자라 그러는데요...
알려주셨으면 좋겠습니다. (고맙습니다.)
:김태현님의 글입니다.
:Pseudo cost는 변수가 목적함수에 기여하는 정도를 평가하는 것입니다.
:
:간단한 예를 설명을 드리면,
:minimization problem에서
:relax된 optimal value is 600이고, binary 변수 x 가 0.7일 때 relax optimal solution을 가진다고 가정하겠습니다.
:
:MIP 문제에서는
: x <= 0 과 x >= 1로 나누어서 문제를 풉니다.
:물론, relaxed optimal 값보다 작은 solution은 나올수 없겠죠.
:x <= 0 인 경우, Z = 650
:x <= 1 인 경우, Z = 620
:의 solution 을 얻었다고 가정하면,
:
:pseudo cost는 위의 x 변수 one unit를 증가시켰을 때 목적함수에 미치는 영향(up pseudo cost) 또는 x 변수 one unit를 감소시켰을 때 목적함수에 미치는 영향(down pseudo cost)을 말합니다.
:
:따라서, 위에 경우는
:up pseudo cost = 20/0.3 = 66.667 이고,
:down pseudo cost is 50/0.7 = 71.429입니다.
:
:위의 방법을 이용하면, 목적함수에 영향을 많이 미치는 변수에 대해서 좋은 휴리스틱을 구현할 수 있을뿐 아니라, 보다 빨리 integer solutions을 찾을 수 있습니다.
:
:다음과 같은 함수를 이용하시면, PseudoCost값을 얻을 수 있습니다.
:IloNum IloLinConstraint::getUpPseudoCost(const IloNumVar x);
:IloNum IloLinConstraint::getDownPseudoCost(const IloNumVar x);
:
:
-
- 소경철2002-05-25
이 함수는 ILOG CPLEX 매뉴얼이 아니라 ILOG Hybrid의 Reference Manual을 찾아보셔야 합니다.
객체 이름 또한 IlogConstraint가 아니라 IloLinConstraint 입니다. 착오없으시기 바랍니다.
그리고, CPLEX를 이용한 Variable Selection 전략 테스트는 다음의 코드를 이용해서 간단하게 구현을 해서 시도해 보시기 바랍니다.
void main() {
IloEnv env;
IloModel model(env);
// 변수 생성
// 제약 부과 => model.add(제약);
// 목적함수 부과 => model.add(목적함수);
IloCplex cplex(model);
cplex.setParam(IloCplex::VarSel, 4);
// 0 = Branch variable automatically selected
// 1 = Branch on variable with maximum infeasibility
// 2 = Branch based on pseudo costs
// 3 = Strong Branching
// 4 = Branch based on pseudo reduced costs
cplex.solve();
env.out() << \"Obj = \" << cplex.getObjValue() << endl;
env.out() << \"Value = \" << cplex.getValue(변수) << endl;
env.end();
}
:김복순님의 글입니다.
:답변 고맙습니다.
:
:올려주신 글을보고 처음보다 많이 이해했습니다.
:
:말씀해 주신 함수의내용을 알기위해,
:
:CPLEX manual (online and offline)을 모두 봤습니다.
:
:하지만 매뉴얼에는
:IlogNum IlogConstraint::getUpPseudoCost(const IloNumVar x);
:IlogNum IlogConstrain::getDownPseudoCost(const IloNumVar x);가 나와있질 않아 자세히 보진 못했습니다.
:
:함수의 내용이 어떤지 알려면 어떻게 해야하나요?
:
:또한, branch and bound의 pseudo reduced cost 부분에 관해 CPLEX로 테스트를 해보고 싶은데 어떻게 하죠?
:
:제가 아직 초보자라 그러는데요...
:
:알려주셨으면 좋겠습니다. (고맙습니다.)
목록
확인