線形計画法の緩和

数学において、（混合）整数線形計画の緩和は、各変数の整数制約を除去することによって生じる問題です。

例えば、0-1整数計画法では、すべての制約は次の形式になります。

${\displaystyle x_{i}\in \{0,1\}}$。

元の整数計画の緩和では、代わりに線形制約の集合を使用する。

${\displaystyle 0\leq x_{i}\leq 1.}$

結果として得られる緩和は線形計画法であるため、この名前が付けられています。この緩和手法は、NP 困難な最適化問題(整数計画法) を多項式時間で解決可能な関連問題(線形計画法) に変換します。緩和された線形計画法の解は、元の整数計画法の解に関する情報を取得するために使用できます。

集合被覆問題を考えてみましょう。この問題の線形計画法緩和は、1975年にLovászによって初めて検討されました。^{[1]この問題では、入力として}集合 族F = { S ₀、S _{1 、...}が与えられます。タスクは、できるだけ少ない集合で、} Fと同じ和集合を持つサブ族を見つけることです。

これを0-1整数計画として定式化するには、各集合S _iに対して、 S _{i が}選択されたサブファミリーに属する場合は値1をとり、属さない場合は値0をとる指示変数 x _iを形成する。次に、制約を満たす指示変数に値を割り当てることによって有効なカバーを記述することができる。

${\displaystyle \textstyle x_{i}\in \{0,1\}}$

（つまり、指定された指示変数値のみが許可される）そして、Fの和集合の各要素e _jについて、

${\displaystyle \textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1}$

（つまり、各要素がカバーされている）。最小セットカバーは、これらの制約を満たし、線形目的関数を最小化する指標変数の割り当てに対応する。

${\displaystyle \textstyle \min \sum _{i}x_{i}.}$

集合カバー問題の線形計画法緩和法は、各要素を含む集合の合計重みが少なくとも 1 になり、すべての集合の合計重みが最小化されるように入力集合に重みが割り当てられる分数カバーを記述します。

集合被覆問題の具体的な例として、インスタンスF = {{ a , b }, { b , c }, { a , c }} を考えてみましょう。最適な集合被覆は 3 つあり、それぞれに 3 つの集合のうち 2 つが含まれています。したがって、対応する 0–1 整数計画の目的関数の最適値は、最適被覆内の集合の数である 2 です。ただし、各集合に重み 1/2 が割り当てられ、目的関数の合計値が 3/2 になる分数解があります。したがって、この例では、線形計画緩和の値は、緩和されていない 0–1 整数計画の値とは異なります。

整数計画の線形計画緩和は、標準的な線形計画手法を使用して解くことができます。最適解ですべての変数が整数値を持つ場合、それは元の整数計画の最適解にもなります。ただし、一部の特殊なケース (たとえば、完全にユニモジュラな行列仕様の問題) を除いて、これは一般的には当てはまりません。

ただし、すべての場合において、線形計画の解の質は少なくとも整数計画の解の質と同程度です。これは、整数計画の解はいずれも有効な線形計画の解でもあるためです。つまり、最大化問題では、緩和された計画の値は元の計画の値以上になりますが、集合被覆問題などの最小化問題では、緩和された計画の値は元の計画の値以下になります。したがって、緩和により、整数計画の解に楽観的な境界が提供されます。

上で説明したセットカバー問題の例では、緩和の最適解の値は 3/2 ですが、緩和されていない整数計画の最適解の値は少なくとも同じ大きさであると推測できます。セットカバー問題の解の値は整数 (サブファミリーで選択されたセットの数) であるため、最適解の品質は、次に大きい整数である 2 と少なくとも同じ大きさである必要があります。したがって、この例では、緩和されていない問題とは異なる値であるにもかかわらず、線形計画緩和によって、元の問題の解の品質の下限が厳密に決まります。

線形計画法の緩和は、困難な最適化問題に対する近似アルゴリズムを設計するための標準的な手法です。このアプリケーションでは、整数計画法の解の質とその緩和法の解の質の最大比である整数ギャップという概念が重要です。最小化問題のインスタンスでは、実際の最小値 (整数問題の最小値) が で、緩和された最小値 (線形計画法の緩和法の最小値) が である場合、そのインスタンスの整数ギャップは です。最大化問題では、分数が逆になります。整数ギャップは常に 1 以上です。上記の例では、インスタンスF = {{ a , b }, { b , c }, { a , c }} は、整数ギャップが 4/3 であることを示しています。 ${\displaystyle M_{\text{int}}}$${\displaystyle M_{\text{frac}}}$${\displaystyle IG={\frac {M_{\text{int}}}{M_{\text{frac}}}}}$

通常、整数ギャップは近似アルゴリズムの近似比に変換されます。これは、近似アルゴリズムが、サイズ のすべての緩和された解に対して、最大でサイズ の整数解を見つける何らかの丸め戦略に依存しているためです(ここでRRは丸め比)。整数ギャップIGのあるインスタンスがある場合、すべての丸め戦略は、そのインスタンスで、サイズが少なくとも の丸められた解を返します。したがって、必ず です。丸め比RR は近似比の上限にすぎないため、理論上は実際の近似比はIGよりも低くなる可能性がありますが、これを証明するのは難しい場合があります。実際には、IG が大きいことは通常、線形計画法の緩和における近似比が悪い可能性があることを意味し、その問題には他の近似スキームを探す方がよい場合があります。 ${\displaystyle M_{\text{frac}}}$${\displaystyle RR\cdot M_{\text{frac}}}$${\displaystyle M_{\text{int}}=IG\cdot M_{\text{frac}}}$${\displaystyle RR\geq IG}$

集合被覆問題では、ロヴァースはn個の要素を持つインスタンスの整数ギャップがH _n、つまりn番目の調和数であることを証明した。この問題の線形計画法緩和は、ランダム化丸めの手法によって、緩和されていない元の集合被覆インスタンスの近似解に変換できる。^[2]各集合S _{i が}重みw _iを持つ分数被覆が与えられた場合、各 0–1 指示変数x _iの値がw _i  × (ln  n +1)の確率で 1 になり 、それ以外の場合は 0 になるようにランダムに選択する。すると、どの要素e _jも被覆されない確率 が 1/( e × n ) 未満になるため、一定の確率ですべての要素が被覆される。この手法で生成される被覆の合計サイズは、高い確率で (1+o(1))(ln n ) Wになる。ここで、 W は分数解の合計重みである。ヤングが1995年に示したように^[3]、このアルゴリズムのランダム部分と線形計画緩和の明示的な解を構築する必要性は、条件付き確率法を使用することで排除でき、残りのカバーされていない要素の最大数をカバーするセットを繰り返し選択する、ロヴァースがすでに知っていたセットカバーの決定論的貪欲アルゴリズムにつながります。この貪欲アルゴリズムは、ロヴァースがセットカバーの整数ギャップとして証明したのと同じH _n係数内でセットカバーを近似します。多項式時間近似アルゴリズムでは大幅に優れた近似比を達成できないと信じる強力な複雑性理論の理由があります。^[4]

同様のランダム化丸め手法と非ランダム化近似アルゴリズムは、Raghavan、Tompson、Young によって説明されているように、線形計画法の緩和と組み合わせて使用​​して、他の多くの問題に対する近似アルゴリズムを開発できます。

線形計画法は、近似値として使用されるだけでなく、困難な最適化問題に対する真の最適解を計算する 分岐限定アルゴリズムでも重要な役割を果たします。

最適解の一部の変数が小数値を持つ場合、分枝限定法タイプのプロセスを開始することができます。このプロセスでは、小数値変数の一部が 0 または 1 に固定された値を持つサブ問題を再帰的に解きます。このタイプのアルゴリズムの各ステップでは、元の 0–1 整数計画のサブ問題を検討します。このサブ問題では、一部の変数に 0 または 1 の値が割り当てられ、残りの変数はどちらの値も自由に取ることができます。サブ問題iでは、V _{i が}残りの変数の集合を表すものとします。プロセスは、変数値が割り当てられていないサブ問題を検討することから始まり、V ₀は元の問題の変数の集合全体です。次に、各サブ問題iに対して、次の手順を実行します。

1. 現在のサブ問題の線形計画法緩和の最適解を計算します。つまり、V _i内の各変数x _jについて、 x _{j が}0 または 1 であるという制約を、区間 [0,1] 内にあるという緩和された制約に置き換えます。ただし、すでに値が割り当てられている変数は緩和されません。
2. 現在のサブ問題の緩和されたソリューションが、これまでに見つかった最良の整数ソリューションよりも悪い場合は、再帰検索のこのブランチからバックトラックします。
3. 緩和されたソリューションのすべての変数が 0 または 1 に設定されている場合、それをこれまでに見つかった最良の整数ソリューションと比較してテストし、2 つのソリューションのうち最適なものを保持します。
4. それ以外の場合、緩和されたソリューションで小数値に設定される任意の変数をx _jとします。 x _jが 0 に設定されるサブ問題とx _jが 1 に設定されるサブ問題の 2 つを作成します。両方のサブ問題で、一部の変数への値の既存の割り当てが引き続き使用されるため、残りの変数のセットはV _i  \ { x _j } になります。両方のサブ問題を再帰的に検索します。

このタイプのアルゴリズムのパフォーマンスに関する理論的な限界を証明することは困難ですが、実際には非常に効果的です。

同じ目的関数と同じ実行可能解の集合を持つという点で同等である 2 つの 0–1 整数計画は、まったく異なる線形計画緩和を持つ場合があります。線形計画緩和は、すべての実行可能解を含み、他のすべての 0–1 ベクトルを除外する凸多面体として幾何学的に見ることができ、無限に多くの異なる多面体がこの特性を持ちます。理想的には、実行可能解の凸包を緩和として使用します。この多面体上の線形計画法は、元の整数計画の正しい解を自動的に生成します。ただし、一般に、この多面体は指数的に多くの面を持ち、構築が困難です。前述の集合被覆問題の緩和などの一般的な緩和は、凸包を厳密に含み、緩和されていない問題を解く 0–1 ベクトル以外の頂点を持つ多面体を形成します。

0–1 整数計画を解くための切断平面法は、 1954 年に巡回セールスマン問題に対してDantzig、Fulkerson、Johnson によって初めて導入され^[5]、1958 年に Gomory によって他の整数計画に一般化されました^[6]。この方法では、最終的に整数解が得られるまで解空間をより厳密に制約する一連の緩和を求めることにより、この可能な緩和の多様性を活用します。この方法は、与えられたプログラムの任意の緩和から開始し、線形計画ソルバーを使用して最適解を求めます。解がすべての変数に整数値を割り当てる場合、それは緩和されていない問題に対する最適解でもあります。それ以外の場合は、結果として得られる分数解を整数解の凸包から分離する追加の線形制約 (切断平面またはカット) が見つかり、この新しいより厳密に制約された問題に対してこの方法が繰り返されます。

この方法で使用されるカットを見つけるには、問題固有の方法が必要です。整数解の凸包のファセットを形成するカット面を見つけることが特に望ましいです。これらの面は、解空間を最も厳密に制約する面であるためです。整数解から分数解を分離するこのタイプのカット面が常に存在します。多面体組合せ論の枠組みの下で、さまざまなタイプの組み合わせ最適化問題に対してこれらのファセットを見つける方法について多くの研究が行われてきました。^[7]

関連する分岐切断法は、切断面法と分岐限定法を組み合わせたものです。どのサブ問題でも、切断面法を切断面が見つからなくなるまで実行し、その後、残っている小数変数の 1 つに分岐します。

• 分数彩色、グラフ彩色の線形計画法緩和。
• 緩和の解から元の問題の解を得るためのランダムな丸め。

• Aardal, Karen ; Weismantel, Robert (1997)、「多面体組み合わせ論: 注釈付き参考文献」、Annotated Bibliographies in Combinatorial Optimization (PDF)、Wiley。
• アグモン、シュムエル (1954)、「線形不等式の緩和法」、カナダ数学ジャーナル、6 : 382–392、doi : 10.4153/CJM-1954-037-2。
• ダンツィグ、ジョージ、フルカーソン、DR、ジョンソン、セルマー（1954）「大規模巡回セールスマン問題の解決」アメリカオペレーションズリサーチ協会誌、2（4）：393-410、doi：10.1287/opre.2.4.393。
• フェイジ、ウリエル(1998)、「集合被覆を近似するための ln nの閾値」、Journal of the ACM、45 (4): 634–652、CiteSeerX  10.1.1.70.5014、doi :10.1145/285055.285059。
• ゴモリー、ラルフ E. (1958)、「線形計画法の整数解法アルゴリズムの概要」、アメリカ数学会報、64 (5): 275–279、doi : 10.1090/S0002-9904-1958-10224-4。
• Lovász、László (1975)、「最適な積分カバーと分数カバーの比率について」、離散数学、13 (4): 383–390、doi : 10.1016/0012-365X(75)90058-8。
• Motzkin, TS ; Schoenberg, IJ (1954)、「線形不等式の緩和法」、Canadian Journal of Mathematics、6 : 393–404、doi : 10.4153/CJM-1954-038-x。
• ラガヴァン、プラバカール、トンプソン、クラーク D. (1987)、「ランダム化丸め: 証明可能な優れたアルゴリズムとアルゴリズム証明のための手法」、コンビナトリカ、7 (4): 365–374、doi :10.1007/BF02579324。
• Young, Neal E. (1995)、「線形計画法を解かずにランダムに丸める」、Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA)、Soda '95、pp. 170–178、ISBN 9780898713497。