0

CPLEX (Java を使用) で古典的なネットワーク フローの問題を解決しています。これには、制約 Ax=b (A はノード アークの発生行列、x はリンク フローの決定変数、b は与えられた右辺) が含まれています。1 次元での b の増減の影の賞に興味があります。

非縮退問題では、シャドウ プライスは制約 Ax=b の双対変数によって与えられます。しかし、私の問題は退化しています。したがって、1 つの最適解は、基底変数と非基底変数のいくつかの組み合わせで表すことができます。これらの組み合わせのそれぞれは、異なる双対変数を持つ必要があります。

これらのデュアルの少なくとも 1 つは、増加する b のシャドウ プライスを提供するはずです。別のデュアルは、減少する b のシャドウ プライスを提供します。（W.Powell（1989）によると：「線形ネットワークの感度結果のレビューと縮退の影響を減らすための新しい近似」）

私の質問は次のとおりです。CPLEX で LP を解き、双対の最初のセットを取得した後、別の双対のセットを取得できるように、CPLEX に基底変数と非基底変数のスワップを実行させるにはどうすればよいですか?

4

1 に答える 1

2

以下の議論全体は、双対問題に言及しています。

削減コストがゼロの非基本変数は、正のレベルで基底に入り、代替の最適解を形成できます。したがって、問題の最適な目的値が z* であり、c'x が関連する目的関数である場合、制約 を追加し c'x = z*、目的関数を別のものに変更し、シンプレックスに 1 回の反復を実行させ、反復することができます。2 回目以降の各反復では、(i) 新しい最適解を生成するか、(ii) 既に生成された最適解を生成する必要があります。この場合、目的関数を変更して反復できます。

この手法については、C API 関数を参照して、ここで説明します。

線形計画法では、非基本変数の削減コストがゼロであることは、別の最適な基底が存在することを示しています。さらに、ルーチン CPXgetgrad および CPXgetx を使用して、関連付けられたピボットが縮退しているかどうか (この場合、解の値は変更されませんが、基底は変化します) かどうか (この場合、解の値と基底の両方が変化します) を判別できます。スラック変数のコスト削減は、関連する双対変数の負の値であることに注意してください。さらに、ルーチン CPXaddrows は、別の最適解を列挙する簡単な方法を提供します。元の問題の最適な目的値が z* であり、c'x が関連する目的関数であるとします。CPXaddrows を使用して、次の制約を追加します。

c'x = z*

目的関数を他の目的に変更します。シンプレックスの反復制限を 1 (1) (または MIP の場合は解の制限を 1) に設定します。次に、問題を繰り返し最適化します。この修正された問題の実行可能な解はそれぞれ、元の問題の最適解です。この手順は、必ずしもすべてではありませんが、元の問題に対する代替の最適なソリューションを提供します。制約を追加するこの方法は、2 次目的をもつ連続モデルでも機能することに注意してください。一方、ゼロ削減コストで非基本変数を固定する方法は、非線形目的には容易に適用されません。CPLEX は凸二次計画法を解くため、二次目的関数に対する制約は、上記の線形目的関数の場合で説明したように、等式ではなく不等式でなければなりません。アプリケーションが代替最適解から別の代替最適解に移行する場合、削減コストが 0 (ゼロ) の非基本変数のみが変化する可能性があるため、ルーチン CPXgetdj および CPXgetpi を使用して代替最適解を列挙し、ゼロ以外の非基本構造変数とスラックを特定することもできます。コスト削減。次に、CPXchgbds を使用してこれらの構造変数を現在の値に修正し、CPXchgsense を使用してスラック変数を修正します。シンプレックス反復制限を 1 (1) に設定します。以前のように目的を変更します。また、すべてではありませんが、いくつかの代替最適解を列挙することもできます。ルーチン CPXgetdj および CPXgetpi を使用して非基本的な構造変数とスラックを非ゼロの削減コストで特定することにより、代替の最適解を列挙することもできます。次に、CPXchgbds を使用してこれらの構造変数を現在の値に修正し、CPXchgsense を使用してスラック変数を修正します。シンプレックス反復制限を 1 (1) に設定します。以前のように目的を変更します。また、すべてではありませんが、いくつかの代替最適解を列挙することもできます。ルーチン CPXgetdj および CPXgetpi を使用して非基本的な構造変数とスラックを非ゼロの削減コストで特定することにより、代替の最適解を列挙することもできます。次に、CPXchgbds を使用してこれらの構造変数を現在の値に修正し、CPXchgsense を使用してスラック変数を修正します。シンプレックス反復制限を 1 (1) に設定します。以前のように目的を変更します。また、すべてではありませんが、いくつかの代替最適解を列挙することもできます。

非常によく似た別の方法は、関連する目的関数の係数に小さなランダム ベクトルを追加し (つまり、目的を「摂動」させ)、問題を解決し、新しい頂点が古い頂点と同じではないことを確認し、次のようになることです。古い頂点と同じ目的関数値 (そうでない場合は、再び摂動して繰り返します)。この手法は、 Paul Rubinによるこの投稿でうまく説明されています。

MIP 問題についてCPLEXは、既に見つかった特定の数の解を保持する解プールと、populateさらに解を検索する関数 を提供します。この投稿(再び Paul Rubin によるもの) では、これが Java API でどのように機能するかを説明しています。

アップデート

以下のコメントのフォローアップ：

  1. 他の解決策があるとしても、固定されたままにするために最適な解決策が必要です。退化した場合にのみベースを変更したい。

目的がその最適値と等しくなければならないという制約を追加するため、目的関数の値は変わりません ( c'x = z*)。上記で「新しい最適解を生成する」と言うとき、最適な双対値の新しいセット、つまり別の最適な双対基底を指します。主解は同じままです (主問題が退化しており、主問題に複数の最適解が存在しない場合)。

  1. 基底を変更した後、双対変数を再評価したいと思います。c'x = z* を制約として追加すると、すべての双対が 0 に設定されます。

すべての双対がゼロに等しいという事実は、実装上の問題のように聞こえます。結果の LP が実行可能であり、有限の最適解が返されることを確認しましたか? また、上記のステートメントの最初の部分 (... 変数を変更した後) を理解しているかどうかもわかりません。(双対) 基底の変更は、定義上、双対変数の再評価です。問題がprimal degenerateの場合 (現在のケース)、複数の双対最適解が存在するため、双対空間で基底を変更すると、同じ最適解値と同じ主基底が得られます (問題に両方が含まれている場合を除く)。プライマルおよびデュアル縮退)。

  1. そもそも回避しようとしていることなので、解決を控えたいと思います。摂動bで問題を解決することにより、シャドウ価格を直接計算できます。

これは本当ですが、この場合、問題を解決する必要があります2 * n。ここで、nは のサイズです。 のb各コンポーネントを一度に解決する必要bがありますb - 1。b + 1

解決せずに探していることを実行できる方法を知りません.CPLEXの主な開発者であるTobias Achterbergによる関連投稿を見つけました。彼は本質的に同じ方法を説明しています。また、この論文では、LP を再度解決することにより、最適双対解から最適主解を回復します。問題のネットワーク フロー構造を利用すれば、解決せずに解決できる可能性がありますが、そのためには、その特定の問題用にカスタマイズされたアルゴリズムを構築する必要があります。私は数年前に多くのサイジング処方のために同様のことをしましたが、それには少しの努力が必要です.

これが役立つことを願っています！

于 2014-09-19T00:57:34.183 に答える