0

整数計画法を使用して、パレート最適解を列挙したいと考えています。これを行うために gurobi または同様の単​​目的整数計画法ソルバーを使用するアルゴリズムを実装したいと思いますが、そのようなアルゴリズムは知りません。誰かが効率的なフロンティアを列挙するためのアルゴリズムを提案してくれませんか?

4

2 に答える 2

1

PolySCIPは、多目的混合整数線形計画のためのアカデミックなオープンソース ソルバーです。独自のソルバーを実装したくない場合、または別のソルバーと比較したい場合。

于 2015-08-28T07:31:29.573 に答える
1

この回答では、次の形式の 2 目的の純粋な整数最適化問題のすべてのパレート効率的な解を列挙する方法について説明します。

min_x {g'x, h'x}
s.t.  Ax <= b
      x integer

アルゴリズム

目的の 1 つを最適化することからアルゴリズムを開始します (gここで使用します)。これは標準的な単目的整数最適化問題であるため、gurobi やその他の LP ソルバーで簡単に解くことができます。

min_x g'x
s.t.  Ax <= b
      x integer

P最終的にすべてのパレート効率的な解を含むセット を に初期化しますP = {x*}。ここx*で、 はこのモデルの最適解です。2 番目に小さいg'x値と改善されたh'x値を持つ効率的なフロンティアの次のポイントを取得するには、モデルに次の制約を追加できます。

  1. 実行可能なソリューションのセットから削除x*します (これらのx != x*制約の詳細は、回答の後半で提供されます)。
  2. 次の制約を追加します。h'x <= h'x*

解決する必要がある新しい最適化モデルは次のとおりです。

min_x g'x
s.t.  Ax <= b
      x != x* for all x* in P
      h'x <= h'x* for all x* in P
      x integer

繰り返しますが、これは単一目的の整数最適化モデルであり、gurobi または別のソルバーで解くことができます (x != x*制約をモデル化する方法に関する以下の詳細に従えば)。このモデルを繰り返し解いて、最​​適解を に追加するとP、解は次第に大きな (悪い)g'x値になり、徐々に小さな (良い)h'x値になります。最終的に、モデルは実行不可能になります。つまり、パレート フロンティア上にポイントが存在しなくなり、アルゴリズムは終了します。

この時点で、 と の解のペアがいくつか存在する可能性があります。このx, y場合、は と によって支配され、除去することができます。この方法でフィルタリングした後、セットは完全なパレート効率的フロンティアを表します。Pg'x = g'yh'x > h'yxyP

x != x*制約

残っているのは、フォーム の制約をモデル化することだけです。x != x*ここで、xとx*は整数変数の n 次元ベクトルです。1 次元であっても、これは非凸制約です (詳細はこちらを参照)。そのため、制約をモデル化するのに役立つ補助変数を追加する必要があります。

最適化モデルに格納されているn変数 (まとめて と表記x) をx_1, x_2, ..., x_n、同様に の変数値を と表記x*しx*_1, x*_2, ..., x*_nます。y_1, y_2, ..., y_nモデルに新しいバイナリ変数を追加できます。ここで、y_iは のときに 1 に設定されx_i > x*_iます。x_iとは整数値であるためx*_i、これは と言うのと同じであり、これx_i >= x*_i + 1は次の制約で実装できます (Mは大きな定数です)。

x_i - x*_i >= 1 - M(1-y_i) for all i = 1, ..., n

同様に、新しいバイナリ変数z_1, z_2, ..., z_nをモデルに追加できます。ここで、z_iは のときに 1 に設定されx_i < x*_iます。x_iとは整数値であるためx*_i、これは と言うのと同じであり、これは次の大きな制約x_i <= x*_i - 1で実装できます。M

x_i - x*_i <= -1 + M(1-z_i) for all i = 1, ..., n

yまたは変数の少なくとも 1 つが設定されている場合、制約が満たされzていることがわかります。x != x*したがって、次のように置き換えることができますx != x*。

y_1 + y_2 + ... + y_n + z_1 + z_2 + ... + z_n >= 1

つまり、各制約は、バイナリ変数と制約をモデルにx != x*追加することで処理できます。ここで、 は元のモデルの変数の数です。2n2n+1n

于 2015-08-26T04:53:34.450 に答える