私はSCIPの初心者です。ブランチと価格のフレームワークとして SCIP を使用したいと考えています。私はすでに C++ で問題をコーディングしており、プライサーまたは列生成を関数として実装しています。実際、Cplex.dll をプロジェクトにリンクすることでルート ノードの BP アルゴリズムを実装しました。次に、分岐ツリーをコーディングする必要があり、この目的のために SCIP を使用することにしました。SCIP と私が持っている古いコードを使用して問題を解決できる最速の方法を知りたいですか? それとも、GCG を使用する方がより適切で高速な方法でしょうか? GCG のドキュメントを読みましたが、プライサーを自分で再度実装する必要があるかどうかわかりません。実際、私はこれら 2 つ (SCIP と GCG) の違いを理解していません。ありがとう。
1 に答える
1
GCG では、自分で何も実装する必要はありません。これは、分岐と価格の一般的なソルバーです。コンパクトな定式化、つまり、Dantzig-Wolfe 再定式化を適用した後に、解決しようとしているマスター問題につながるモデルを提供する必要があります。再定式化は価格設定問題の MIP 定式化も提供するため、GCG はこれを価格設定のサブ MIP として解決できます。ただし、GCG にプライシング ソルバーをプラグインする可能性があります。これには、解決されるプライシング MIP が渡されます (現在のプライシング ラウンドに対応する目的関数を使用)。その後、価格設定ソルバーは、問題固有のアルゴリズムを使用してこの問題を解決し、解決策を GCG に戻すことができます。
一方、SCIP では、解決したいマスター問題を作成し、LP から二重値を取得して対応する価格設定問題を解決するプライサーを実装します。これはおそらくあなたがすでに持っているものと非常に似ています。
さらに、分岐と価格を実行する場合は、分岐ルールが必要です。GCG にはいくつかの一般的なものがありますが、SCIP では自分で実装する必要があります (分岐の決定は価格設定手順内で考慮する必要があるため)。
全体として、SCIP は分岐と価格のフレームワークです。つまり、ツリー管理、LP の解決と更新などを提供しますが、リーダー、プライサー、分岐ルールなどの一部を自分で実装する必要があります。GCG は一般的なソルバーであるため、コンパクトなモデルをプラグインするだけで、一般的な方法で再定式化および解決できます。再構成は、入力ファイルを介して提供されるか、GCG に適切な構造を検出させることができます。何も実装する必要はありません。再定式化を利用する主なヒューリスティック、価格設定の問題がいつ解決されるかの自動管理など、いくつかの優れた機能が既に提供されています。一方で、価格設定ソルバーや分岐ルールなどによってさらに拡張する可能性は、SCIP に比べて制限されています。
SCIP を使用してプライサーを追加するのがおそらくより簡単な方法であり、既にお持ちのものに似ていると思います (コンパクトなモデルを定式化する必要はありません)。分岐がどのように機能するかについてすでに考えがある場合は、SCIP 内での実装もそれほど難しくないはずです。
于 2016-11-29T09:59:19.333 に答える