線形計画法

3つの変数を持つ問題の閉じた実行可能領域は、凸多面体です。目的関数の固定値を与える面は平面です（図示せず）。線形計画問題は、多面体上で可能な限り最高の値を持つ平面上の点を見つけることです。

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

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

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

{\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}

ここで、の成分は決定されるべき変数であり、は与えられたベクトルであり、は与えられた行列です。値が最大化される関数（この場合）は目的関数と呼ばれます。制約とは、目的関数が最適化される凸多面体を指定します $\mathbf {x}$ $\mathbf {c}$ $\mathbf {b}$ $A$ $\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$ $A\mathbf {x} \leq \mathbf {b}$ $\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つの部分で構成されます。

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

例

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

次の形式の問題制約

例

{\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}}

非負変数

例

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

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

\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ヘクタールあたりには}F1キログラムの肥料とP1キログラムの農薬が必要であり、大麦₁ヘクタールあたりにはF2キログラムの肥料とP2キログラムの農薬が必要です。S1_を小麦の₁ヘクタールあたりの販売価格、S2_を大麦の_{1ヘクタール}_あたりの販売価格とします。小麦と大麦が栽培されている土地の面積をそれぞれx1と_{x2とすると、}x1とx2の最適な値_を選択することで利益を最大化できます。この問題_は、標準形の次の線形計画問題で表すことができます。

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

最大化

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

条件：

{\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}}.

拡張形式（スラック形式）

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

最大化：

z

{\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}}

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

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

例

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

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

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

最大化：

z

{\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 ^Txを最大化する

対応する対称双対問題において、

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

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

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

対応する非対称双対問題において、

A ^Ty = c、y ≥ 0を条件として、 b ^Ty を最小化する

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

線形計画法は、非有界または実行不可能になることもあります。双対理論によれば、主計画法が非有界であれば、弱双対定理により双対計画法は実行不可能になります。同様に、双対計画法が非有界であれば、主計画法は実行不可能でなければなりません。ただし、双対計画法と主計画法の両方が実行不可能になる可能性もあります。詳細といくつかの例については、双対線形計画法を参照してください。

バリエーション

被覆／パッキング双対性

被覆線形計画法は、次の形式の線形計画法です。

b ^Ty を最小化する

ただし、 A ^Ty ≥ c、y ≥ 0 を条件とする

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

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

最大化: c ^Tx

ただし、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番目のスラック変数が0でない場合、双対変数のi番目の変数は0になります。同様に、双対変数のj番目のスラック変数が0でない場合、主変数のj番目の変数は0になります

この最適性の必要条件は、かなり単純な経済原理を表しています。標準的な形式（最大化の場合）では、制約された基本資源に余裕がある場合（つまり、「残り物」がある場合）、その資源の追加量は価値がなくなります。同様に、双対（影）価格の非負性制約要件に余裕がある場合、つまり価格がゼロでない場合、供給が不足している（「残り物」がない）必要があります。

理論

最適解の存在

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

最適解は、2つの理由から必ずしも存在するとは限りません。第一に、制約条件が矛盾する場合、実行可能な解は存在しません。例えば、制約条件x ≥ 2 とx ≤ 1 を同時に満たすことはできません。この場合、LP は実行不可能であると言います。第二に、多面体が目的関数の勾配の方向に有界でない場合（目的関数の勾配は目的関数の係数のベクトルです）、目的関数の任意の有限値よりも良い結果を得ることが常に可能であるため、最適値は達成されません。

多面体の最適な頂点（および光線）

そうでない場合、実行可能解が存在し、制約集合が有界である場合、線形関数は凸関数と凹関数の両方であるため、凸関数の場合は最大原理（または、凹関数の場合は最小原理）により、制約集合の境界上で最適値は常に達成されます。ただし、問題によっては異なる最適解を持つ場合があります。例えば、線形不等式連立方程式の実行可能解を見つける問題は、目的関数が零関数（つまり、どこでも値零を取る定数関数）である線形計画問題です。目的関数が零関数であるこの実行可能性問題では、2つの異なる解が存在する場合、解のすべての凸組み合わせが解となります

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

アルゴリズム

基底交換アルゴリズム

ダンツィグの単体アルゴリズム

1947年にジョージ・ダンツィグによって開発された単体アルゴリズムは、多面体の頂点で実行可能解を構築し、多面体の辺上の経路に沿って目的関数の値が減少しない頂点まで進み、確実に最適解に到達するまでLP問題を解きます。多くの実用的な問題では、「ストール」が発生します。つまり、目的関数が増加することなく多くのピボットが行われます。^[13]^[14]まれな実用的な問題では、単体アルゴリズムの通常のバージョンが実際に「循環」する場合があります。^[14]循環を回避するために、研究者は新しいピボット規則を開発しました。^[15]

実際には、単体アルゴリズムは非常に効率的であり、循環に対する特定の予防措置を講じれば、大域的最適解を見つけることが保証されます。単体アルゴリズムは「ランダム」問題を効率的に、つまり3乗のステップで解くことが証明されており^[16] 、これは実用的な問題における動作と同様です。^[13]^[17]

しかし、単体法は最悪の場合の挙動が悪くなります。クレーとミンティは、単体法が問題の規模に比例してステップ数を増やす線形計画問題の族を構築しました。^[13]^[18]^{[19]実際、線形計画問題が}多項式時間で解けるかどうか、つまり複雑性クラスPかどうかは、しばらくの間知られていませんでした。

クリスクロスアルゴリズム

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

内点法

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

カチヤンに従う楕円体アルゴリズム

これは、線形計画法においてこれまでに発見された最初の最悪ケースの多項式時間アルゴリズムです。n個の変数を持ち、 L個の入力ビットでエンコードできる問題を解くために、このアルゴリズムは実行時間で実行されます。^[9]レオニード・カチヤンは、1979年に楕円体法の導入により、この長年の計算量問題を解決しました。収束解析には（実数の）先行例があり、特にナウム・Z・ショアによって開発された反復法と、アルカディ・ネミロフスキーとD・ユディンによる近似アルゴリズムがあります。 $O(n^{6}L)$

カルマーカーの射影アルゴリズム

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

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

ヴァイディアの87アルゴリズム

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

ヴァイディアの89アルゴリズム

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

入力スパース時間アルゴリズム

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

現在の行列乗算時間アルゴリズム

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

内点法と単体アルゴリズムの比較

現在、線形計画法の日常的な応用においては、単体法と内点法の適切な実装の効率は同程度であると考えられています。しかし、特定の種類の線形計画問題では、ある種類のソルバーが他の種類よりも優れている場合（場合によってははるかに優れている場合）、また、内点法と単体法によって生成される解の構造が大きく異なり、後者ではアクティブ変数のサポートセットが通常小さくなる可能性があります。^[28]

未解決問題と最近の研究

コンピュータサイエンスにおける未解決問題

線形計画法は、強多項式時間アルゴリズムを許容するか？

コンピュータサイエンスにおけるその他の未解決問題

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

LPは強多項式時間アルゴリズムを許容するか？
LPは、厳密に相補的な解を見つけるための強多項式時間アルゴリズムを許容するか？
線形計画法は、実数（単位コスト）計算モデルにおいて多項式時間アルゴリズムを許容するか？

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

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

多項式時間の単体変種につながるピボットルールはありますか？
すべての多面体グラフは多項式的に有界な直径を持っていますか？

これらの疑問は、単体法のような手法の性能分析と開発に関連しています。単体法は、理論上は指数時間であるにもかかわらず、実際には非常に高い効率性を示しており、多項式時間、あるいは強多項式時間で実行される単体法のバリエーションが存在する可能性を示唆しています。そのようなバリエーションが存在するかどうかを知ることは、特に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年にエドモンズとジャイルズが観察したように、すべての有界実行可能積分目的関数cに対して、線形計画法の最適値が整数である場合、多面体は積分であると言えます $P=\{x\mid Ax\geq 0\}$ $\{\max cx\mid x\in P\}$ $x^{*}$ $P$ $\{\max cx\mid x\in P\}$

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

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

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

多面体が積分であることを証明する一般的な方法の1つは、それが全ユニモジュラであることを示すことです。整数分解性や全双対積分性など、他にも一般的な方法があります。その他のよく知られた積分線形計画法には、マッチング多面体、格子多面体、劣モジュラフロー多面体、2つの一般化ポリマトロイド/ g-ポリマトロイドの交差などがあります。例えば、Schrijver 2003を参照してください。

ソルバーとスクリプト（プログラミング）言語

許容ライセンス：

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

MINTO（Mixed Integer Optimizer、分岐限定法を使用する整数計画ソルバー）のソースコードは公開されています^[33]が、オープンソースではありません。

独自のライセンス：

参照

注釈

^ フォン・ノイマン, J. (1945). 「一般経済均衡モデル」. The Review of Economic Studies . 13 (1): 1– 9. doi :10.2307/2296111. JSTOR 2296111.
^ ケメニー, JG; モルゲンシュテルン, O.; トンプソン, GL (1956). 「拡大経済のフォン・ノイマン・モデルの一般化」. Econometrica . 24 (2): 115– 135. doi :10.2307/1905746. JSTOR 1905746
^ Li, Wu (2019).一般均衡と構造ダイナミクス：新構造経済学の展望（中国語）. 北京：経済科学出版社. pp. 122– 125. ISBN 978-7-5218-0422-5。
^ ab Gerard Sierksma; Yori Zwols (2015).線形および整数最適化：理論と実践（第3版）. CRC Press. p. 1. ISBN 978-1498710169。
^ 「線形計画法｜定義と事実｜ブリタニカ」. www.britannica.com . 2023年11月20日閲覧
^ abc George B. Dantzig (1982年4月). 「線形計画法の起源についての回想」(PDF) . Operations Research Letters . 1 (2): 43– 48. doi :10.1016/0167-6377(82)90043-8. 2015年5月20日時点のオリジナルからのアーカイブ。
^ Alexander Schrijver (1998).線形計画法と整数計画法の理論. John Wiley & Sons. pp. 221– 222. ISBN 978-0-471-98232-6。
^ abc Dantzig, George B.; Thapa, Mukund Narain (1997).線形計画法. ニューヨーク: Springer. p. xxvii. ISBN 0387948333 OCLC 35318475
^ abc Leonid Khachiyan (1979). 「線形計画法のための多項式アルゴリズム」. Doklady Akademii Nauk SSSR . 224 (5): 1093–1096 .
^ ab Narendra Karmarkar (1984). 「線形計画法のための新しい多項式時間アルゴリズム」. Combinatorica . 4 (4): 373–395 . doi :10.1007/BF02579150. S2CID 7257867
^ M. Grundmann、V. Kwatra、I. Essa (2011). 「ロバストなL1最適カメラパスによる自動指示ビデオ安定化」CVPR 2011 (PDF) pp. 225– 232. doi :10.1109/CVPR.2011.5995525. ISBN 978-1-4577-0394-2. S2CID 17707171.
^ Vazirani (2001, p. 112)
^ ab Dantzig & Thapa (2003)
^ ab Padberg (1999)
^ abc 福田孔明;テルラキータマス(1997). Thomas M. Liebling; Dominique de Werra (編). 「クリスクロス法：ピボットアルゴリズムの新たな視点」数理計画シリーズB . 79 ( 1– 3): 369– 395. CiteSeerX 10.1.1.36.9373 . doi :10.1007/BF02614325. MR 1464775. S2CID 2794181.
^ Borgwardt (1987)
^ Todd (2002)
^ Murty (1983)
^ Papadimitriou & Steiglitz
^ Roos, C. (1990). 「クリスクロスシンプレックス法におけるTerlakyのピボット則の指数関数的例」.数理計画. シリーズA. 46 (1): 79– 84. doi :10.1007/BF01585729. MR 1045573. S2CID 33463483
^ Strang, Gilbert (1987年6月1日). 「Karmarkarのアルゴリズムと応用数学におけるその位置づけ」. The Mathematical Intelligencer . 9 (2): 4– 10. doi :10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.
^ Vaidya, Pravin M. (1987).算術演算を必要とする線形計画法のアルゴリズム. 第28回IEEEコンピュータサイエンス基礎シンポジウム. FOCS ${O}(((m+n)n^{2}+(m+n)^{1.5}n)L)$
^ Vaidya, Pravin M. (1989). 「高速行列乗算を用いた線形計画法の高速化」.第30回コンピュータサイエンス基礎シンポジウム. 30th Annual Symposium on Foundations of Computer Science. FOCS. pp. 332– 337. doi :10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1。
^ Lee, Yin-Tat; Sidford, Aaron (2015).線形計画法のための効率的な逆メンテナンスと高速アルゴリズム．FOCS '15 Foundations of Computer Science. arXiv : 1503.01752 .
^ Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018).現在の行列乗算時間で線形計画法を解く．第51回ACM計算理論シンポジウム．STOC'19. arXiv : 1810.07896 .
^ Lee, Yin-Tat; Song , Zhao; Zhang, Qiuyi (2019).現在の行列乗算時間で経験的リスク最小化を解く．学習理論会議．COLT'19. arXiv : 1905.04447
^ Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020).高速LPのための高速動的逆行列法. arXiv : 2004.07470 .
^ イレス、ティボル;タマス、テルラキー (2002)。「ピボットと内点法: 長所と短所」。欧州オペレーショナルリサーチジャーナル。140 (2): 170. CiteSeerX 10.1.1.646.3539。土井：10.1016/S0377-2217(02)00061-9。
^ Anstreicher, Kurt M.; Terlaky, Tamás (1994). 「線形計画法のための単調な積み上げ単体アルゴリズム」. Operations Research . 42 (3): 556– 561. doi : 10.1287/opre.42.3.556 . ISSN 0030-364X. JSTOR 171894.
^ 「lp_solve リファレンスガイド (5.5.2.5)」. mit.edu . 2023年8月10日閲覧.
^ 「外部言語インターフェース」 . 2021年12月3日閲覧.
^ 「lp_solve コマンド」 . 2021年12月3日閲覧
^ 「COR@L – リーハイ大学における計算最適化研究」. lehigh.edu
^ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf ミュンスター大学、混合モデル組立ラインの最適化モデルにおけるOptimJの使用
^ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 2011年6月29日アーカイブ、Wayback Machine繰り返しゲームの近似部分ゲーム完全均衡計算手法におけるOptimJの使用

参考文献

Kantorovich, LV (1940). 「いくつかの種類の極値問題を解く新しい方法」[いくつかの種類の極値問題を解く新しい方法]. Doklady Akad Sci SSSR . 28 : 211–214 .
FL Hitchcock:複数の供給源から多数の局所性への製品の分布、Journal of Mathematics and Physics, 20, 1941, 224–230
GB Dantzig:線形不等式に従う変数の線形関数の最大化、1947年。TC Koopmans (編)：生産と配分の活動分析、ニューヨーク・ロンドン、1951年（Wiley & Chapman-Hall） 339～347頁に掲載
JE Beasley編。線形計画法と整数計画法の進歩。オックスフォード・サイエンス、1996年。（サーベイ集）
Bland, Robert G. (1977). 「単体法のための新しい有限ピボット規則」。オペレーションズ・リサーチの数学。2 ( 2): 103–107 . doi :10.1287/moor.2.2.103. JSTOR 3689647
カール＝ハインツ・ボルグヴァルト (1987).シンプレックス法：確率的分析. アルゴリズムと組合せ論. 第1巻. シュプリンガー・フェアラーク.（ランダム問題における平均的挙動）
リチャード・W・コトル編. 『The Basic George B. Dantzig 』. スタンフォード・ビジネス・ブックス, スタンフォード大学出版局, カリフォルニア州スタンフォード, 2003. （ジョージ・B・ダンツィグの選集）
ジョージ・B・ダンツィグとムクンド・N・タパ. 1997. 『線形計画法1：入門』 . シュプリンガー・フェアラーク.
ジョージ・B・ダンツィグ; ムクンド・N・タパ (2003). 『線形計画法2：理論と拡張』 . シュプリンガー・フェアラーク（包括的で、例えば、ピボット法と内点法アルゴリズム、大規模問題、ダンツィヒ＝ウルフとベンダーズ法に従った分解、確率計画法の導入などを網羅しています。）
エドモンズ、ジャック、ジャイルズ、リック (1977). 「グラフ上の劣モジュラ関数の最小最大関係」.整数計画法研究. 離散数学年報. 第1巻. pp. 185– 204. doi :10.1016/S0167-5060(08)70734-9. ISBN 978-0-7204-0765-5。
福田孔明; テルラキータマス (1997). トーマス・M・リーブリング; ドミニク・デ・ヴェラ (編). 「クリスクロス法：ピボットアルゴリズムへの新たな視点」.数理計画シリーズB. 79 ( 1–3 ) : 369–395 . CiteSeerX 10.1.1.36.9373 . doi :10.1007/BF02614325. MR 1464775. S2CID 2794181
ヤチェク・ゴンジオ、タマーシュ・テルラキー (1996). 「3 内点法の計算論的視点」 JE Beasley (編).線形計画法と整数計画法の進歩. オックスフォード数学とその応用講義シリーズ第4巻. ニューヨーク: オックスフォード大学出版局. pp. 103–144 . MR 1438311. GondzioのウェブサイトとTerlakyのマクマスター大学ウェブサイトのPostscriptファイル.
カッタ・G. マーティ (1983).線形計画法. ニューヨーク: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9 MR 0720547. (古典的アプローチの包括的な参考文献).
Evar D. NeringとAlbert W. Tucker、1993年、『線形計画法と関連問題』、Academic Press。（初級）
Padberg, M. (1999). 『線形最適化と拡張第2版』、Springer-Verlag(主単体アルゴリズムと双対単体アルゴリズム、射影アルゴリズムについて丁寧に説明されており、整数線形計画法の入門書としてオデュッセウスの巡回セールスマン問題を取り上げています。)
パパディミトリウ、クリストス・H.；シュタイグリッツ、ケネス.組合せ最適化：アルゴリズムと複雑性（新しい序文を加えた訂正再出版）ドーバー.（コンピュータサイエンス）
トッド、マイケル・J.（2002年2月）. 「線形計画法の多くの側面」.数理計画. 91 (3): 417–436 . doi :10.1007/s101070100261. S2CID 6464735.（国際数理計画シンポジウムからの招待講演）
ヴァンダーベイ、ロバート・J.（2001年）.線形計画法：基礎と拡張. シュプリンガー・フェアラーク.
ヴァジラニ、ヴィジェイ・V.（2001年）.近似アルゴリズム. シュプリンガー・フェアラーク. ISBN 978-3-540-65367-7。（コンピュータサイエンス）

さらに詳しく

線形計画法に関する図書館資料

図書館の資料

Dmitris AlevrasとManfred W. Padberg著、『線形最適化と拡張：問題と解答』、Universitext、Springer-Verlag、2001年。（Padbergの問題と解答）
de Berg, Mark; van Kreveld, Marc; Overmars, Mark ; Schwarzkopf, Otfried (2000).計算幾何学（第2版）. Springer-Verlag . ISBN 978-3-540-65620-3。第4章：線形計画法：63～94ページ。線形計画法のためのランダム化半平面交差アルゴリズムについて説明します。
Michael R. GareyとDavid S. Johnson (1979). 『コンピュータと扱いにくさ：NP完全性理論へのガイド』 . WH Freeman. ISBN 978-0-7167-1045-5。A6: MP1: 整数計画法、245ページ。（コンピュータサイエンス、複雑性理論）
ベルント・ガートナー、イジー・マトウシェク（2006年）。『線形計画法の理解と応用』。ベルリン：シュプリンガー。ISBN 3-540-30697-8。（数学者とコンピュータ科学者のための初歩的な入門
コルネリス・ルース、タマーシュ・テルラキー、ジャン＝フィリップ・ヴィアル、『線形最適化のための内点法』、第2版、シュプリンガー・フェアラーク、2006年。（大学院レベル）
アレクサンダー・シュライバー（2003年）。『組合せ最適化：多面体と効率性』。シュプリンガー。
アレクサンダー・シュライバー、『線形計画法と整数計画法の理論』。ジョン・ワイリー・アンド・サンズ、1998年、ISBN 0-471-98232-6（数学）
Gerard Sierksma、Yori Zwols (2015).線形および整数最適化：理論と実践. CRC Press. ISBN 978-1-498-71016-9。オンラインソルバー付き：https://online-optimizer.appspot.com/
Gerard Sierksma、Diptesh Ghosh (2010). Networks in Action; Text and Computer Exercises in Network Optimization . Springer. ISBN 978-1-4419-5512-8。（線形最適化モデリング）
HP Williams, Model Building in Mathematical Programming , Fifth Edition, 2013. （モデリング）
Stephen J. Wright, 1997, Primal-Dual Interior-Point Methods , SIAM. （大学院レベル）
Yinyu Ye , 1997, Interior Point Algorithms: Theory and Analysis , Wiley. (大学院上級レベル)
ジーグラー、ギュンター・M.、『多面体に関する講義』第1～3章および第6～7章、シュプリンガー・フェアラーク、ニューヨーク、1994年。（幾何学）

外部リンク

ウィキメディア・コモンズには、線形計画法に関連するメディアがあります。

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