問題タブ [network-flow]

特定のネットワーク フローに単一の最小カットがあるかどうかをチェックするアルゴリズムを探しています。

すべてのカットを検索し、最小カットが 1 つしかないかどうかを確認できるため、それが可能であることはわかっていますが、多項式で実行されるより効率的なアルゴリズムを見つけたいと考えています。

私を助けるために max-flow アルゴリズムを使用することを考えましたが、成功しませんでした。

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

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

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

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

SDN と NFV について研究しています。

ウィキペディアの NFV の概念では、次のように述べられています。一緒に通信サービスを作っていきます。」==>まず第一に考えることは、設備のコスト削減につながることです。

たとえば、実際の実装では、ルーターのようなネットワーク ノードを仮想化するにはどうすればよいでしょうか?

NFV は、静的な方法 (新しいルーターの購入) ではなく動的な方法 (ルーターの仮想化) でネットワークを拡張できるようにするために作成されました。次に、新しいルーターを現在の nextwork に適応させます。この場合、この実装に違いは見られません。仮想化されたルーターを実装するためにサーバーを購入することは、新しいルーターを購入するよりも安くはないからです。

誰かが私のためにこれを説明できますか、またはNFVの概念を間違って理解していますか?

ありがとう。

私は最適化問題を解いており、特にフロー ネットワークを最大化する必要があります。Sedgewick の本「Algorithms in Java, Third Edition, Part 5: Graph Algorithms」に掲載されている次のJava コードに基づいて、C++ コード ベースのフロー最大化アルゴリズムを実装しました。これは、頂点ベースの PREFLOW を使用してネットワーク フローを最大化します。プッシュ アルゴリズム:

私の実装は、そのコードに基づいて、次のネットワークを最大化できません 実行後のフローは次のよう になります この フローでは、フローの値は 8 ですが、最大値は 9 です。 私の理解では、アルゴリズムは本の説明と一致しています。しかし、私は2つの奇妙なものを見ます

1. ソースからの明示的なプリフロー フェーズはありません。これは に含まれwhile、述語P > 0 && v == sが true の場合に最初に 1 回だけ実行されます。多分これはコードを短くするために行われた
2. 私の理解と本書の言説によれば、シンクはキューに入ることはありません。ただし、高さが増加すると、コードは v != t であることを確認します。これには何か理由がありますか？

これは、C++ でのこのアルゴリズムの実装からの抜粋です。

私のコードと Sedgewick のコードの間に論理的な矛盾を見つけた人はいますか? 私のコード (およびおそらく Sedgewick も) が高さの増加を適切に処理していないという印象があります。しかし、私はその理由を理解することができません

最大化に失敗したネットワークの詳細な実行トレースを示します (トレースは while の最初の q.get() から始まります。括弧内の値は高さの値です。IN はノードへの着信フローです。OUT は来るもの。

例として、ライン

適格アーク 4104-->0 を参照します。ノード４１０４の高さは２であり、ノード０の高さは１である。「１を押す」という表現は、１単位のフローが目的のノード（０）に向かって押されることを意味する。行================は、各キュー抽出を区切ります。キューは FIFO であり、その状態は各処理の最後に出力されます。

多くの場合、ゼロ フロー ユニットがプッシュまたは削減されますが、宛先ノードがアクティブになることに注意してください。

これは実行トレースです

ノード A が 2 つのパケットをノード B に送信するネットワークがあり、セキュリティ上の理由から、これら 2 つのパケットがノード B に到達するために異なるパスを取得する必要があるとします。最大ネットワーク フローを使用して、特定のネットワークでそれが可能かどうかを判断するにはどうすればよいですか?

すべての容量を 1 と見なす必要があると思います。2 つのパケットが共通のエッジを通過する必要がある場合、最大ネットワーク フローは 1 になり、指定されたネットワークはこのタスクを実行できません。すべてのエッジの容量を考慮するのは本当ですか?

次の 2 つの質問を読みました: link1 link2

また、このウィキペディア

しかし、最小パスカバーを解決するために最大マッチング問題を解決する方法を理解できません。解が nm であることはわかっています。ここで、n は G の頂点の数、m は最大一致ですが、理由がわかりません。