整数計画法

混合整数計画法は、ジョブショップモデルをはじめとする工業生産において多くの応用例があります。重要な例の一つは農業生産計画で、資源（土地、労働力、資本、種子、肥料など）を共有できる複数の作物の生産量を決定する際に用いられます。考えられる目標の一つは、利用可能な資源を超えずに総生産量を最大化することです。場合によっては、これは線形計画問題として表現できますが、変数は整数に制約されなければなりません。

これらの問題は、輸送ネットワークにおけるサービスと車両のスケジューリングに関するものです。例えば、時刻表を遵守するためにバスや地下鉄を個々の路線に割り当て、さらに運転手を配置するという問題が考えられます。ここで、二値決定変数は、バスや地下鉄が路線に割り当てられるかどうか、また運転手が特定の列車や地下鉄に割り当てられるかどうかを示します。ゼロイチ計画法は、プロジェクトが相互に排他的であったり、技術的に相互依存的であったりするプロジェクト選択問題の解決に成功裏に適用されています。

地域分割問題とは、さまざまな基準や制約を考慮しながら、地理的な地域を複数の地区に分割し、事業計画を立てる問題です。この問題における要件としては、隣接性、コンパクト性、バランスまたは公平性、自然境界の尊重、社会経済的均質性などが挙げられます。この種の問題の応用例としては、政治区割り、学校区割り、医療サービス区割り、廃棄物管理区割りなどがあります。

これらの問題の目標は、あらかじめ定義された通信要件を満たし、ネットワークの総コストが最小になるように、設置する回線のネットワークを設計することです。^{[ 9 ]} これには、ネットワークのトポロジーを最適化するとともに、さまざまな回線の容量を設定する必要があります。多くの場合、容量は整数値に制限されます。通常、使用する技術に応じて、整数またはバイナリ変数の線形不等式としてモデル化できる追加の制約があります。

GSMモバイルネットワークにおける周波数計画のタスクは、利用可能な周波数をアンテナ間で分配して、ユーザーにサービスを提供し、アンテナ間の干渉を最小限に抑えることです。^{[ 10 ]} この問題は、バイナリ変数が周波数がアンテナに割り当てられるかどうかを示す整数線形計画問題として定式化できます。

• キャッシュフローマッチング
• エネルギーシステムの最適化^{[ 11 ] [ 12 ]}
• UAV誘導^{[ 13 ] [ 14 ]}
• 交通路線図のレイアウト^{[ 15 ]}

一般的にLP緩和の解は必ずしも整数値になるとは限りませんが、ILPが次の形式の場合${\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }$そのため${\displaystyle A\mathbf {x} =\mathbf {b} }$どこ${\displaystyle A}$そして${\displaystyle \mathbf {b} }$すべて整数エントリを持ち、${\displaystyle A}$が完全ユニモジュラーである場合、すべての基本実行可能解は整数です。したがって、シンプレックス法によって返される解は整数であることが保証されます。すべての基本実行可能解が整数であることを示すために、${\displaystyle \mathbf {x} }$任意の基本実行可能解とする。${\displaystyle \mathbf {x} }$実現可能だとわかっているので、${\displaystyle A\mathbf {x} =\mathbf {b} }$。 させて${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$基本解の基底列に対応する要素とする。${\displaystyle \mathbf {x} }$基底の定義により、ある正方部分行列が存在する。${\displaystyle B}$の ${\displaystyle A}$線形独立な列を持ち、${\displaystyle B\mathbf {x} _{0}=\mathbf {b} }$。

列以来${\displaystyle B}$線形独立であり、${\displaystyle B}$正方形です。${\displaystyle B}$は非特異であり、したがって仮定により、${\displaystyle B}$単一モジュールなので${\displaystyle \det(B)=\pm 1}$また、${\displaystyle B}$は非特異であり、可逆であるため、${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$定義上、${\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}$。 ここ${\displaystyle B^{\mathrm {adj} }}$の補佐役を表す${\displaystyle B}$そしてそれは不可欠である${\displaystyle B}$は整数です。したがって、 $${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}}$$ したがって、行列が${\displaystyle A}$ILP の完全ユニモジュラーである場合、ILP アルゴリズムを使用する代わりに、シンプレックス法を使用して LP 緩和を解くことができ、解は整数になります。

行列が${\displaystyle A}$完全にユニモジュラーではないものの、整数線形計画問題を正確に解くために使用できるアルゴリズムは数多く存在する。アルゴリズムの一種に、切除平面法がある。これは、線形計画緩和問題を解き、整数実行可能点を排除することなく解を整数に近づける線形制約を追加することで機能する。

もう一つのアルゴリズムのクラスは、分岐限定法の変種です。例えば、分岐限定法と切断平面法を組み合わせた分岐カット法などがあります。分岐限定法は、切断平面法のみを使用するアルゴリズムに比べて多くの利点があります。1つの利点は、アルゴリズムを早期に終了できることです。少なくとも1つの整数解が見つかれば、必ずしも最適解ではないものの、実行可能な解を返すことができます。さらに、線形計画緩和の解を用いることで、返された解が最適解からどれだけ離れているかを最悪の場合の推定値として提供できます。最後に、分岐限定法は複数の最適解を返すために使用できます。

仮定する${\displaystyle A}$はm × nの整数行列であり、${\displaystyle \mathbf {b} }$はm行 1 の整数ベクトルです。ここでは、 n行 1 のベクトルが存在するかどうかを判定する実現可能性問題に焦点を当てます。${\displaystyle \mathbf {x} }$満足${\displaystyle A\mathbf {x} \leq \mathbf {b} }$。

Vを係数の最大絶対値とする${\displaystyle A}$ そして${\displaystyle \mathbf {b} }$n（変数の数）が固定定数である場合、実行可能性問題はmとlog Vの多項式時間で解くことができます。n =1の場合は自明です。n=2の場合は1981年にHerbert Scarfによって解決されました。^{[ 16 ]}一般的なケースは、 László LovászとPeter van Emde Boasのアイデアを組み合わせて、 1983年にHendrik Lenstraによって解決されました。^{[ 17 ]} Doignonの定理は、整数計画が実行可能であるのは、すべての部分集合が${\displaystyle 2^{n}}$制約は実行可能であり、この結果をLP型問題のアルゴリズムと組み合わせた方法を用いることで、線形時間で整数計画問題を解くことができる。${\displaystyle m}$固定パラメータ扱い可能(FPT)${\displaystyle n}$しかし、おそらく二重指数関数的である${\displaystyle n}$依存なし${\displaystyle V}$[ ^{18 ]​}

0-1整数線形計画問題（ILP）の特殊なケースでは、レンストラのアルゴリズムは完全列挙と同等です。つまり、可能な解の数は固定（2 ⁿ ）であり、各解の実行可能性のチェックはpoly( m , log V )の時間で実行できます。一般のケースでは、各変数は任意の整数になり得るため、完全列挙は不可能です。ここで、レンストラのアルゴリズムは数の幾何学の考え方を利用します。元の問題を、次の性質を持つ同等の問題に変換します。すなわち、解の存在です。${\displaystyle \mathbf {x} }$は明らかです、または、${\displaystyle x_{n}}$（n番目の変数）は、 nの関数によって長さが制限される区間に属します。後者の場合、問題は限られた数の低次元問題に縮小されます。アルゴリズムの実行時間計算量は、いくつかのステップで改善されました。

• ^{Lenstra [ 17 ]}の元のアルゴリズムは実行時間が${\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}$。
• Kannan ^{[ 19 ]}は 、実行時間を改善したアルゴリズムを発表した。${\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$[ ^{20 ]​}
• FrankとTardos ^{[ 21 ]}は、実行時間を改善したアルゴリズムを発表した。 ${\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$[ ^{22 ] [ 23 ] :命題8}
• Dadush ^{[ 24 ]}は、実行時間を改善したアルゴリズムを発表しました。${\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$。
• ReisとRothvoss ^{[ 25 ]} は、実行時間を改善したアルゴリズムを発表した。${\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$。

これらのアルゴリズムは、混合整数線形計画問題（MILP）にも使用できます。MILPとは、一部の変数が整数で、一部の変数が実数であるプログラムです。^{[ 26 ]} Lenstraの元のアルゴリズム^{[ 17 ]： Sec.5}は実行時間が${\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}$ここで、n は整数変数の数、d は連続変数の数、Lは問題のバイナリ符号化サイズです。後のアルゴリズムの手法を使用すると、係数${\displaystyle 2^{O(n^{3})}}$改善できる${\displaystyle 2^{O(n\log n)}}$または${\displaystyle n^{n}}$[ ^{26 ]​}

整数線形計画法はNP 困難であるため、多くの問題インスタンスは扱いが難しく、代わりにヒューリスティック法を使用する必要があります。たとえば、タブーサーチを使用して ILP の解を探索できます。^{[ 27 ]} タブーサーチを使用して ILP を解くには、実行可能な解の整数制約変数を増減させ、他のすべての整数制約変数を一定に保つように移動を定義できます。次に、制約のない変数を解きます。短期記憶は以前に試した解で構成され、中期記憶は高い目的値をもたらす整数制約変数の値で構成されます (ILP が最大化問題であると仮定します)。最後に、長期記憶は、以前に試していない整数値に向かって探索を誘導できます。

ILPに適用できるその他のヒューリスティック手法には以下のようなものがある。

• 丘登り
• シミュレーテッドアニーリング
• 反応型検索最適化
• アリコロニー最適化
• ホップフィールドニューラルネットワーク

他にも、巡回セールスマン問題に対するk-optヒューリスティックなど、問題固有の様々なヒューリスティックが存在する。ヒューリスティック手法の欠点は、解が見つからなかった場合、実行可能な解が存在しないのか、単にアルゴリズムが解を見つけられなかったのかを判断できないことである。さらに、これらの手法によって得られた解が最適解にどれだけ近いかを定量化することは通常不可能である。