고객지원
기술문의
disjunctive constraint에 관해 여쭈어 봅니다.
- 김태규
- 2008.02.25
- 조회수 2,232
disjuctive constraint 는 || 로 표현이 된다고 들어서 사용했는데..
최종해의 값이 disjunctive 두가지 제약을 둘 다 어긴다고 나와서 이상합니다.
예를 들면,
첨부화일을 돌려보면,
id1626: - m2t[0][1] + ut[3][0] - 1000000 id1624 >= -999994
id1628: ut[0][0] - m2t[3][1] + 1000000 id1624 >= 6
Bounds
0 <= id1624 <= 1
Generals
id1624
의 식이 있는데, 최종값은
ut[0][0] = 304.000000
m2[0][1] = 389.000000
ut[3][0] = 181.000000
m2[3][1] = 303.000000 입니다.
그러면
-389 + 181 + Big_K(1-id1624) >= 6
304 - 303 + Big_K (id1624) >= 6
이니 두 식다 어긋나는데, 제가 뭐를 잘못한건가요?
@Cplex는 9.x 버전인거 같습니다.
proto.cpp
최종해의 값이 disjunctive 두가지 제약을 둘 다 어긴다고 나와서 이상합니다.
예를 들면,
첨부화일을 돌려보면,
id1626: - m2t[0][1] + ut[3][0] - 1000000 id1624 >= -999994
id1628: ut[0][0] - m2t[3][1] + 1000000 id1624 >= 6
Bounds
0 <= id1624 <= 1
Generals
id1624
의 식이 있는데, 최종값은
ut[0][0] = 304.000000
m2[0][1] = 389.000000
ut[3][0] = 181.000000
m2[3][1] = 303.000000 입니다.
그러면
-389 + 181 + Big_K(1-id1624) >= 6
304 - 303 + Big_K (id1624) >= 6
이니 두 식다 어긋나는데, 제가 뭐를 잘못한건가요?
@Cplex는 9.x 버전인거 같습니다.
proto.cpp
댓글 7
-
- 소경철2008-02-26
- id1626과 id1628의 두 제약은 서로 disjunctive 관계에 있는 제약입니다.
따라서 두 제약중에 하나는 만족하고 다른 하나는 만족하면 안되는거죠..
id1624의 값이 1로 결정됐다고 하겠습니다.
그러면
-389 + 181 + Big_K(1-id1624) >= 6 -- (1)
304 - 303 + Big_K (id1624) >= 6 -- (2)
위의 두 식 중에서 (1)번은 만족하지 않고, (2)번은 만족하게 되죠..
반대로 id1624의 값이 0으로 결정되었다고 하면 반대의 결과가 나오게 됩니다. (즉 (1)번은 만족하고, (2)번은 만족하지 않게 되겠죠..)
즉, 이 문제에서 disjuctive constraint는 정상 동작하고 있다고 보입니다..
-
- 이상진2008-02-27
- MIP에서 모든 제약식이 "만족"해야 feasible solution이 나오는 것 아닌지요?
하나라도 만족하지 않으면 infeasible이지 않나요?
disjunctive constraint이기 때문에 하나는 "만족(tight?)"하고 하나는 의미가 없어진다 (--> 있으나 마나한 식으로 변한다) 로 해석되어야 하지 않나 생각됩니다.
따라서 제 생각엔 "만족하지 않는다"가 아니고 "의미가 없어진다"가 맞지 않을까 합니다.
-389 + 181 + Big_K(1-id1624) >= 6 -- (1)
304 - 303 + Big_K (id1624) >= 6 -- (2)
여기서 "id1624"가 "1"이라면 식 (1)은 모순이 되고 식(2)는 있으나 마나한 식으로 전환되는 것 아닌지요? 반대의 경우도 역시 같은 이유일 듯 한데요.
-
- 소경철2008-02-27
- 두 제약 A와 B가 disjunctive constraint로 정의되었다면, 두 제약 중에서 최소한 하나의 제약은 만족을 해야 합니다. 두 제약이 모두 만족해도 상관없구요...
즉, 제약 A에 해당하는 0/1 Integer 변수 a와 제약 B에 해당하는 0/1 Integer 변수 b라고 하면, a+b >= 1이라는 제약이 성립한다고 볼 수 있는 거죠...
-
- 김태규2008-02-27
- disjunctive constraint는 둘 중에 하나만 만족해야한다는 것은 맞는데..
-389 + 181 >= 6 -- (1)
304 - 303 >= 6 -- (2)
위의 식 둘 중에 하나만 만족시키기 위해서,
-389 + 181 + Big_K(1-id1624) >= 6 -- (3)
304 - 303 + Big_K (id1624) >= 6 -- (4)
id1624 = 0 or 1 -- (5)
와 같이 표현이 된것 아닌지요?
근데 최적해값이 두 식 (1) (2)중에 어느것도 만족시키지 않는 결과가 나와서 이상합니다.
제 식을 어떻게 고쳐야하나요?
-
- 소경철2008-02-27
- 첨부 파일에 제약 이름을 부여한 다음 생성된 LP 파일에서 가져온 제약입니다.
ct31_0,0,3: id2496 + id2498 >= 1
i5: id2496 = 1 <-> - m2t(0)(1) + ut(3)(0) >= 6 --- (1)
i6: id2498 = 1 <-> - m2t(3)(1) + ut(0)(0) >= 6 --- (2)
문의하신 제약과 동일한 의미죠...
이렇게 실행한 결과 중에서 위 제약에 포함된 변수의 값만 가져오면 다음과 같습니다.
(생성된 결과 파일에서 가져왔습니다.)
var mark row col start dur
m2[0][1] m2 0 1 613.000000 6
m2[3][1] m2 3 1 230.000000 6
ut[0][0] U 0 0 518.000000 11
ut[3][0] U 3 0 86.000000 11
이 값을 (1), (2) 제약에 대입시켜 보면 다음과 같습니다.
-613 + 86 >= 6 --- (3) => 위반
-230 + 518 >= 6 --- (4) => 만족
(3)번은 위반했고, (4)번은 만족했네요..
이 결과로 보면 아무런 문제없이 정상 실행하는 것으로 보이는데요...^^
수정한 소스 파일, 생성된 LP 파일, 그리고 결과 파일을 첨부하겠습니다..
-
- 이준호2008-02-27
- 먼저 문의하신 Disjunctive 제약의 표현 및 작용에 대한 수식적인 이해가 정확하게 선행되면 좋을 것 같습니다.
ct31_0,0,3: id2496 + id2498 >= 1
i5: id2496 = 1 <-> - m2t(0)(1) + ut(3)(0) >= 6 --- (1)
i6: id2498 = 1 <-> - m2t(3)(1) + ut(0)(0) >= 6 --- (2)
위에서 나온 포맷 대로, "<->" Operator를 통해서 Disjunctive Constraint가 표현이 됩니다. 또한 이렇게 표현된 제약의 경우 둘 중 하나만 만족시키면 되는 것이죠.
만약 i5, i6 각각이 LP파일에서 단순히
i5:- m2t(0)(1) + ut(3)(0) >= 6
i6:- m2t(3)(1) + ut(0)(0) >= 6
...위와 같이 표현되었다면, 둘 모두 당연히 만족해야 하며, 그렇지 않을 경우 Infeasible이 됩니다. 그러나 Disjunctive 제약은 둘 중 하나만 만족하면 되는 것입니다.
-
- 이상진2008-02-27
- 제가 disjunctive constraint의 의미를 잘 못 알고 있었군요
감사합니다.
목록
확인