SCIP를 사용하는 B & P의 분기 메커니즘

Question

SCIP를 사용하여 분기 및 가격 알고리즘을 구현했습니다.

질문 : 분기 메커니즘을 호출하기 위해 기본 BRANCHEXECLP 메커니즘을 사용합니다. SCIP는 언제 출장해야하는지 어떻게 알 수 있습니까? 현재 이완 해결책이 비 - 정수 해를 가질 때, 맞습니까? 이 경우 브랜칭 메커니즘을 호출하도록 SCIP에게 알릴 필요는 없습니다. 맞습니까?

(대부분은) 내 B & P 알고리즘이 잘 작동하기 때문에 묻습니다. 그러나 어느 시점에서 이중 결합 솔루션에 해당하는 노드에 도달합니다. 가격 문제를 해결 한 후 (마스터 문제를 입력하는 데 유용한 열이 없음)이 노드의 완화 솔루션에는 비 정수 솔루션이 포함되어 있지만 분기 메커니즘은 호출되지 않습니다. 달리기가 방금 종료됩니다. 여기에 무슨 일이 벌어지고 있는지에 대한 어떤 생각?

감사합니다, 롭 카레

Answer 1

나는 현재 LP 솔루션에서 분수 변수가 있음을 가격하는 동안 확인 추측?

그리고 그 노드에서 이중 경계는 전역 이중 경계와 같습니까? 당신은 오직 당신의 목표를 적분 값으로 만 표기 했습니까? 이 경우, 이중 경계가 원의 경계에 충분히 가까워지면, 그 경계가 반올림 됨으로써 동일한 수를 얻게된다. SCIP은 단지 노드를 차단할 것이다. 아마도 SCIP는 가격 책정 후에도 현재의 글로벌 듀얼 경계에 의해 최적 인 것으로 즉시 입증 된 새로운 솔루션을 발견했을 것입니다. SCIP은 가격 결정 루프에서 해결 된 각각의 LP 이후에 자동으로 간단한 반올림 추론을 실행합니다.