整数計画法

整数計画問題は、変数の一部またはすべてが整数に制限される数学的な最適化または実現可能性プログラムです。多くの場合、この用語は整数線形計画(ILP) を指し、目的関数と制約 (整数制約以外) は線形です。

整数計画法はNP完全である。特に、未知数が2進数で制約条件のみを満たす必要がある0–1整数線形計画法の特殊なケースは、Karpの21のNP完全問題のうちの1つである。^[1]

いくつかの決定変数が離散的でない場合、この問題は混合整数計画問題として知られています。^[2]

整数線形計画法では、標準形は標準形とは異なります。標準形の整数線形計画法は次のように表現されます（決定すべきはベクトルであることに注意）。^[3]${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm { T} }\mathbf {x} \\&{\text{対象}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{整列}}}$

標準形式のILPは次のよ​​うに表現される。

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}$

ここで、 はベクトル、は行列です。線形計画法と同様に、標準形式ではない ILP は、不等式を削除し、スラック変数 ( ) を導入し、符号制約のない変数を 2 つの符号制約のある変数の差に置き換えること によって、標準形式に変換できます。${\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}$${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle \mathbf {s} }$

右側のグラフは次の問題を示しています。

${\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}$

実行可能な整数点は赤で示され、赤い破線はそれらの凸包を示します。凸包は、これらすべての点を含む最小の凸多面体です。青い線は座標軸とともに、LP 緩和の多面体を定義します。これは、整数制約のない不等式によって与えられます。最適化の目標は、黒の破線を多面体に接触したまま、できるだけ上方に動かすことです。整数問題の最適解は、目的値が 2 である点と点です。緩和の唯一の最適解は、目的値が 2.8 です。緩和の解が最も近い整数に丸められる場合、ILP では実行可能ではありません。 ${\displaystyle (1,2)}$${\displaystyle (2,2)}$${\displaystyle (1.8,2.8)}$

以下は、NP 困難性の証明となる、 最小頂点カバーから整数計画法への還元です。

を無向グラフとします。次のように線形計画を定義します。 ${\displaystyle G=(V,E)}$

${\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}}$

制約が0 か 1 に制限されることを考えると、整数計画の実行可能な解は頂点のサブセットになります。最初の制約は、すべてのエッジの少なくとも 1 つの端点がこのサブセットに含まれることを意味します。したがって、解は頂点カバーを表します。さらに、頂点カバー C が与えられている場合、任意の に対して 1 に設定でき、任意の に対して 0に設定できるため、整数計画の実行可能な解が得られます。したがって、 の合計を最小化すれば、最小の頂点カバーも見つかったと結論付けることができます。^[4]${\displaystyle y_{v}}$${\displaystyle y_{v}}$${\displaystyle v\in C}$${\displaystyle v\not \in C}$${\displaystyle y_{v}}$

混合整数線形計画法( MILP ) では、変数の一部のみが整数に制限され、他の変数は非整数であることが許可される問題が扱われます。 ${\displaystyle x_{i}}$

ゼロ-1線形計画法（または二進整数計画法）は、変数が0か1に制限される問題です。任意の有界整数変数は、二進変数の組み合わせとして表現できます。^[5]たとえば、整数変数が与えられた場合、変数は二進変数を使用して表現できます。 ${\displaystyle 0\leq x\leq U}$${\displaystyle \lfloor \log _{2}U\rfloor +1}$

$${\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}$$

問題を線形計画としてモデル化するときに整数変数を使用する主な理由は 2 つあります。

1. 整数変数は整数でしか表せない量を表します。たとえば、3.7 台の自動車を製造することはできません。
2. 整数変数は決定（たとえば、グラフにエッジを含めるかどうか）を表すため、0 または 1 の値のみを取る必要があります。

これらの考慮事項は実際には頻繁に発生するため、整数線形計画法は多くのアプリケーション領域で使用できます。そのうちのいくつかについて、以下で簡単に説明します。

混合整数計画法は、ジョブショップ モデリングを含む工業生産において多くの用途があります。重要な例の 1 つは農業生産計画で、リソース (土地、労働力、資本、種子、肥料など) を共有できる複数の作物の生産量を決定することです。考えられる目標は、利用可能なリソースを超えずに総生産量を最大化することです。場合によっては、これを線形計画法で表現できますが、変数は整数に制限する必要があります。

これらの問題には、輸送ネットワークにおけるサービスと車両のスケジュールが含まれます。たとえば、バスや地下鉄を個別のルートに割り当てて時刻表に間に合うようにし、運転手を配置するという問題があります。ここで、バイナリ決定変数は、バスまたは地下鉄がルートに割り当てられているかどうか、および運転手が特定の電車または地下鉄に割り当てられているかどうかを示します。ゼロ-1 計画法は、プロジェクトが相互に排他的であるか、技術的に相互依存しているプロジェクト選択問題を解決するために効果的に適用されてきました。これは、すべての決定変数が整数である、整数計画法の特殊なケースで使用されます。変数は、0 または 1 の値のみを取ることができます。

領土分割または地区分割の問題は、さまざまな基準や制約を考慮しながらいくつかの操作を計画するために、地理的領域を地区に分割することです。この問題の要件には、連続性、コンパクトさ、バランスまたは公平性、自然境界の尊重、および社会経済的均質性などがあります。このタイプの問題の用途には、政治地区分割、学校地区分割、医療サービス地区分割、廃棄物管理地区分割などがあります。

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

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

• キャッシュフローマッチング
• エネルギーシステムの最適化^{[8] [9]}
• 無人航空機 誘導^{[10] [11]}
• 交通マップの レイアウト^[12]

ILP を解く単純な方法は、x が整数であるという制約を削除し、対応する LP ( ILP のLP 緩和と呼ばれる) を解き、ソリューションのエントリを LP 緩和に丸めることです。ただし、このソリューションは最適ではないだけでなく、実行可能でもない可能性があります。つまり、何らかの制約に違反している可能性があります。

一般に、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} }$

の列は線形独立で は正方なので、は非特異であり、したがって仮定により はユニモジュラであり、したがって です。また、は非特異なので、可逆であり、したがって です。定義により、 です。ここで はの随伴を表し、 は整数であるため、 は整数です。したがって、 したがって、ILP の行列が完全にユニモジュラである場合、ILP アルゴリズムを使用するのではなく、単体法を使用して LP 緩和を解くことができ、解は整数になります。 ${\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}$

行列が完全にユニモジュラでない場合は、整数線形計画法を正確に解くために使用できるさまざまなアルゴリズムがあります。アルゴリズムの 1 つのクラスは、切断平面法です。これは、LP 緩和を解決してから、整数実行可能点を除外することなくソリューションを整数に近づける線形制約を追加することによって機能します。 ${\displaystyle A}$

別の種類のアルゴリズムは、分岐限定法のバリエーションです。たとえば、分岐限定法と切断面法の両方を組み合わせた分岐切断法があります。分岐限定アルゴリズムには、切断面のみを使用するアルゴリズムに比べて多くの利点があります。利点の 1 つは、アルゴリズムを早期に終了でき、少なくとも 1 つの積分解が見つかれば、必ずしも最適ではないものの実現可能な解を返すことができることです。さらに、LP 緩和の解を使用して、返された解が最適からどれだけ離れているかの最悪のケースの推定値を提供できます。最後に、分岐限定法を使用して、複数の最適解を返すことができます。

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

V を、 およびにおける係数の絶対値の最大値とする。n (変数の数) が固定定数である場合、実現可能性問題は、 mおよび log Vにおける時間多項式で解くことができる。これは、 n =1の場合に自明である。n =2 の場合は、 1981 年にHerbert Scarfによって解決された。^[13]一般の場合は、László LovászとPeter van Emde Boasのアイデアを組み合わせて、 1983 年にHendrik Lenstraによって解決された。^[14]ドワニョンの定理は、制約のすべてのサブセットが実行可能である場合は常に、整数計画が実行可能であることを主張する。この結果をLP 型の問題のアルゴリズムと組み合わせた方法は、で線形かつで固定パラメータ扱い可能(FPT) であるが、では に依存せずに二重指数関数である可能性のある整数計画を時間で解くために使用できる。^[15]${\displaystyle A}$${\displaystyle \mathbf {b} }$ ${\displaystyle 2^{n}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$${\displaystyle V}$

0-1 ILP の特殊なケースでは、Lenstra のアルゴリズムは完全な列挙と同等です。つまり、すべての可能な解の数は固定 (2 ⁿ ) で、各解の実現可能性の確認は時間 poly( m、 log V ) で実行できます。各変数が任意の整数になる一般的なケースでは、完全な列挙は不可能です。ここで、Lenstra のアルゴリズムは数の幾何学のアイデアを使用します。元の問題を、解の存在が明らかであるか、 ( n番目の変数)の値がnの関数によって長さが制限される区間に属するかのいずれかである同等の問題に変換します。後者の場合、問題は制限された数の低次元の問題に縮小されます。アルゴリズムの実行時の複雑さは、いくつかのステップで改善されています。 ${\displaystyle \mathbf {x} }$${\displaystyle x_{n}}$

• ^{Lenstra [14]}のオリジナルのアルゴリズムは実行時間がありました。${\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}$
• Kannan ^[16]は 実行時間を考慮した改良アルゴリズムを提示した。^[17]${\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$
• フランクとタルドス^[18]は、実行時間を考慮した改良アルゴリズムを提示した 。^{[19] [20] ：提案8}${\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$

• Dadush ^[21]は実行時間を考慮した改良アルゴリズムを提示した。${\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$

• ReisとRothvoss ^[22]は 実行時間を考慮した改良アルゴリズムを提示した。${\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$

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

整数線形計画法はNP困難であるため、多くの問題インスタンスは扱いにくく、代わりにヒューリスティックな方法を使用する必要があります。たとえば、タブー探索を使用してILPの解を検索できます。^[24] タブー探索を使用してILPを解くには、移動を、実行可能なソリューションの整数制約変数を増分または減分し、他のすべての整数制約変数を一定に保つこととして定義できます。次に、制限のない変数を解きます。短期記憶は以前に試したソリューションで構成でき、中期記憶は高い目的値をもたらした整数制約変数の値で構成できます（ILPが最大化問題であると仮定）。最後に、長期記憶は、以前に試したことのない整数値への検索を導くことができます。

ILPに適用できる他のヒューリスティック手法としては、

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

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

整数計画法を定義する行列がスパース であるケースはよくあります。特に、これは行列がブロック構造 を持つ場合に発生し、多くのアプリケーションで当てはまります。行列のスパース性は次のように測定できます。のグラフにはの列に対応する頂点があり、の行に両方の列に非ゼロのエントリがある場合、2 つの列がエッジを形成します。同様に、頂点は変数に対応し、2 つの変数が不等式を共有する場合、2 つの変数がエッジを形成します。のスパース性尺度は、のグラフのツリーの深さとの転置のグラフのツリーの深さの最小値です。を の任意のエントリの最大絶対値として定義されるの数値尺度とします。を整数計画法の変数の数とします。その後、2018 年^[25]で、整数計画法はおよびによってパラメータ化された強多項式かつ固定パラメータの扱いやすい時間で解くことができることが示されました。つまり、何らかの計算可能な関数と何らかの定数に対して、整数計画法は 時間 で解くことができます。特に、時間は右辺と目的関数に依存しません。さらに、変数の数がパラメータであるLenstraの古典的な結果とは対照的に、ここでは変数の数が入力の可変部分です。 ${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$ ${\displaystyle d}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle a}$${\displaystyle A}$${\displaystyle A}$${\displaystyle n}$${\displaystyle a}$${\displaystyle d}$${\displaystyle f}$${\displaystyle k}$${\displaystyle f(a,d)n^{k}}$${\displaystyle b}$${\displaystyle c}$${\displaystyle n}$${\displaystyle n}$

• 制約付き最小二乗法
• ディオファントス方程式 – 整数解を求める多項式

• George L. Nemhauser 、 Laurence A. Wolsey (1988)。整数と組み合わせ最適化。Wiley。ISBN 978-0-471-82819-8。
• Alexander Schrijver (1998)。線形計画法と整数計画法の理論。John Wiley and Sons。ISBN 978-0-471-98232-6。
• ローレンス・A・ウォルジー（1998年）。整数計画法。ワイリー。ISBN 978-0-471-28366-9。
• ディミトリス・ベルチマス、ロバート・ワイズマンテル (2005)。整数の最適化。ダイナミック・アイデア。ISBN 978-0-9759146-2-5。
• John K. Karlof (2006)。整数計画法：理論と実践。CRC Press。ISBN 978-0-8493-1914-3。
• H. ポール・ウィリアムズ (2009)。論理と整数プログラミング。Springer。ISBN 978-0-387-92279-9。
• Michael Jünger、Thomas M. Liebling、Denis Naddef、George Nemhauser、William R. Pulleyblank、Gerhard Reinelt、Giovanni Rinaldi、Laurence A. Wolsey 編 (2009)。50 Years of Integer Programming 1958-2008 : From the Early Years to the State-of-the-Art。Springer。ISBN 978-3-540-68274-5。
• Der-San Chen、Robert G. Batson、Yu Dang (2010)。応用整数計画法: モデリングとソリューション。John Wiley and Sons。ISBN 978-0-470-37306-4。
• ジェラルド・シールクスマ。ヨリ・ズウォルス (2015)。線形最適化と整数最適化: 理論と実践。 CRCプレス。ISBN 978-1-498-71016-9。

• 整数計画法のチュートリアル
• 会議 整数計画法と組み合わせ最適化、IPCO
• オーソワ組み合わせ最適化ワークショップ