問題タブ [branch-and-bound]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c - CPLEX ジェネリック コールバック、カット分離用のノード LP
CPLEX 12.10 の C API を介して汎用コールバック フレームワークを使用して、分岐カット アルゴリズムをセットアップしています。
各ノードで、分離問題は現在のノード LP に基づいており、違反した場合は現在のノードのすべての子ノードに追加されるローカルに有効なカットを検出します。
私の理解では、現在のノード LP の情報は、一般的なコールバックではすぐに利用できません。ただし、子ノードでより良いカットを生成するために、親ノード用に生成されたカットを使用したいと思います。
どのカットがすべてのノードで生成されるかについて簿記を行う必要がありますか?それとも、CPLEX 機能を使用してこの情報を何らかの方法で渡すことができますか? 生成されたすべてのカットを追跡することが唯一の可能性である場合、CPLEX が異なるスレッドから異なるノードでコールバックを呼び出す場合、このブックキーピングをスレッドセーフにするにはどうすればよいでしょうか?
scheduling - 変数分岐と制約分岐
変数分岐と制約分岐 (ライアンとフォスター) の違いは何ですか?
私は記事を読んでいました：
DM Ryan 著「航空機乗務員名簿における大規模な一般化集合分割問題の解決」 (J. Op1 Res. Soc. Vol. 4)
セット分割問題として定式化された乗組員のスケジューリングまたは看護師の勤務表の問題とまったく同じことが私には思えます。
どちらの分岐方法も 1 つの変数で分岐しますが、違いは何ですか?
SCIP を使用して Python で Branch-and-Price を実装しようとしています。
algorithm - 巡回セールスマン問題を解くとき、分枝限定アルゴリズムは力ずくのアルゴリズムよりもどのように高速ですか?
巡回セールスマン問題を解決するために分岐限定アルゴリズムがどのように機能するかは理解していますが、このアルゴリズムがブルート フォースよりもどのように高速であるかを理解するのに苦労しています。私の見方では、あなたは最終的にすべての道を通り抜けます。B&B アルゴリズムがすべてのパスをブルート フォーシングするよりも高速な例を誰かが示すことができますか?