0

LP ソルバーとして cplex 12.6 で SCIP 3.0.2 を使用しています。私のモデルには列の生成が必要です。私はすでに CPLEX に実装しましたが、CPLEX はルート ノードで CG しか実行できないため、SCIP を使用して Branch-and-Price を実行しています。CPLEX では、ヒューリスティック、カット、および前処理/プローブをオフにすることが有益であることが判明しました。SCIP で次のように設定します。

SCIP_CALL( SCIPsetBoolParam(scip, "lp/presolving", FALSE) );

SCIPsetSeparating(scip, SCIP_PARAMSETTING_OFF, true);   //disable cuts
SCIPsetHeuristics(scip, SCIP_PARAMSETTING_OFF, true);   //disable heuristics
SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, true);   //disable presolving

私のパラメーターファイルは次のようになります。

display/primalbound/active = 1
presolving/maxrounds = 0
separating/maxrounds = 0
separating/maxroundsroot = 0
separating/maxcuts = 0
separating/maxcutsroot = 0
lp/initalgorithm = d
lp/resolvealgorithm = d
lp/fastmip = 1
lp/threads = 1
limits/time = 7200
limits/memory = 2900
limits/absgap = 0
#display/verblevel = 5
#display/freq = 10

モデルが同じであることを確認するために、CPLEX モデルを SCIP (CG なし) で解決し、SCIP で生成されたモデルと同じ LP バウンドを得ましたが、CPLEX で解決した場合の LP バウンドとは異なります。

SCIP は、私がまだ解除していない「魔法」をまだ使用しているようです。したがって、私の質問は、モデルだけに依存して LP バウンドを取得するために何を非アクティブ化する必要があるかということです。

私はすでに統計出力を見てきましたが、実際には問題の解決に役立つ可能性のあるものがいくつかあります。

  1. 制約 #EnfoLP は積分に対して 1 をリストします (カットが無効になっているので奇妙に思えますか?)
  2. 変換された問題は問題ないようです。統計出力は次のように表示されます。

解決済みの問題 : 問題名 : t_ARLP 変数 : 969 (バイナリ 806、整数 0、暗黙的整数 0、連続 163) 制約 : 初期 9311、最大 9311

反復が開始される前に、次の結果が得られます。

LP ソルバー : 基底の行表現は利用できません -- SCIP パラメータ lp/rowrepswitch は効果がありません 変換された問題には 897 の変数 (806 ビン、0 int、0 impl、91 cont) と 9311 制約があります

9311 タイプ < 線形 > の制約

事前解決: 事前解決 (0 ラウンド): 0 削除された変数、0 削除された制約、0 追加された制約、0 強化された境界、0 追加された穴、0 変更された辺、0 変更された係数 0 含意、0 クリーク 事前解決された問題には 897 個の変数があります (806 ビン、0 int、0 impl、91 cont) および 9311 制約

9311 タイプ < 線形 > の制約

前解決時間: 0.00

72 個の列を追加しました: 元の 91 個 + 追加された 72 個 = 合計 163 個。これは大丈夫そうです。

推奨パラメータを追加しました。ドメインの伝播は以前は使用されていなかったようですが、強力な分岐がありました。残念ながら、パラメータに変更はありませんでした。

パラメータを追加することに加えて、代わりに SCIP 3.0.1 を使用しようとしました。これにより、バウンドが 670.194 から 699.203 に改善されましたが、754.348 でバインドされた cplex とはまだかなり異なります。ソルバーが多くの数値パラメーターによって異なることは知っていますが、これらのパラメーターによって引き起こされるには違いが大きすぎると思いますか?

4

3 に答える 3

2

ルート ノードでバインドされた LP に影響を与える可能性があるものは他に 2 つあります。それは、ドメインの伝播と強い分岐です。

ドメインの伝播は一種のノード前処理であり、現在のローカル ドメインと制約に基づいて可変ドメインを削減しようとします。強力な分岐は、潜在的な子ノードの LP 境界を事前計算して、分岐に適した変数を選択します。子ノードの 1 つが実行不可能であることが検出された場合、そのドメインは削減されます。

設定することにより、ドメインの伝播を無効にすることができます

propagating/maxrounds = 0
propagating/maxroundsroot = 0

強い分岐を適用しない分岐ルールに高い優先度を設定することで、強い分岐を無効にすることができます。たとえば、

branching/pscost/priority = 100000000

純粋な疑似コスト分岐を有効にするため。

一般に、 DomReds列のゼロ以外の値について統計を確認する必要があります。

于 2014-05-13T19:51:24.910 に答える
1

内部の問題をファイルに書き込んで、元の問題と比較するだけです。

SCIP> write transproblem

また、SCIP の統計をよく読んで、SCIP が実行した「魔法」の種類を確認する必要があります。

SCIP> display statistics
于 2014-05-10T18:40:10.930 に答える
1

私はスレッドのことをほとんど忘れていましたが、再びそれに出くわし、自分で見つけた後に答えを追加するのが良いかもしれないと考えました:カットコールバック内で(残念ながら、私が使用したことについては言及しませんでした)私はメソッドを使用しました:

SCIPisCutEfficacious

これは、真の LP バウンドを得るために関連するいくつかのカットを破棄しました。このメソッドを呼び出さないと、解決プロセスが遅くなりますが、少なくとも結果は保持されます。

于 2017-06-13T09:00:10.460 に答える