이전 코드를 사용하는 SCIP

Question

나는 SCIP에 대해 처음 사용합니다. SCIP을 지점 및 가격 체계로 사용하고 싶습니다. 나는 C++에서이 문제를 이미 코딩했고, 함수로 pricer 나 column 생성을 구현했다. 사실 Cplex.dll을 프로젝트에 연결하여 루트 노드에 대한 BP 알고리즘을 구현했으며 이제 분기 트리를 코딩해야하며이 목적으로 SCIP를 사용하기로 결정했습니다. 내가 가지고있는 SCIP 및 이전 코드를 사용하여 내 문제를 해결할 수있는 가장 빠른 방법은 무엇입니까? 아니면 GCG를 사용하는 것이 더 빠르고 더 좋은 방법일까요? GCG 문서를 읽었지만 pricer를 다시 구현해야하는지 여부를 이해하지 못합니까? 사실 나는이 두 가지 (SCIP와 GCG)의 차이를 이해하지 못합니다. 감사합니다. .

Answer 1

GCG에서는 직접 구현할 필요가 없습니다. 그것은 branch-and-price를위한 일반적인 솔버이다. 컴팩트 포 뮬레이션, 즉 Dantzig-Wolfe 재구성을 적용한 후 해결중인 마스터 문제로 이어지는 모델을 제공해야합니다. 이 재구성은 가격 결정 문제의 MIP 공식을 제공하기 때문에 GCG는 이것을 가격 결정을위한 하위 MIP로 해결할 수 있습니다. 그러나 GCG에 가격 결정 솔 루션을 플러그인 할 수 있습니다.이 솔 루션에는 해결할 가격 결정 MIP가 전달됩니다 (현재 가격 결정 라운드에 상응하는 객관적인 기능 포함). 그런 다음 가격 결정 솔버는 문제 별 알고리즘으로이 문제를 해결하고 솔루션을 GCG로 다시 전달할 수 있습니다.

SCIP에서는 해결하려는 마스터 문제를 만들고 LP에서 이중 값을 가져 와서 해당 가격 책정 문제를 해결하는 pricer를 구현합니다. 이것은 아마도 이미 가지고있는 것과 매우 유사 할 것입니다.

또한 branch-and-price를 수행하려면 분기 규칙이 필요합니다. GCG는 몇 가지 일반적인 것들을 제공합니다. SCIP에서는 스스로를 구현해야합니다 (분기 결정은 가격 결정 절차 내에서 고려되어야하기 때문에).

전반적으로, SCIP는 분기 및 가격을위한 프레임 워크입니다. 즉, 트리 관리, LP 해결 및 업데이트 등을 제공하지만 독자는 독자, 가격 책정자 및 분기 규칙. GCG는 일반적인 솔버이므로 컴팩트 모델을 플러그인 할 수 있습니다.이 모델은 공식화되고 일반 방식으로 해결됩니다. 재구성은 입력 파일을 통해 사용자가 제공하거나 GCG가 적절한 구조를 감지하도록 할 수 있습니다. 아무 것도 구현할 필요가 없습니다. 그것은 이미 재구성을 사용하는 원시 발견 적 방법, 가격 책정 문제가 자동으로 해결되는 것과 같은 멋진 기능을 제공합니다. 반면에, GCG에 의해 정의 된 구조를 고수해야하기 때문에, 예를 들어 가격 책정 해결사 및 분기 규칙에 의해 SCIP에 비해 더 확장 될 가능성이 제한됩니다.

나는 SCIP를 사용하고 pricer를 추가하는 것이 아마도 당신이 이미 가지고있는 것보다 더 쉬운 방법 일 것이라고 말하고 싶다. (당신은 콤팩트 모델을 공식화 할 필요가 없다.) 분기가 어떻게 작동해야하는지에 대한 아이디어가 이미 있다면 SCIP 내에서 구현하는 것이 너무 어렵지 않아야합니다.