問題タブ [operations-research]

私は C++ で CPLEX を使用して、ハブの場所の問題である MIP を解決しています。最近、問題が確かに実行可能であるにもかかわらず、CPLEX が実行不可能と考える非常に正確な入力セット (つまり、CPXMIP_INFEASIBLE) を見つけました。この問題は、MIP Presolve 中に CPLEX で発散するように見えます。通常、その時点で問題はヌル問題に縮小されますが、実行不可能な入力セットには含まれません。

入力データをわずかに調整すると、CPLEX のソリューションを見つける機能が切り替わる可能性があることがわかりました。たとえば、250.242566 を 250.242567 に変更するか、各入力値を最も近い整数に丸めるだけでも、完全に有効なソリューションが得られます。

私が持っている 2 つのスラック制約を緩和することも解決策を可能にしますが、これらの制約は入力データを考慮して破られるべきではありません。解決後のこれらの制約変数の値は、約 0 ですが、わずかに負の値 (-0.7e-10 など) です。(値が 0 より大きいはずなので、これは疑わしいです。)

何が起こっている？私は無知です。精度に関連するいくつかの CPLEX 変数 (つまり、CPX_PARAM_NUMERICALEMPHASIS、CPX_PARAM_EPOPT、CPX_PARAM_EPMRK、CPX_PARAM_EPRHS) を調整しようとしましたが、何も役に立ちませんでした。入力データ自体はあまり精度を必要としません。入力の最小値は 1.412 で、最大値は 1520.984907 です。

アドバイスや提案をいただければ幸いです。

アップデート：

MIP の Presolve 中に、実行不可能な問題が実行可能な問題から分岐していることに気付きました。

両方の問題について CPXgetprestat をチェックすると、2 つの問題の間に見られる顕著な違いの 1 つは、pcstat ベクトルにあり、実行不可能なセットで 1 つの変数を集約できないことです (つまり、実行不可能な問題では値が 0 であるのに対し、実行可能な問題では -4 です)。 .

また、CPXgetprestat の ocstat および orstat ベクトルは、実行不可能な問題にゼロ以外の値をそれぞれ 1 つずつ持っています (実行可能な問題は、ヌル問題に縮小されているため、値はありません)。orstat[0] == 7 かつ ocstat[0] == 1 の場合、Presolve 前の問題の 7 行目と 1 番目の変数に何か注目すべき点があるということですか? これを確認するにはどうすればよいですか？

両方の問題で CPXwriteprob の出力を比較しましたが、問題を実行不可能にするために 0.0001 だけ変更した入力値以外に違いはありません。

AMPL を使用しており、非負の偏差変数 (s+ - s-) を持つモデルを入力する必要があります。

制約の例: (x - 5) = (s+ - s-)

MarxanとConsNetという 2 つの保全地域設計ツールの比較を行っています。どちらもメタヒューリスティック アルゴリズムを使用して、最小集合被覆問題のバージョンを解決します。Marxan はシミュレーテッド アニーリングを使用し、ConsNet はタブー検索を使用します。私のバックグラウンドは生物学ですが、メタヒューリスティクスを通じて最適化の概念のいくつかを理解できたと思います。

しかし、タブー検索について、まだわかっていないことが 2 つあります。1 つ目は、ローカル オプティマを回避する方法です。私はそれがその動きを元に戻すことができないことを知っています、そしてそれはそれが循環するのを止めます、しかし私はそれがそれを見つけたらそれが局所最適を残す理由を知りません. シミュレーテッド アニーリングがどのようにそれを行うかは理解できます - より悪い解決策を受け入れなくなるまで時間の経過とともに減少するより悪い解決策を受け入れる可能性がありますが、TS がどのようにそれを行うかはわかりません。

2 番目の問題は、ConsNet のマニュアルに次の記述があることです。

検索は完全に決定論的ですが、ソリューション アーカイブの現在の状態または目標の現在の状態に基づいて、どのように進めるかを決定できます。

TS は常に決定論的ですか? いくつかの情報源を読んで、移動は SA のようにランダムである可能性があるという考えを得ました。しかし、「決定論的タブー検索」について話している論文がいくつかあります。決定論的タブー検索は、どの動きを取るべきかをどのように認識し、どのように局所最適を回避しますか? 時にはもっと悪い解決策を受け入れなければなりませんよね？

よろしくお願いします

私は、学習可能な任意のアルゴリズムを使用して、キャパシテイテッド ビークル ルーティング問題のソリューションを作成するという課題を設定されました。文献を簡単に検索したところ、タブー検索バリアントが最も成功しているようです。それらは学習アルゴリズムとして分類できますか、それともローカル検索の亜種にすぎませんか?

cplex モデル (Java 内) でいくつかの変数を定義します。これらの変数は[0,1]に制限されます。として： Model.numVar(0, 1, IloNumVarType.Float, "X(" + i+ ")");

しかし、最終的なソリューションでは、これらの変数はこの範囲外の値を取得します。( -1.7、1.3 など)。助けてください。

この問題を解決するにはあなたの助けが必要です。一連のタスクがあり、各タスクには実行時間があります。2 種類の制約があります。最初のタイプは、タスク間の優先関係です。2 番目の制約タイプでは、一連のタスクを同時に実行できます。例：6つのタスクと次のエッジ（T1、T2）、（T2、T3）、（T4、T3）、（T4、T5）、および（T6、T5）を持つグラフGがあります。T1、T4 は一緒に実行でき、T1、T6 も実行できますが、T4、T6 は実行できないとします。各タスクの実行時間を考慮します。いくつかのタスクの並列実行を考慮して、タスク間の優先関係を満たし、スケジュールの長さを最小限に抑えるスケジュールを見つける方法。

グラフ G= (V, E) にいくつかの制約があるソース ノード s から宛先ノード t への Max-flow を使用してk (k が指定されている) パスを見つけようとしています。V の異なるサブセット A_i が与えられると、1 つのサブセットは 1 つまたは複数のノードを持つことができます。問題は、1 つのパスでのみ 1 つのサブセットを使用できることです。私はこのコードを使用しています

このコードで各サブセットを追加するにはどうすればよいですか (つまり、パス 1 でサブセット A_1 を使用すると、他のパスに A_1 を再度使用できなくなりますか?私は Java が初めてです。問題をアップロードしようとしました)写真ですが、私はこの面が初めてなのでできませんでした. ありがとう