線形計画法

線形計画法( LP )は線形最適化とも呼ばれ、要件と目的が線形関係によって表される数学モデルで最良の結果 (最大利益や最小コストなど) を達成する方法です。線形計画法は、数理計画法 (数学的最適化とも呼ばれます) の特殊なケースです。

より正式には、線形計画法は、線形等式制約と線形不等式制約に従って、線形目的関数を最適化する手法です。その実行可能領域は凸多面体であり、これは有限個の半空間の交差として定義される集合であり、各半空間は線形不等式によって定義されます。その目的関数は、この多面体上で定義された実数値アフィン（線形）関数です。線形計画アルゴリズムは、この関数が最大（または最小）の値を持つ 多面体の点（存在する場合）を見つけます。

線形計画問題は、次のように 標準形式で表現できる問題である。

${\displaystyle {\begin{aligned}&{\text{ベクトルを見つける}}&&\mathbf {x} \\&{\text{最大化する}}&&\mathbf {c} ^{\mathsf {T}} \mathbf {x} \\&{\text{対象}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}$

ここで、 の成分は決定すべき変数であり、 は与えられたベクトルであり、 は与えられた行列です。 値が最大化される関数 (この場合) は目的関数と呼ばれます。 制約と は、目的関数が最適化される 凸多面体を指定します。${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {c} }$${\displaystyle \mathbf {b} }$${\displaystyle A}$${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} }$${\displaystyle A\mathbf {x} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \geq \mathbf {0} }$

線形計画法は、さまざまな研究分野に応用できます。数学では広く使用されており、程度は低いものの、ビジネス、経済学、一部の工学問題でも使用されています。線形計画法、固有方程式、フォン・ノイマンの一般均衡モデル、構造均衡モデルの間には密接な関係があります (詳細については、双対線形計画法を参照)。 ^{[1] [2] [3]線形計画法モデルを使用する業界には、運輸、エネルギー、通信、製造などがあります。線形計画法は、}計画、ルーティング、スケジュール、割り当て、設計 におけるさまざまなタイプの問題をモデル化するのに有効であることが証明されています。

線形不等式系を解く問題は、少なくともフーリエまで遡ります。フーリエは1827年に線形不等式を解く方法を発表し、^[4]フーリエ-モツキン消去法は彼にちなんで名付けられました。

1930 年代後半、ソ連の数学者レオニード・カントロヴィッチとアメリカの経済学者ワシリー・レオンチェフは、それぞれ独立して線形計画法の実用的応用を研究しました。カントロヴィッチは製造スケジュールに焦点を当て、レオンチェフは経済への応用を研究しました。彼らの画期的な研究は、何十年もの間ほとんど見過ごされていました。

転機は第二次世界大戦中に訪れました。線形計画法が重要なツールとして登場したのです。線形計画法は、輸送ロジスティクス、スケジュール、リソース割り当てなど、戦時中の複雑な課題に対処するために広く利用されました。線形計画法は、コストやリソースの可用性などの重要な制約を考慮しながらこれらのプロセスを最適化する上で非常に役立つことが証明されました。

当初は無名であったにもかかわらず、戦時中の成功により線形計画法は脚光を浴びるようになりました。第二次世界大戦後、この方法は広く認知され、オペレーションズ・リサーチから経済学まで、さまざまな分野の基礎となりました。1930年代後半のカントロヴィッチとレオンチェフの見過ごされていた貢献は、最終的に意思決定プロセスの最適化における線形計画法のより広範な受容と利用の基礎となりました。^[5]

カントロヴィッチの研究は当初ソ連では無視されていた。^[6]カントロヴィッチとほぼ同時期に、オランダ系アメリカ人の経済学者TCクープマンスが古典的な経済問題を線型計画法として定式化した。カントロヴィッチとクープマンスは後に1975年のノーベル経済学賞を共同受賞した。^[4] 1941年、フランク・ローレン・ヒッチコックも輸送問題を線型計画法として定式化し、後の単体法に非常によく似た解法を示した。^[7]ヒッチコックは1957年に亡くなっており、ノーベル記念賞は死後に授与されることはない。

1946年から1947年にかけて、ジョージ・B・ダンツィグは、米国空軍の計画問題に使用するための一般線形計画法の定式化を独自に開発しました。^[8] 1947年、ダンツィグは単体法も発明しました。これは、初めて、ほとんどの場合に線形計画法の問題を効率的に解決するものでした。^{[8]ダンツィグが単体法について議論するために}ジョン・フォン・ノイマンとの会合を手配したとき、フォン・ノイマンは、自分がゲーム理論で取り組んでいた問題が同等であることに気づき、すぐに双対性理論を推測しました。^[8]ダンツィグは、1948年1月5日に未発表のレポート「線形不等式の定理」で正式な証明を提供しました。^[6]ダンツィグの研究は1951年に公開されました。戦後、多くの産業がそれを日常の計画に応用しました。

ダンツィグの最初の例は、70 人の人材を 70 の仕事に割り当てる最適な方法を見つけることでした。最適な割り当てを選択するためにすべての組み合わせをテストするために必要な計算能力は膨大です。可能な構成の数は、観測可能な宇宙の粒子の数を超えています。しかし、問題を線形計画法として設定し、単体アルゴリズムを適用することで、最適な解を見つけるのにほんの一瞬しかかかりません。線形計画法の背後にある理論により、確認しなければならない可能な解の数が大幅に削減されます。

線形計画問題は、1979年にレオニード・カチヤンによって多項式時間で解けることが初めて示されましたが^[9] 、この分野におけるより大きな理論的かつ実用的な進歩は、1984年にナレンドラ・カルマーカーが線形計画問題を解くための新しい内点法を導入したときに起こりました^{[10] 。}

線形計画法は、いくつかの理由から最適化の分野で広く使用されています。オペレーションズリサーチにおける多くの実際的な問題は、線形計画法の問題として表現できます。^[6]ネットワークフロー問題やマルチコモディティフロー問題などの線形計画法の特定の特殊なケースは、専門のアルゴリズムに関する研究が盛んに行われるほど重要であると考えられています。他の種類の最適化問題に対する多くのアルゴリズムは、線形計画法問題をサブ問題として解決することで機能します。歴史的に、線形計画法のアイデアは、双対性、 分解、凸性の重要性とその一般化など、最適化理論の中心的な概念の多くに影響を与えてきました。同様に、線形計画法はミクロ経済学の初期の形成に多用され、現在は計画、生産、輸送、技術などの企業経営に活用されています。現代の経営問題は常に変化していますが、ほとんどの企業は限られたリソースで利益を最大化し、コストを最小化したいと考えています。Google も線形計画法を使用して YouTube 動画を安定化しています。^[11]

標準形式は、線形計画問題を記述する通常の最も直感的な形式です。次の 3 つの部分で構成されます。

• 最大化される線形（またはアフィン）関数

例えば${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• 次の形式の問題の制約

例えば

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}$

• 非負の変数

例えば

${\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}$

この問題は通常、行列形式で表現され、次のようになります。

${\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

最小化問題、代替形式に制約がある問題、負の変数を含む問題などの他の形式は、常に標準形式の同等の問題に書き換えることができます。

農家がL ヘクタールの農地を所有しており、そこに小麦か大麦、あるいはその両方を植えるとします。農家はFキログラムの肥料とPキログラムの農薬を所有しています。小麦 1 ヘクタールにはF ₁キログラムの肥料とP ₁キログラムの農薬が必要で、大麦 1 ヘクタールにはF ₂キログラムの肥料とP ₂キログラムの農薬が必要です。小麦の 1 ヘクタールあたりの販売価格をS _{1 、大麦の 1 ヘクタールあたりの販売価格を S 2 とします。小麦と大麦を植えた土地の面積をそれぞれ}x ₁とx ₂で表すと、 x ₁とx ₂の最適値を選択することで利益を最大化できます。この問題は、標準形式の次の線形計画問題で表現できます。

行列形式では、次のようになります。

最大化する${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

対象となる${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}$

線形計画問題は、単体法の共通形式を適用するために拡張形式に変換できます。この形式では、制約内の不等式を等式に置き換えるために非負のスラック変数が導入されます。問題は、次のブロック行列形式で記述できます。

最大化:${\displaystyle z}$

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$

${\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0}$

ここで、は新しく導入されたスラック変数、は決定変数、 は最大化される変数です。 ${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {x} }$${\displaystyle z}$

上記の例は、次の拡張形式に変換されます。

ここで、（非負の）スラック変数は、この例では未使用の面積、未使用の肥料の量、未使用の農薬の量を表します。 ${\displaystyle x_{3},x_{4},x_{5}}$

行列形式では、次のようになります。

最大化:${\displaystyle z}$

$${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}$$

主問題と呼ばれるすべての線形計画問題は、主問題の最適値の上限を提供する双対問題に変換できます。行列形式では、主問題は次のように表すことができます。

A x ≤ b、x ≥ 0 を条件としてc ^T x を最大化する。

対応する対称双対問題では、

A ^T y ≥ c、y ≥ 0 を条件としてb ^T y を最小化します 。

代わりとなる基本的な定式化は次のとおりです。

A x ≤ bを条件としてc ^T x を最大化する。

対応する非対称双対問題、

A ^T y = c、y ≥ 0を条件としてb ^T y を最小化します 。

双対性理論には、2 つの基本的な考え方があります。1 つは、(対称双対の場合) 双対線形計画の双対は、元の主線形計画であるという事実です。さらに、線形計画のすべての実行可能解は、その双対の目的関数の最適値に上限を与えます。弱い双対性定理は、任意の実行可能解における双対の目的関数値は、任意の実行可能解における主の目的関数値以上であることを述べています。強い双対性定理は、主に最適解x ^*がある場合、双対にも最適解y ^*があり、c ^T x ^* = b ^T y ^*であることを述べています。

線形計画法は、無限大または実行不可能になることもあります。双対理論によれば、主計画法が無限大の場合、弱双対定理により双対計画法は実行不可能になります。同様に、双対計画法が無限大の場合、主計画法は実行不可能になります。ただし、双対計画法と主計画法の両方が実行不可能になる可能性もあります。詳細とその他の例については、 双対線形計画法を参照してください。

被覆LP は次の形式の線形プログラムです。

最小化: b ^T y、

ただし、A ^T y ≥ c、y ≥ 0、

行列Aとベクトルbおよびcが非負となるようにします。

被覆 LP の双対はパッキング LPであり、次の形式の線形計画です。

最大化: c ^T x、

ただし、A x ≤ b、x ≥ 0、

行列Aとベクトルbおよびcが非負となるようにします。

被覆LPとパッキングLPは、一般的に組み合わせ問題の線形計画法緩和として現れ、近似アルゴリズムの研究で重要です。^[12]たとえば、集合パッキング問題、独立集合問題、マッチング問題のLP緩和はパッキングLPです。集合被覆問題、頂点被覆問題、支配集合問題のLP緩和も被覆LPです。

グラフの部分色付けを見つけることは、被覆 LP の別の例です。この場合、グラフの各頂点に 1 つの制約があり、グラフの 各独立セットに 1 つの変数があります。

相補的緩み定理を使用すると、主問題の最適解のみがわかっている場合でも、双対問題の最適解を得ることができます。定理は次のように述べます。

x  = ( x ₁ ,  x ₂ , ... ,  x _n ) が主実行可能で、y  = ( y ₁ ,  y ₂ , ... ,  y _m ) が双対実行可能であるとします。 ( w ₁ ,  w ₂ , ... ,  w _m ) が対応する主スラック変数を表し、 ( z ₁ ,  z ₂ , ... ,  z _n ) が対応する双対スラック変数を表すものとします。この場合、xとy がそれぞれの問題に対して最適であるためには、次の条件を満たす必要があります。

• x _j z _j  = 0、j  = 1, 2, ...,  n、および
• w _i y _i  = 0、ただしi  = 1, 2, ... ,  m。

したがって、主変数のi番目のスラック変数がゼロでない場合、双対変数のi番目の変数はゼロになります。同様に、双対変数のj番目のスラック変数がゼロでない場合、主変数のj番目の変数はゼロになります。

この最適性の必要条件は、かなり単純な経済原理を伝えています。標準形式 (最大化時) では、制約された基本リソースに余裕がある場合 (つまり、「残り物」がある場合)、そのリソースの追加量は価値がなくなります。同様に、二重 (影) 価格の非負制約要件に余裕がある場合 (つまり、価格がゼロでない場合)、供給が不足している (「残り物」がない) 必要があります。

幾何学的には、線形制約は凸多面体である実行可能領域を定義します。線形関数は凸関数であり、すべての局所最小値は大域最小値であることを意味します。同様に、線形関数は凹関数であり、すべての局所最大値は大域最大値であることを意味します。

最適解が存在する必要はありません。それには 2 つの理由があります。まず、制約が矛盾している場合、実行可能な解は存在しません。たとえば、制約x  ≥ 2 とx  ≤ 1 を同時に満たすことはできません。この場合、LP は実行不可能であると言えます。2 番目に、多面体が目的関数の勾配の方向に無制限である場合 (目的関数の勾配は目的関数の係数のベクトルです)、目的関数の有限値よりも優れた結果を得ることが常に可能であるため、最適値は達成されません。

それ以外の場合、実行可能解が存在し、制約セットが有界であれば、線形関数は凸関数と凹関数の両方であるため、凸関数の最大原理によって（あるいは、凹関数の最小原理によって）制約セットの境界上で最適値が常に達成されます。ただし、問題によっては最適解が明確に区別されるものもあります。たとえば、線形不等式システムの実行可能解を見つける問題は、目的関数がゼロ関数（つまり、どこでも値ゼロを取る定数関数）である線形計画問題です。目的関数がゼロ関数であるこの実行可能性問題では、2 つの異なる解がある場合、解のすべての凸組み合わせが解になります。

多面体の頂点は、基本実行可能解とも呼ばれます。この名前を選んだ理由は次のとおりです。d を変数の数とします。すると、線形不等式の基本定理は、（実行可能な問題の場合）LP 実行可能領域のすべての頂点x ^{*に対して、LP からの}d個（またはそれ以下）の不等式制約のセットが存在し、それらのd個の制約を等式として扱うと、唯一の解はx ^*であることを意味します。これにより、LP 解の連続体ではなく、すべての制約のセットの特定のサブセット（離散セット）を調べることによって、これらの頂点を調べることができます。この原理は、線形計画を解くための 単体アルゴリズムの基礎となっています。

1947 年にジョージ ダンツィグが開発したシンプレックスアルゴリズムは、多面体の頂点で実行可能な解を構築し、多面体のエッジ上のパスに沿って、目的関数の値が減少しない頂点まで進み、確実に最適値に到達するまで LP 問題を解決します。多くの実際の問題では、「失速」が発生します。つまり、目的関数が増加せずに多くのピボットが行われます。^{[13] [14]}まれな実際の問題では、シンプレックス アルゴリズムの通常のバージョンが実際に「循環」する場合があります。^[14]循環を回避するために、研究者は新しいピボット ルールを開発しました。^[15]

実際には、シンプレックスアルゴリズムは非常に効率的であり、サイクリングに対する特定の予防措置を講じれば、グローバル最適解を見つけることが保証されます。シンプレックスアルゴリズムは、「ランダム」問題を効率的に、つまり3乗のステップで解決することが証明されており、^[16]これは実際の問題での挙動に似ています。^{[13] [17]}

しかし、単体法は最悪の場合の動作が悪くなります。KleeとMintyは、単体法が問題のサイズに対して指数関数的にステップ数を必要とする線形計画問題のファミリーを構築しました。^{[13] [18] [19]実際、線形計画問題が}多項式時間で解けるかどうか、つまり複雑性クラスがPであるかどうかは長い間わかっていませんでした。

ダンツィグの単体法と同様に、クリスクロス法は基底間でピボットする基底交換アルゴリズムである。しかし、クリスクロス法は実行可能性を維持する必要はなく、実行可能な基底から実行不可能な基底にピボットすることができる。クリスクロス法は線形計画法の多項式時間計算量を持たない。どちらのアルゴリズムも、最悪の場合、次元 Dの（摂動された）立方体、つまりクリー・ミンティ立方体の2 ^Dコーナーすべてを訪れる。^{[15] [20]}

多面体集合上の頂点間の辺を走査して最適解を見つける単体アルゴリズムとは対照的に、内点法は実行可能領域の内部を移動します。

これは、線形計画法で初めて発見された最悪ケースの 多項式時間アルゴリズムです。n個の変数を持ち、 L 個の入力ビットでエンコードできる問題を解くために、このアルゴリズムは時間で実行されます。^[9] Leonid Khachiyan は、 1979 年に楕円体法を導入して、この長年の計算量問題を解決しました。収束解析には (実数の) 先行例があり、特にNaum Z. Shorによって開発された反復法や、 Arkadi Nemirovski と D. Yudin による近似アルゴリズムがあります。 ${\displaystyle O(n^{6}L)}$

カチヤンのアルゴリズムは、線形計画法の多項式時間解法を確立する上で画期的な重要性を持っていました。このアルゴリズムは計算上の画期的進歩ではありませんでした。なぜなら、特別に構築された線形計画法の族を除いて、単体法の方が効率的だからです。

しかし、カチヤンのアルゴリズムは、線形計画法における新たな研究分野に影響を与えました。1984年、N. カルマーカーは線形計画法のための射影法を提案しました。カルマーカーのアルゴリズム^[10]は、カチヤン^[9]の最悪ケース多項式境界（を与える）を改良しました。カルマーカーは、彼のアルゴリズムは実用的なLPでは単体法よりもはるかに高速であると主張し、この主張は内点法に大きな関心を呼びました。^[21]カルマーカーの発見以来、多くの内点法が提案され、分析されてきました。 ${\displaystyle O(n^{3.5}L)}$

1987年、ヴァイディアは時間内で実行されるアルゴリズムを提案した。^[22]${\displaystyle O(n^{3})}$

1989年、ヴァイディアは時間内で実行されるアルゴリズムを開発した。 ^[23]正式に言えば、このアルゴリズムは最悪の場合、制約の数、変数の数、ビットの数などの算術演算を実行する。 ${\displaystyle O(n^{2.5})}$${\displaystyle O((n+d)^{1.5}nL)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle L}$

2015年に、リーとシドフォードは線形計画法が時間内に解けることを示しました。^[24]ここで、はソフトO表記を表し、は非ゼロ要素の数を表し、最悪の場合でも をとります。 ${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$${\displaystyle {\tilde {O}}}$${\displaystyle nnz(A)}$${\displaystyle O(n^{2.5}L)}$

2019年、Cohen、Lee、Songは実行時間を に改善し、は行列乗算の指数であり、は行列乗算の双対指数です。^[25]は（大まかに言えば）行列を行列で時間内に乗算できる最大の数として定義されます。Lee、Song、Zhangによるフォローアップの研究では、彼らは別の方法で同じ結果を再現しています。^[26]これら2つのアルゴリズムは、およびの場合でも変わりません。Jiang、Song、Weinstein、Zhangによる結果はに改善されました。^[27]${\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}$${\displaystyle \omega }$${\displaystyle \alpha }$ ${\displaystyle \alpha }$${\displaystyle n\times n}$${\displaystyle n\times n^{\alpha }}$${\displaystyle O(n^{2})}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle \omega =2}$${\displaystyle \alpha =1}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle {\tilde {O}}(n^{2+1/18}L)}$

現在の見解では、単体法と内点法の優れた実装の効率は、線形計画法の日常的な応用においては同等である。しかし、特定の種類の LP 問題では、ある種類のソルバーが他の種類よりも優れている場合があり (場合によってははるかに優れている)、内点法と単体法によって生成される解の構造は大きく異なり、後者のほうがアクティブ変数のサポート セットが小さいのが一般的である。^[28]

線形計画法の理論には未解決の問題がいくつかあり、その解決は数学における根本的な進歩を意味し、大規模な線形計画法を解く能力の大きな進歩となる可能性があります。

• LP は強多項式時間アルゴリズムを許容しますか?
• LP は、厳密に補完的なソリューションを見つけるための強力な多項式時間アルゴリズムを許可しますか?
• LP は、実数 (単位コスト) 計算モデルで多項式時間アルゴリズムを許可しますか?

スティーブン・スメールは、この密接に関連した一連の問題を、21 世紀の18 の最大の未解決問題のうちの 1 つとして挙げています。スメールの言葉を借りれば、問題の 3 番目のバージョンは「線形計画理論の主要な未解決問題」です。楕円体法や内点法など、線形計画を弱多項式時間で解くアルゴリズムは存在しますが、制約の数と変数の数に関して強多項式時間のパフォーマンスを可能にするアルゴリズムはまだ見つかっていません。そのようなアルゴリズムの開発は、理論的に大きな関心を集め、おそらく大規模な LP の解決においても実用的な利点をもたらすでしょう。

ヒルシュ予想は最近、高次元では反証されましたが、以下の疑問はまだ残っています。

• 多項式時間の単体変種につながるピボット規則はありますか?
• すべての多面体グラフは多項式的に制限された直径を持ちますか?

これらの質問は、単体法のような方法のパフォーマンス分析と開発に関連しています。単体法アルゴリズムは、理論的には指数時間のパフォーマンスであるにもかかわらず、実際には非常に効率的であることから、多項式時間または強多項式時間で実行される単体法のバリエーションが存在する可能性が示唆されています。特に、LP が強多項式時間で解決できるかどうかを判断する方法として、そのようなバリエーションが存在するかどうかを知ることは、実用的および理論的に非常に重要な意味を持ちます。

単体アルゴリズムとその変種は、エッジ追跡アルゴリズムのファミリーに属し、多面体のエッジに沿って頂点から頂点へ移動することで線形計画問題を解くことからそのように名付けられています。つまり、その理論的なパフォーマンスは、LP 多面体上の任意の 2 つの頂点間のエッジの最大数によって制限されます。結果として、多面体グラフの最大グラフ理論的直径を知ることに興味があります。すべての多面体は指数以下の直径を持つことが証明されています。ヒルシュ予想の最近の反証は、多面体が超多項式直径を持つかどうかを証明する第一歩です。そのような多面体が存在する場合、エッジ追跡変種は多項式時間で実行できません。多面体の直径に関する質問は、独立した数学的な関心事です。

単体ピボット法は、主（または双対）実行可能性を保存します。一方、クリスクロスピボット法は（主または双対）実行可能性を保存しません。主実行可能、双対実行可能、または主双対実行不可能基底を任意の順序で訪問する可能性があります。このタイプのピボット法は、1970年代から研究されてきました。^[29] 本質的に、これらの方法は、線形計画問題の下で配置多面体上の最短ピボットパスを見つけようとします。多面体グラフとは対照的に、配置多面体のグラフは直径が小さいことが知られており、一般的な多面体の直径に関する問題を解決せずに、強力に多項式時間のクリスクロスピボットアルゴリズムの可能性を可能にします。^[15]

未知の変数がすべて整数であることが求められる場合、その問題は整数計画法(IP) または整数線形計画法(ILP) 問題と呼ばれます。最悪の場合でも効率的に解くことができる線形計画法とは対照的に、整数計画法問題は多くの実際的な状況 (変数が制限されている場合) でNP 困難です。0 - 1 整数計画法または2 進整数計画法(BIP) は、変数が 0 または 1 (任意の整数ではなく) であることが求められる整数計画法の特殊なケースです。この問題も NP 困難として分類され、実際、決定バージョンはKarp の 21 の NP 完全問題の 1 つでした。

未知の変数の一部のみが整数である必要がある場合、この問題は混合整数 (線形) 計画(MIP または MILP) 問題と呼ばれます。これらは ILP プログラムよりもさらに一般的なため、一般に NP 困難でもあります。

ただし、IP 問題と MIP 問題には、効率的に解決可能な重要なサブクラスがいくつかあります。最も顕著なのは、制約行列が完全にユニモジュラであり、制約の右辺が整数である問題、またはより一般的には、システムが全双対整数(TDI) プロパティを持つ問題です。

整数線形計画法を解くための高度なアルゴリズムには以下のものがあります。

• 切断面法
• 分岐限定法
• 枝分かれして切る
• 支店と価格
• 問題に何らかの追加構造がある場合は、遅延列生成を適用できる可能性があります。

このような整数計画アルゴリズムについては、Padbergと Beasley によって説明されています。

実変数の線形計画法は、少なくとも 1 つの最適解が積分である、つまり整数値のみで構成される場合、積分であると言われます。同様に、多面体は、すべての有界実行可能目的関数cに対して、線形計画法が整数座標を持つ最適値を持つ場合、積分であると言われます。1977 年に Edmonds と Giles が観察したように、すべての有界実行可能積分目的関数cに対して、線形計画法の最適値が整数である 場合、多面体は積分であると同等に言えます。${\displaystyle P=\{x\mid Ax\geq 0\}}$${\displaystyle \{\max cx\mid x\in P\}}$${\displaystyle x^{*}}$${\displaystyle P}$${\displaystyle \{\max cx\mid x\in P\}}$

積分線形計画法は、問題の別の特徴付けを提供するため、組み合わせ最適化の多面体的側面において中心的な重要性を持っています。具体的には、どの問題でも、解の凸包は積分多面体です。この多面体が適切/コンパクトな記述を持つ場合、任意の線形目的の下で最適で実行可能な解を効率的に見つけることができます。逆に、線形計画緩和法が積分であることを証明できれば、それは実行可能な (積分) 解の凸包の望ましい記述になります。

文献全体で用語が一貫していないため、次の2つの概念を区別するように注意する必要があります。

• 前の節で述べた整数線形計画法では、変数は強制的に整数に制約されており、この問題は一般にNP困難である。
• このセクションで説明する積分線形計画法では、変数は整数に制限されませんが、連続問題には常に積分最適値（cが整数であると仮定）があることが何らかの方法で証明されており、すべての多項式サイズの線形計画法は多項式時間で解くことができるため、この最適値は効率的に見つけることができます。

多面体が積分であることを証明する一般的な方法の 1 つは、それが完全にユニモジュラであることを示すことです。整数分解特性や全双対積分性など、他の一般的な方法もあります。その他の特定のよく知られた積分 LP には、マッチング多面体、格子多面体、サブモジュラフロー多面体、および 2 つの一般化ポリマトロイド/ gポリマトロイドの交差などがあります(例: Schrijver 2003 を参照)。

許可ライセンス:

コピーレフト（相互）ライセンス:

MINTO（Mixed Integer Optimizer、分岐限定アルゴリズムを使用する整数計画ソルバー）はソースコードが公開されているが^[33]、オープンソースではない。

独自のライセンス:

• LP 問題の定式化に関するガイダンス
• 数理計画用語集
• 線形計画法に関するよくある質問
• 最適化ソフトウェアのベンチマーク