線形計画法

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

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

最大化する

{\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 ^*である、と述べています。

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

バリエーション

被覆/パッキングの双対性

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

最小化: b ^Ty、

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

行列Aとベクトルbとcが非負となるようなもの。

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

最大化: 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番目のスラック変数がゼロでない場合、双対変数のi番目の変数はゼロになります。同様に、双対変数のj番目のスラック変数がゼロでない場合、主変数のj番目の変数はゼロになります。

この最適化の必要条件は、非常に単純な経済原理を示しています。標準的な形式（最大化の場合）では、制約された基本資源に余裕がある場合（つまり「余剰」がある場合）、その資源の追加量は価値を持たないはずです。同様に、双対（影）価格非負制約の要件に余裕がある場合、つまり価格がゼロでない場合、供給は希少（「余剰」がない）でなければなりません。

理論

最適解の存在

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

最適解は、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]

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

交差アルゴリズム

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

内点

多面体セット上の頂点間のエッジをトラバースして最適なソリューションを見つける単体アルゴリズムとは対照的に、内点法は実行可能領域の内部を移動します。

Khachiyan に従う楕円体アルゴリズム

これは、線形計画法において初めて発見された最悪ケースの多項式時間アルゴリズムです。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年に、リーとシドフォードは線形計画法が時間で解けることを示しました。 ^[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 は、厳密に補完的なソリューションを見つけるための強力な多項式時間アルゴリズムを許可しますか?
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が整数であると仮定）があることが何らかの方法で証明されており、すべての多項式サイズの線形計画法は多項式時間で解くことができるため、この最適値は効率的に見つけることができます。

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

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

許容ライセンス:

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

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

独自のライセンス:

参照

注記

^ フォン・ノイマン, J. (1945). 「一般経済均衡モデル」.経済研究. 13 (1): 1– 9. doi :10.2307/2296111. JSTOR 2296111.
^ Kemeny, JG; Morgenstern, O.; Thompson, GL (1956). 「拡大経済におけるフォン・ノイマン・モデルの一般化」. Econometrica . 24 (2): 115– 135. doi :10.2307/1905746. JSTOR 1905746.
^ 李、呉（2019）『一般均衡と構造動学：新構造経済学の展望』（中国語）北京：経済科学出版社、pp. 122– 125. ISBN 978-7-5218-0422-5。
^ ab ジェラルド・シールクスマ;ヨリ・ズウォルス (2015)。線形最適化と整数最適化: 理論と実践(第 3 版)。 CRCプレス。 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日時点のオリジナルよりアーカイブ。
^ アレクサンダー・シュライバー (1998)。線形計画法と整数計画法の理論。ジョン・ワイリー＆サンズ。ページ 221–222。ISBN 978-0-471-98232-6。
^ abc Dantzig, George B.; Thapa, Mukund Narain (1997).線形計画法. ニューヨーク: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475。
^ abc レオニード・ハチヤン (1979)。「線形計画法のための多項式アルゴリズム」。ドクラディ・アカデミ・ナウク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。
^ ヴァジラニ（2001年、112ページ）
^ abc 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.
^ ボルグヴァルト（1987）
^ トッド（2002）
^ マーティ（1983）
^ パパディミトリウ＆シュタイグリッツ
^ 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回コンピュータサイエンス基礎シンポジウム. 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 .
^ 江、春華;宋、趙。ワインスタイン、オムリ。張恒傑（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). 「線形計画法のための単調なビルドアップシンプレックスアルゴリズム」.オペレーションズ・リサーチ. 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 Archived 2011-07-20 at the Wayback Machine OptimJ used in an optimization model for mixing-model assemble lines, University of Münster
^ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 Archived 2011-06-29 at the Wayback Machine OptimJ used in an approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games

参考文献

カントロヴィッチ、LV (1940)。「Об одном эффективном методе резения некоторых классов экстремальных проблем」[いくつかのクラスの極限問題を解く新しい方法]。ドクラディ・アカド科学SSSR。28 : 211–214 .
FL ヒッチコック:複数の供給源から多数の地域への製品の分布、数学および物理学ジャーナル、20、1941、224–230。
GB Dantzig:線形不等式に従う変数の線形関数の最大化、1947年。TC Koopmans (ed.): Activity Analysis of Production and Allocation、New York-London 1951 (Wiley & Chapman-Hall)の339～347ページに掲載。
JE Beasley編著『線形計画法と整数計画法の進歩』オックスフォード・サイエンス社、1996年（概説集）
ブランド、ロバート・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・ダンツィグ選集）
George B. DantzigとMukund N. Thapa. 1997.線形計画法1：入門. Springer-Verlag.
Dantzig, George B.; Thapa, Mukund N. (2003).線形計画法 2: 理論と拡張. Springer-Verlag.(包括的で、ピボットおよび内点アルゴリズム、大規模問題、Dantzig–WolfeおよびBendersに従った分解、確率的計画法の紹介などをカバーしています。)
エドモンズ、ジャック、ジャイルズ、リック (1977). 「グラフ上の劣モジュラ関数の最小-最大関係」.整数計画法研究. 離散数学年報. 第1巻. pp. 185– 204. doi :10.1016/S0167-5060(08)70734-9. ISBN 978-0-7204-0765-5。
福田孔明; テルラキータマス (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.
Gondzio, Jacek; Terlaky, Tamás (1996). 「3 内点法の計算論的視点」 JE Beasley (編).線形計画法と整数計画法の進歩. Oxford Lecture Series in Mathematics and its Applications. 第4巻. ニューヨーク: Oxford University Press. 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 年、「Linear Programs and Related Problems 」、Academic Press。(初級)
Padberg, M. (1999).線形最適化と拡張, 第2版. Springer-Verlag.(主単体アルゴリズムと双対単体アルゴリズム、射影アルゴリズムについて丁寧に説明されており、整数線形計画法の入門書としてオデュッセウスの巡回セールスマン問題を取り上げています。)
パパディミトリウ, クリストス・H. ; シュタイグリッツ, ケネス.組合せ最適化：アルゴリズムと複雑性（新しい序文を追加した修正版）ドーバー.（コンピュータサイエンス）
トッド, マイケル・J. (2002年2月). 「線形計画法の多様な側面」.数理計画. 91 (3): 417– 436. doi :10.1007/s101070100261. S2CID 6464735.(国際数理計画シンポジウムからの招待調査。)
Vanderbei, Robert J. (2001).線形計画法：基礎と拡張. Springer Verlag.
ヴァジラニ、ビジェイ V. (2001)。近似アルゴリズム。スプリンガー・フェルラーク。ISBN 978-3-540-65367-7。（コンピュータサイエンス）

さらに読む

線形計画法に関する図書館リソース

ライブラリ内のリソース

Dmitris Alevras および Manfred W. Padberg、「Linear Optimization and Extensions: Problems and Solutions」、Universitext、Springer-Verlag、2001 年。(Padberg の問題と解答。)
デ・バーグ、マーク。マーク・ヴァン・クレフェルト。マーク・オーヴァーマーズ;シュワルツコップ、オトフリート (2000)。計算幾何学(改訂第 2 版)。スプリンガー・フェルラーグ。ISBN 978-3-540-65620-3。第4章：線形計画法：63～94ページ。線形計画法のためのランダム半平面交差アルゴリズムについて説明します。
マイケル・R・ギャリー、デイビッド・S・ジョンソン（1979年）『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 WHフリーマン、ISBN 978-0-7167-1045-5。A6: MP1: 整数計画法、245ページ。（コンピュータサイエンス、計算量理論）
ガートナー、ベルント;マトウシェク、イジー(2006)。線形計画法の理解と使用。ベルリン：シュプリンガー。ISBN 3-540-30697-8。（数学者とコンピュータ科学者のための初歩的な入門）
Cornelis Roos、Tamás Terlaky、Jean-Philippe Vial、『線形最適化のための内点法』第2版、Springer-Verlag、2006年（大学院レベル）
アレクサンダー・シュライバー (2003)。組み合わせ最適化: 多面体と効率。スプリンガー。
Alexander Schrijver、線形計画法と整数計画法の理論。ジョン・ワイリー＆サンズ、1998、ISBN 0-471-98232-6（数学）
ジェラルド・シールクスマ。ヨリ・ズウォルス (2015)。線形最適化と整数最適化: 理論と実践。 CRCプレス。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. （大学院上級レベル）
Ziegler, Günter M.、Lectures on Polytopes の第1章から第3章、第6章から第7章、Springer-Verlag、ニューヨーク、1994年。（幾何学）

外部リンク

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

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