2
this link과 같이 문제가 발생합니다.MATLAB에서 bintprog을 반복적으로 사용
가 bintprog 리콜과 종래 용액 x을 배제 할 수 있고, bintprog의 첫 번째 통화가 어떤 사후 처리가 적절하게 물리적 문제를 해결하지 않는 한 후 그 용액 x을 제공한다는 고려?
A
답변
0
노구드 커팅이 필요합니다.
어떤 종류의 사후 처리를 통해 결정할 수없는 솔루션 \ hat {x}을 발견했다고 가정 해 보겠습니다. x와 \ hat {x}가 i에 의해 색인이 만들어 지도록합시다. 이 솔루션은 적어도 하나 개의 인덱스 I에 의해 {X} \ 모자 달라야합니다 :이 제약이없는 좋은 컷의 예입니다
\sum_{i : \hat{x}_i = 0} x_i + \sum_{i : \hat{x} = 1} (1-x_i) \geq 1
:
는 다음과 같은 형식의 제약 조건을 추가 할 수 있습니다 그렇지 않으면 실행 불가능하다. 변수가 바이너리가 아닌 경우 no-goods는 좀 더 복잡 할 수 있습니다.
제약 조건 행렬에 제약 조건을 추가하고 bintprog() 함수를 사용하여 문제를 해결하면 솔루션에 좋지 않은 점을 추가 할 수 있습니다. MATLAB 표기법으로 다시 작성하겠습니다.
당신은 당신의 후 처리가 무엇인지 말하지 않았지만, 후 처리가 당신의 solution \ hat {x}에서 다른 솔루션도 실행 불가능하다는 것을 추론 할 수 있다면 훨씬 더 좋을 것입니다. 반복 당 하나의 행. 이것은 논리 기반 Benders 분해의 한 형태이며, 다른 실행 불가능한 솔루션의 추론은 추론 이중 해결이라고 부릅니다 (선형 프로그래밍 이중을 해결하는 표준 Benders 분해와 반대입니다). More on logic based Benders decomposition CMU의 John Hooker라는 용어를 사용했다.
서식을 지정해 주셔서 감사합니다. 나는 가야하지만 나중에 더 멋지게 방정식을 표시하는 방법을 찾아 낼 것이다.
제약 조건으로 추가하지 않는 이유는 무엇입니까? – Bitwise
@Bitwise 'bintprog'에 두 가지 유형의 제약 조건을 추가 할 수 있습니다. 첫 번째 것은 불평등에 해당하고 두 번째 것은 평등에 해당합니다. 나는 평등 제약에 대한 특정한 논쟁을 이미 가지고 있으며, 내가 원하는 것에 대한 불평등 제약 조건을 통합 할 수있는 방법을 생각할 수 없다. 무슨 생각해? –
불평등은 어떨까요? x = 3이면 x <= 2와 -x <= - 4를 더합니다. 아니면 지원되지 않습니까? – Bitwise