古いコードを使用したSCIP

Question

私はSCIPの新しいものです。 SCIPをブランチと価格フレームワークとして使用したいと思います。私はすでにC++でこの問題をコード化しており、関数としてのpricerまたはcolumnの生成も実装しています。実際、Cplex.dllをプロジェクトにリンクすることでルートノードのBPアルゴリズムを実装しましたが、今は分岐ツリーをコード化する必要があり、この目的のためにSCIPを使用することに決めました。 私はSCIPと私が持っている古いコードを使って自分の問題を解決できる最速の方法は何ですか？または、GCGを使用する方がより優れた方法ですか？ 私はGCGのドキュメントを読んだことがありますか？実際、私はこれらの2つの違いを理解していません（SCIPとGCG）。おかげさまで

Answer 1

GCGでは、自分で実装する必要はありません。それは支店と価格のための一般的なソルバです。 Dantzig-Wolfeの再定式化を適用した後、あなたが解決しているマスター問題につながるコンパクトな製剤、つまりモデルを提供する必要があります。この改訂はまた、価格問題のMIP策定を提供するので、GCGはこれを価格決定のためのサブMIPとして解決することができます。しかし、解決しようとする価格設定MIPが（現在の価格決定ラウンドに対応する目的関数を用いて）渡されるGCGに価格設定ソルバーをプラグインする可能性があります。価格決定ソルバは、この問題を問題固有のアルゴリズムで解決し、ソリューションをGCGに戻すことができます。

一方、SCIPでは、解決したいマスター問題を作成し、LPから二重の値を取得し、対応する価格問題を解決する価格を実装します。これはあなたがすでに持っているものと非常によく似ています。

さらに、分岐価格を実行する場合は、分岐ルールが必要です。 GCGにはいくつかの一般的なものが付属していますが、SCIPでは自分で実装する必要があります（ブランチングの決定は価格設定手順の中で行わなければならないため）。

全体的に、SCIPは支店と価格のフレームワークです。つまり、ツリー管理、LP解決と更新などを提供しますが、読者、値札、分岐ルール。 GCGは一般的なソルバーなので、コンパクトなモデルをプラグインするだけで、一般的な方法で再定式化され解決されます。再構成は、入力ファイルを介してユーザーから提供されるか、GCGに適切な構造を検出させるように試みることができます。何も実装する必要はありません。これは、すでに定式化された経験則のような素敵な機能を提供しています。一方、GCGによって定義された構造に固執する必要があるため、たとえば価格設定ソルバや分岐ルールなどでさらに拡張する可能性はSCIPに比べて制限されています。

私は、SCIPを使用し、あなたの値段を追加する方が、おそらくあなたがすでに持っているもの（よりコンパクトなモデルを作成する必要はありません）に似ていると言います。ブランチングがどのように機能するかについてのアイデアが既にある場合は、SCIP内で実装するのも難しくありません。