1

新しい scip 緩和ハンドラーを作成しようとしています。ノードごとに、その下限と上限を自分が思いついた値で更新したいと考えています。次に、scip が解決プロセスでこれらのより良い境界を自然に使用するようにします。しかし、私は奇妙な結果を得ています。

私の質問は、ブランチ アンド バウンドで現在のノードの下限と上限を更新するにはどうすればよいですか?

リレーション ハンドラ内には、次のデバッグ コードがあります。

double l = -100;
double u = -15;
cout << "SCIP STAGE " << (scip->set->stage) << std::endl;
cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << l             << " <= " << u << endl;

SCIPupdateLocalLowerbound(scip, l);

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;

出力は

SCIP STAGE 9
1 min scip  -1e+14 <= -100000
1 min my b  -100 <= -15
1 min scip  1e+20 <= -10000

scip ステージ 9 は SCIP_STAGE_SOLVING で、良さそうです。

「scip」のある行は、ノードに対する scip の境界です。「my b」のある中央の行は、私の新しい境界を表します。

SCIPupdateLocalLowerbound(scip, -10)現在の下限が -1e14 であるときに呼び出しているため、その呼び出しの後、新しい下限は 10 になるはずです。ただし、下限は 1e20 に変更され、これは大きなエラーです。

SCIPupdateLocalLowerbound(scip, -10);私はそれがSCIPgetLocalLowerbound(scip)リターンで-10はないと期待してい1e20ます。私は何を間違っていますか？

また、 という関数が表示されないSCIPupdateLocalUpperbound()ので、ノードの上限を更新するにはどうすればよいですか?

EDIT 2015/03/13 scip のその部分を説明してくれてありがとう。1 つ小さな質問が残っています。

完全を期すために、ローカル ノードの最小化問題の下限を次のように設定しています。

SCIPupdateLocalLowerbound(scip, l)

そして、最小化問題のグローバルな上限を次のように設定しています

if ( newUpperBound < scip->primal->upperbound)
    {
        SCIPprimalSetUpperbound(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->transprob, scip->tree, scip->lp, newUpperBound);
    }

SCIPprimalSetUpperbound の 2 番目のパラメーターは、

BMS_BLKMEM*           blkmem,             /**< block memory */

そして、scip->mem で見つけた blkmem を渡しています。これは正しいですか、それとも他のクリーンなブロック メモリを渡す必要がありますか? 重要なものを上書きしていますか？

編集 2015/03/19

目的関数を設定するときの出力がわかりません。(私にとって) 注意点として、元のマスター問題は最大化問題であり、scip の変換された問題は最小化です。の結果を見てみると

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << newLowerBound             << " <= " << newUpperBound << endl;


cout << "SCIPgetObjlimit " << SCIPgetObjlimit(scip) << endl;
cout << "SCIPretransformObj " << SCIPretransformObj(scip,newUpperBound) << endl;

出力は次のとおりです。

7 min scip  -1.10142e+08 <= 100000
7 min my b  -1.37597e+08 <= 2.11197e+08
SCIPgetObjlimit -1.97183e+08
SCIPretransformObj -2.11197e+08

したがって、このノードの最小値に対する scip の境界は -1.10142e+08 <= 100000 であり、このノードの最小値に対する私の境界は -1.37597e+08 <= 2.11197e+08 であり、この場合はさらに悪化します。

なぜ SCIPgetObjlimit = -1.97183e+08 なのですか? -100000 でないのはなぜですか? 100000 が変換された空間 (最小化) の現在の上限である場合、-100000 が元の問題の現在のグローバルな下限です。

4

1 に答える 1

2

下限は各ノードに固有のローカル プロパティですが (通常、このノードでの最適な LP 緩和目標から、または既に解決されている場合はノードの子の下限から推測されるため、上限は主なソリューションから得られます)。問題であり、したがってグローバルに有効です。

SCIP の観点からは、グローバルな上限以上の下限を持つすべてのノードを削除することができ、そのようなノードは +infinity (つまり、デフォルトの SCIP 設定では 1e+20) を下限として取得します。値をよく見ると、ローカル バウンドをl=-100に設定するとグローバル バウンドが -100000 になるため、このノードが強制的にプルーニングされることがわかります。したがって、SCIP の動作はここで意図されたものです。

編集 質問の2番目の部分に関して:実際には、たとえば、プラグイン内からprimal.hに由来する、リラクセータなどのメソッドを使用することは、ある意味で禁止されています。その理由はまさに、気にする必要のない SCIP 内部に関して、あなたが今直面している問題です。SCIPprimalSetUpperBound()

代わりに、目的の制限を設定することをお勧めしSCIPsetObjlimit()ます。客観的な制限は、元のスペースで指定する必要があることに注意してください。前に上限を渡したい場合は、ub = SCIPretransformObj(scip, ub)and afterを使用しSCIPsetObjlimit(scip, ub)ます。

元の変換された問題の主な境界を編集します。

  1. SCIPgetUpperBound(scip): 変換された問題空間の現在の上限、最適解目的の最小値、および (変換された) 目的限界
  2. SCIPgetPrimalBound(scip):SCIPgetUpperBound(scip)元の問題空間での の値。最善の解決策とユーザーの目標制限の両方を考慮します。
  3. SCIPgetObjlimit(scip): ユーザーが設定した目標制限の値であり、主要なソリューション目標を尊重していません。

客観的な制限を設定したと思いますが、SCIP はより優れた主な解決策を見つけました。

于 2015-03-12T09:06:42.033 に答える