最適化セミナーのご案内

15.3.4 整数計画法(simplex/asqp)/大域的最適化(global)に有効なパラメータ

 以下のパラメータは単体法(simplex)/有効制約法(asqp)/大域的最適化(global)を,整数変数を含む問題について適用した際,あるいは大域的最適化(global)を非線形計画問題に対して適用した場合にのみ有効です.

 これらのアルゴリズムは,整数変数の整数条件を一部緩和した問題を繰り返し解きながら,分枝限定法というスキームによって,整数条件を満たす実行可能解の発見と,実行可能解の最適性の保証を行うものです.本質的に難しいクラスに属する問題であるため,連続変数のみからなる同程度の規模の問題に比べて,ときとして数倍程度の時間がかかることはよくあります.

 また,この分枝限定法というスキームの好ましからざる特徴として,最適解を発見して最適性を証明するまでの時間が問題の規模のみならず,問題の性質に大きく左右されるということがあります.具体的には,数万変数の問題が数秒で解けてしまったり,一方では数百変数の問題を解くのに一時間以上を所要したりということがございます.

 Numerical Optimizerは現在得られる最新の技法を組み込み,できるだけ多様な問題が安定にとけるようにパラメータをチューニングしておりますが,あらゆる性質の問題に対して常に良い設定を見出すことはできておりません.そのため,以下にご紹介するパラメータを適宜設定することによって,デフォルトの状態ではかなり時間を所要した問題をより効率よく解くことができることも十分にあり得ます.以下では効果的と思われる順にチューニングのためのパラメータをご紹介します.

 以下説明の便宜のため,解いている問題が最小化問題だと仮定します.最大化問題は目的関数の符号を逆にして最小化を行っていることと等価なので,意味は同じですが以下に出てくる下界値と上界値という言葉を逆転させて解釈する必要があります.

  • 切除平面法のパラメータ(simplex/asqpのみ有効)
    分枝限定法は整数性あるいは非凸性の条件を緩和した部分問題を解き,その解を,現在求められている実行可能解の下界値(これ以上小さくなることはあり得ないと理論的に保証された値)を参照しながら探索を行います.現在求められている実行可能解と下界値の差が零に近いとみなされたときに,現在得られている実行可能解の最適性が証明されたと判断し,アルゴリズムは停止します.
    切除平面法は,整数解が満たすであろう線形な制約式(妥当不等式と呼びます)を生成し,下界値を押し上げて,分枝限定法の収束を早める手法です.切除平面を加えるほど下界値は上がり,分枝限定法は早期に停止することが期待されますが,加えすぎると扱う問題の規模が増大するため,緩和解の計算コストがかさみ,結局実行時間の増大につながる可能性もあります.このパラメータは切除平面を加える個数を調整するものです.値としては0, 1, 2のいずれかを取ることができ,デフォルト値は1(標準的な量)です.2を設定すると,切除平面を多めに加えるようになり,0を設定すると全く加えなくなります.
    実行可能解は発見されるが,最適性がなかなか証明されずに停止しない状況ではこのパラメータを2に設定するのが効果的な可能性がございます.一方で最適解が問題なく得られている場合には,切除平面の追加が計算のオーバーヘッドになっている可能性がありますので,0に設定するのが有効な場合もあります.Numerical OptimizerはV12から追加される切除平面の種別を増やしたため,切除平面を比較的多めに加えるようになっています.結果として難しい(性質の悪い)問題のパフォーマンスは向上しましたが,以前の状態で高速にとけていた問題のパフォーマンスは低下している可能性はあります.切除平面の追加数が多すぎると感じる場合は,clevelを0に設定して試してみることをお勧めします.
    モデルファイルに記述する方法
    options.clevel = 1;
    パラメータファイルnuopt.prmに記述する方法
    branch:clevel=1
  • ヒューリスティックサーチを調整するパラメータ(simplex/asqpのみ有効)
    良質な実行可能解を早期に得ることは分枝限定法の収束を加速するうえで大きく貢献します.緩和問題の変数を一つずつ整数値に固定していった結果として実行可能解を得るのが通常の分枝限定法ですが,問題の対称性が強い場合などには実行可能解の発見が非常に遅くなることはあり得ます.ヒューリスティックサーチとは緩和解を様々な方法で変形して,良質な実行可能解を早期に得るためのテクニックです.この手法がうまく機能すれば,分枝限定法の収束が加速する,あるいはより良質な実行可能解が早く得られる可能性があります.
    各パラメータは組み込まれているヒューリスティックサーチの手法(rounding, feasibility Pump, neighbour search, rins)にそれぞれ対応しています.0は行わない,1は行うという意味となっています.また,roundingに関しては2, 3を設定することができ,値が大きいほど行う頻度が高くなります.feasibility Pumpとneighbour searchは大規模問題で実行可能解が得られにくい場合に効果的です.数千~数万変数規模の実行可能解がなかなか現れない問題を解いている場合には,適用を試みるとよい結果が得られる可能性があります.
    一方で規模の小さな問題(数百変数),あるいは実行可能解が既に多数出力される問題に対しては,ヒューリスティックサーチは効果がないばかりか時間を余計に所要する可能性があります.その際にはこれらのパラメータをすべて0として,ヒューリスティクスサーチをやめてみてください.デフォルトでは,rinsは実行する(1),その他のヒューリスティックサーチはNumerical Optimizerが実行有無を適当に判断する(負の値)です.
    モデルファイルに記述する方法
    options.rounding = -1; // -1,0,1,2,3を選択できます
    options.feasPump = -1; // -1,0,1を選択できます
    options.neighbourSearch = -1; // -1,0,1を選択できます
    options.rins = 1 // 0,1を選択できます
    パラメータファイルnuopt.prmに記述する方法
    branch:round=-1     *  -1,0,1,2,3を選択できます
    branch:feas=-1      *  -1,0,1を選択できます
    branch:neigh=-1     *  -1,0,1を選択できます
    branch:rins=1       *  0,1を選択できます
  • 探索深さ
    探索の深さを設定します.1とすると深さ優先探索を行います.大きい値であるほど,発見的探索に近くなります.
    pを大きめに設定すると実行可能解が見つかりにくく,所要メモリが大きくなりがちです.そのような場合にはp=1(深さ優先探索)という設定が有効な場合があります.
    モデルファイルに記述する方法
    options.p = 10;
    パラメータファイルnuopt.prmに記述する方法
    branch:p=10
  • wcsplpを用いた実行可能解探索の支援に関するパラメータ(simplex/asqpのみ有効)
    V17以降では,問題が線形な場合に限り,分枝限定法のヒューリスティックサーチの一つとして,wcspを使用することができます.このwcsplpを用いた実行可能解探索の支援を使用することはデフォルトの設定となっています.
    分枝限定法から使用されるwcspは,下記の点で単独使用のwcsplpと異なります.
    1. 0-1変数以外の変数は適当な刻み幅のDiscreteVariableとして扱われる
    2. wcspのtarget値は,変数の上下限を考慮した目的関数の最小値や最大値が使用される
    3. Numerical Optimizerが収束の具合を見計らい,自動的にwcsplpを用いた実行可能解探索の支援を終了する
    他のヒューリスティックサーチと同様に,wcsplpを用いた実行可能解探索の支援も実行可能解がなかなか得られない問題に対して使用することで良い結果が得られる可能性があります.逆に小規模な問題や実行可能解が多く見つかる問題に関しては,有効には作用せず求解時間の増加に繋がる可能性があります.
    また,wcsplpを用いた実行可能解探索の支援には,上記の特徴2.の影響で長い時間がかかってしまう場合もあります.このような場合には,wcspの反復回数上限や求解時間を制限することで,求解時間の増加を抑えられる可能性があります.反復回数上限のデフォルト値はNumerical Optimizerが適当に判断することを示す(-1)であり,求解時間のデフォルト値は180秒です.
    wcsplpを用いた実行可能解探索の支援に関するパラメタの設定方法は下記の通りです.
    • モデルファイルに記述する方法
      options.useWcsp = 1;            //0(使用しない), 1(使用する)
      options.branchWcspMaxitn = -1;  //-1または正の整数
      options.branchWcspMaxtim = 180; //正の整数
    • パラメータファイルnuopt.prmに記述する方法
      branch:useWcsp = 1        * 0(使用しない), 1(使用する)
      branch:wcspMaxitn = -1   * -1または正の整数
      branch:wcspMaxtim = 180        * 正の整数
  • 足切り点設定用パラメータ
    Numerical Optimizerは分枝限定法の探索中に,これまでで最良の目的関数値$f_{inc}$を持つ実行可能解が求まると,$f_{inc}$を基に足切り点$f_{cut}$

    \[f_{cut} = f_{inc} - \Delta_f \mbox{(最小化問題)} \]

    \[f_{cut} = f_{inc} + \Delta_f \mbox{(最大化問題)} \]

    と更新します.すなわち現在求まっている実行可能解から$\Delta_{f}$以上良い部分問題のみに探索を限ることになりますので,$\Delta_{f}$をより大きく設定することにより,探索がより絞り込まれ,計算の手間を減らすことが期待できます.
    ただし,その際には求まった解が最適であることは保証できません.その解から$\Delta_{f}$以上良い解がないことのみが保証されます.
    $\Delta_f$は,絶対値(addToCutoff)を設定する方法,LP緩和解からの相対値(rel_addToCutoff)で設定する方法の二つがあります.デフォルト値は絶対値1.0e-6,相対値0です.
    絶対値1.0e-6という設定は,目的関数の1.0e-6程度のぶれは小さなものとして無視してよいとしたことに相当します.
    相対値は例えば1.0e-4程度に設定するのが大多数の場合適切ですが,LP緩和解が真の最適解と大きくへだたっている場合には不適切な動作を招くのでデフォルト値は0となっています.LP緩和解が真の最適解に比べて同じ程度の大きさである場合には有用です.
    非線形問題に対する大域的最適化(global)の場合には,絶対値で指定する場合のデフォルト値は1.0e-5となります.相対値の指定をすることはできません.
    モデルファイルに記述する方法

    options.addToCutoff = 1.0e-6; // 絶対値で指定
    options.rel_addToCutoff = 1.0e-4; // 相対値で指定(globalでは無効)
    パラメータファイルnuopt.prmに記述する方法
    branch:add=1.0e-6       * 絶対値
    branch:reladd=1.0e-4    * 相対値(globalでは無効)
  • 足切り点
    足切り点設定用パラメータの箇所で説明した足切り点$f_{cut}$の値そのものです.足きり点(cutoff)より悪い解しか与えないことが解った問題は探索の対象から外します.従って,適切に設定すると計算の無駄を省くことができます.この値を最小化問題の場合は小さく(最大化問題の場合は大きく)設定するほど,足切り条件は厳しく,探索の対象は狭くなり,計算の手間は減ります.厳しく設定しすぎると実行可能解がない((NUOPT16) Infeasible MIP.)というエラーになりますので,注意が必要です.初期設定では何も設定されていません.
    モデルファイルに記述する方法
    options.cutoff = 1.0e-2;
    パラメータファイルnuopt.prmに記述する方法
    branch:cutoff=1.0e-2
  • 計算時間上限
    計算時間の上限です.計算開始から秒単位の計算時間が計算時間上限maxtimを越えると,下記のエラーメッセージとともに現在までの最適解を出力して実行を終了します.(実行可能解が見つかっていない場合にはLP(QP)緩和解のみの出力となります.また,0以下の値は設定していないのと同じ意味になります.)計算時間には,前処理や最初の緩和解を求める時間が含まれます.初期設定では計算時間上限なしを意味する-1が設定されています.
    (NUOPT 21) B&B itr. timeout (with feasible.sol).
    (NUOPT 22) B&B itr. timeout (no feasible.sol).
    モデルファイルに記述する方法
    options.maxtim = -1;
    パラメータファイルnuopt.prmに記述する方法
    crit:maxtim=-1
  • 整数解個数上限
    実行可能解の個数の上限です.0以下は設定していない(無制限)と同じと見なされます.1とすれば,実行可能解を1つだけ求めて終了する,ということが可能になります.計算開始から見つかった実行可能解の数がmaxintsolを越えると,以下のエラーメッセージとともに,現在までの実行可能解を出力して実行を終了します.
    (NUOPT 37) B&B terminated with given # of feasible.sol.
    モデルファイルに記述する方法
    options.maxintsol = -1;
    パラメータファイルnuopt.prmに記述する方法
    branch:maxintsol=-1
  • 最大メモリ量制限
    Numerical Optimizerプロセスが使用することのできる最大メモリ量を制限するためのパラメータで,MB単位で指定します.例えば1000とすると1GBを上限とすることを意味し,1GBを超えた場合に実行を停止します.
    負の値を設定すると,システムで利用可能なメモリ量が残り-maxmem以下になったときに実行を停止します.メモリ上限によって実行が停止した場合にはNUOPT43エラーが,実行可能解が見つかっていない場合にはNUOPT44エラーが出力されます.この場合,現在までの最適解を出力して実行を終了します(実行可能解が見つかっていない場合には緩和解のみの出力となります).
    (NUOPT 43) B&B memory error (with feasible.sol.).
    (NUOPT 44) B&B memory error (no feasible.sol.).
    モデルファイルに記述する方法
    options.maxmem = -10;
    パラメータファイルnuopt.prmに記述する方法
    branch:maxmem=-10
  • 上下界値のギャップによる停止
    上下界値のギャップが,指定した値を下回る場合に解の探索を停止します.
    ただし,gap =(上界値 – 下界値)です.gapは目的関数の実際の値に依存することにご注意ください.以下のエラーが出力されて止まります.
    実行可能解が求まってはじめて上下界値のギャップは意味を持ちますので,このエラーで停止した場合には必ず実行可能解の出力が成されます.初期状態では,設定はなされていません.
    大域的最適解から一定範囲の解が許容されている場合にはこのパラメータの設定によって,探索の手間を削減することができます.
    (NUOPT 45) B&B gap reaches under the limit.
    モデルファイルに記述する方法
    options.gaptol = 1.0e-2;
    パラメータファイルnuopt.prmに記述する方法
    branch:gaptol=1.0e-2
  • スレッド数の上限
    分枝限定法はマルチコア環境において並列処理を行うことにより,計算時間を短縮することができます.ユーザは分枝限定法が使用するスレッド数の上限を指定することができます.-1を指定すると,Numerical Optimizerが内部で適切なスレッド数を設定します.0あるいは1と設定した場合は,シングルスレッドの分枝限定法が動作します.分枝限定法の並列化を実行した場合,デフォルトの設定は2になります.なお,並列化を実行する場合「10.5分枝限定法・制約充足問題ソルバwcspの並列化」を参考に実行形式を作成する必要がございます.
    モデルファイルに記述する方法
    options.bbthreads = 2;
    パラメータファイルnuopt.prmに記述する方法
    branch:threads=2

 

 

上に戻る