一般流通問題に関して：
@ヘレンに同意します。下限の実際の使用を考えるのは直感的ではないかもしれませんが、それは満たさなければならない制約です。フローがゼロの場合でも、この制約を無視できるとは思えません。
フロー = 0 のケースは、より直感的な最大フローの問題に訴えます (@KillianDS が指摘したように)。その場合、ノードのペア間のフローがゼロの場合、「フロー合計の保存」に影響を与えることはできません。
下限が指定されていない場合 (フローが非負であると仮定)、ゼロ フローは結果に影響を与えることはできません。
- 制約に違反を導入することはできません
- 合計に影響を与えることはできません (ゼロ項が追加されるため)。
最小流量の実用的な例は、何らかの外部制約のために存在する可能性があります (関連する問題では、@Helen が指摘したように、少なくとも X 個の水が特定のパイプを通過する必要があります)。下限の制約は、特定のエッジが下限を持つようにフローを最小化する (上限を持つ最大化問題に最適な等価物を見つける) 等価双対問題からも発生する可能性があります。
特定の問題について：
固定された一連のタイム スロットでできるだけ多くのイベントを実行しようとしているようです (1 つのタイム スロットで 2 つのイベントが重複することはありません)。
特定のイベントに割り当てることができるタイムスロットのセットを考えてみましょう:
E1 -- { 9:10 }
E2 -- { 9:00 }
E3 -- { 9:20、9:30、9:40、9:50 }
E3 -- { 9:00、9:10、9: 20日9時30分}
そのため、タスクの割り当て (つまり、「オン」になっているエッジに付随するイベント) の数を最大化する必要があります。結果のセットは対ごとにばらばらです (つまり、割り当てられたタイムスロットが重複しません)。
これを解くことができれば、それを使用して最大集合パッキング問題を解くことができるため、これは NP 困難であると思います(つまり、最大集合パッキングはこれに縮小されます)。あなたの問題は整数線形計画法で解決できますが、実際には、これらの問題は貪欲な方法/分岐限定法でも非常にうまく解決できます。
たとえば、あなたの例の問題では。イベント E1 は E3 と「衝突」し、E2 は E3 と衝突します。E1 が割り当てられている場合 (オプションは 1 つしかない)、E3 の残りの可能な割り当ては 1 つだけです (後の割り当て)。この割り当てが E3 に割り当てられた場合、E2 の残りの割り当ては 1 つだけです。さらに、分断されたサブグラフ (リソースをめぐって競合する可能性がない一連のイベント) は、個別に解決できます。
私だったら、非常に単純な貪欲な解決策 (最初に可能な「スロット」の少ないタスクを割り当てる) から始め、それを分枝限定ソルバーのシードとして使用します (貪欲な解決策で 4 つのタスク割り当てが見つかった場合、割り当ての再帰サブツリーが 3 を超えることができない場合にバインドされます)。セット間のペアごとの交差のグラフを作成し、割り当てが行われたときに隣接するセットにのみ通知することで、パフォーマンスをさらに絞り出すこともできます。また、分岐と結合を続けながら割り当ての最高数を更新することもできます (これは正常だと思います)。したがって、早い段階で運が良ければ、すぐに収束します。
私はこれと同じ考えを使用して、特定された一連のペプチド (タンパク質片) を説明する最小のタンパク質のセットを見つけましたが、実際の問題には十分すぎることがわかりました. よく似た問題です。
最先端のパフォーマンスが必要な場合:
言い換えると、整数線形計画法は、この問題のほぼすべてのバリアントを実行できます。もちろん、非常に悪いケースでは遅いかもしれません (実際には、特にグラフがあまり密に接続されていない場合は、おそらくうまくいくでしょう)。そうでない場合は、通常の線形計画法の緩和によって ILP の解が近似され、一般にこの種の問題には非常に適しています。
お役に立てれば。
