|
|
제 목 |
[RE] pseudo reduced cost에 관하여 |
|
작성자 |
김복순 |
작성일 |
2002-05-24 |
조회수 |
1186 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
답변 고맙습니다.
올려주신 글을보고 처음보다 많이 이해했습니다.
말씀해 주신 함수의내용을 알기위해,
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);
:
: |
|
|
|
