|
|
제 목 |
[RE] pseudo reduced cost에 관하여 |
|
작성자 |
김태현 |
작성일 |
2002-05-24 |
조회수 |
1177 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
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);
|
|
|
|
