これは CLRS 24.4-12 からの演習です (宿題ではなく、CLRS のすべての演習を解決しようとしています)。
b のすべての要素が実数値であり、すべてではないが一部の未知数 xi の指定されたサブセットが整数でなければならない場合に、差分制約の系 Ax ≤ b を解く効率的なアルゴリズムを与えてください。
すべての xi が整数の場合、b = floor(b) とし、Bellman-Ford アルゴリズムを使用して制約グラフの問題を解決するための最短経路を見つけることができますが、xi の一部が整数であり、一部が整数でない場合はどうでしょうか? 整数計画問題に似ていますが、整数計画問題は NP 困難です。この質問は制約が少なく、より効率的なアルゴリズムはありますか?
最初にベクトル b の最小絶対値を持つ要素を見つけ、それを C 倍して b のベクトルのすべての値を整数にします (たとえば、最小絶対値が 3.102 の場合、ベクトル b に 1000 を掛けることができます)。ベルマンフォード アルゴリズム 、最後に C で割ります !
良い。おい、これはアルゴリズム入門の演習だ。私自身の方法は、Bellman-Ford アルゴリズムを適応させることです。これは、基本的に、不等式に基づいて有向加重グラフを構築し、エッジを緩和するときに、整数のみをノードのキー値にできるようにすることです。うまくいくと思います。
線形最適化にも同様のことがあります。唯一の違いは、最小要件または最大要件がないことです。たぶん、いくつかの方法を適応させることができます。実数値の解から始めて、整数 xi を強制的に整数にするための制約を追加する Gomory アルゴリズムと、検索空間の大きな部分をできるだけ早く除外しようとする分枝限定アルゴリズムがあります。