주메뉴 바로가기 본문 바로가기 하단 바로가기

고객지원

기술문의

disjunctive constraint에 관해 여쭈어 봅니다.

  • 김태규
  • 2008.02.25
  • 조회수 2,138
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

댓글 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의 의미를 잘 못 알고 있었군요

    감사합니다.

    아이콘삭제

댓글 입력