混合整数線形計画問題(MILP)

Mark 29.3において、NAGは大規模な混合整数線形計画問題(MILP)に特化した最先端のソルバー (nag_mip_handle_solve_milp)を導入しました。これは、NAGが数理最適化分野での提供内容を強化・拡大するという取り組みにおいて重要な前進となります。

MILPは、金融、製造、物流、輸送、通信など、さまざまな業界で幅広く応用されています。連続変数と離散変数の両方を扱えるため、このソルバーを使うことで、資源配分、スケジューリング、ネットワークフローなど、実践的で難しい問題をモデル化することができます。

以下の形式の大規模MILPは、

\[ \begin{array}{ll} \underset{x \in {\mathbb{R}}^{n}}{\text{minimize}} & {c^{T}x} \\ & \\ \text{subject to} & {l_{A} \leq \mathit{Ax} \leq u_{A},} \\ & \\ & {l_{x} \leq x \leq u_{x},} \end{array} \tag{1}\]

\(x \in P\),

ここで、 \(A \in \mathbb{R}^{m \times n}\), \(l_{A}, u_{A} \in \mathbb{R}^m\), \(c\), \(l_{x}\), \(u_{x} \in \mathbb{R}^n\) は問題のデータであり、 \(P = \mathbb{Z}^{n_{int}} \times \mathbb{R}^{n_{l}}\) は現実のアプリケーションでは非常にありふれています。MILPの解を求めることは、組合せ的な性質上、かなりの難しさがあり、実用的なシナリオの多くでは、妥当な時間内に厳密解を見つけることは非常に困難であることを強調しておくことが重要です。私たちは、NAGライブラリに最新の追加を発表でき、ユーザーが効率的かつ正確に意思決定を行うのに役立つことを目指しています。

MILPのモデリングと解法

モデル(1)は、多くの実用的なユースケースをカバーしています。 MILPの特徴の1つは、含意や二分法などの論理条件をモデル化できることです。

例えば、固定費用のモデリングを考えてみましょう。経済活動では、固定費用と変動費用の両方が発生することがよくあります。これらの場合、変数 \(y\) が正の値を取るときにのみ、固定費用 \(c_{fix}\) が発生します。変動費用を \(c_{var}\) とすると、\(y > 0\) のときの総費用は \(c_{fix} + c_{var}y\) で、それ以外は0となります。コスト関数が非線形であることは容易に観察できます。バイナリ変数 \(x\) を導入することで、

\[c_{\mathit{fix}}x + c_{\mathit{var}}y,\]

と線形式でモデル化することができます。ここで、以下の制約を追加します。

\[\begin{array}{l} {0 \leq y \leq \mathit{Mx},} \\ \\ {x \in \{ 0,1\},} \end{array}\]

ここで、 \(M\)\(y\) の上界であり、恣意的に大きな \(M\) ではなく、既知の最小の上界として選ばれるべきです。このモデリング手法は、施設配置やネットワーク設計などのアプリケーションで登場します。

MILPのもう1つの素晴らしい使い方は、選言をモデル化することです。例えば、マシン上でジョブをスケジューリングする際、ジョブ \(i\) をジョブ \(j\) の前にスケジューリングするか、その逆にスケジューリングするかを選択できるようにしたいとします。 \(p_{i}\)\(p_{j}\) をそれぞれジョブ \(i\) とジョブ \(j\) の処理時間、\(t_{i}\)\(t_{j}\) をそれぞれの開始時刻とします。すると、次の制約のうち少なくとも1つが満たされる必要があります。

\[\begin{array}{l} {t_{j} \geq t_{i} + p_{i},} \\ \\ {t_{i} \geq t_{j} + p_{j},} \end{array}\]

バイナリ変数 \(x_{1}\)\(x_{2}\) を導入することで、この問題は次のようにモデル化できます。

\[\begin{array}{l} {x_{1} + x_{2} \geq 1,} \\ \\ {x_{1},x_{2} \in \{ 0,1\},} \\ \\ {t_{j} \geq t_{i} + p_{i} - M(1 - x_{1}),} \\ \\ {t_{i} \geq t_{j} + p_{j} - M(1 - x_{2}),} \end{array}\]

ここでも、 \(M\) は正の値で、既知の上界として機能します。

オペレーションズリサーチの分野では、他にも非常に有用な制約のタイプがたくさんあります。例えば、

  • 変数 \(x\) が0か区間 \([a, b)\) のいずれかの値をとる半連続変数
  • \(x \in \{ - 2, - 1,1,2 \}\) のように、変数が集合の中の値だけを取る
  • 線形関数の組み合わせとみなすことができる、連続な区分線形関数

などがあります。スケジューリングにおけるより多くの定式化手法とその使用法については、[1, 2] を参照してください。

図1:分枝限定法の木の例示

(1)を効率的に解くために、前処理、カット生成、さまざまなヒューリスティックなどの現代的なMILP手法を備えた分枝限定法が基本的なフレームワークとして機能します。分枝限定法の木の一部を図1に示します。元の問題(ルートノードと呼ばれる)から始めて、このアルゴリズムはゴモリー分数カットの追加などにより実行可能領域を形作ることで、さまざまな子ノードを生成します。各ノードは、効率的な双対単体法を使用して連続線形計画問題として解かれます。より良い下界を得るために、さまざまなヒューリスティックが採用されています。探索木を上手く枝刈りし、探索ノードを選択することで、分枝限定法アルゴリズムが妥当な時間内に最適解を見つける可能性が大幅に高まります。MILPを解くアルゴリズムの詳細については、[3] を参照してください。

MILPソルバー nag_mip_handle_solve_milp は、NAG最適化モデリングスイート に完全に統合されており、ユーザーは実世界の問題を数理モデルにより良く表現でき、モデルの内部動作の理解を深めることができます。モデリングの過程で、ユーザーは以下のことができます。

  • 特定の制約や変数を一時的に取り除いたり、再び追加したりすることで、その影響を確認する
  • 線形目的関数や線形制約の個々の係数を変更する
  • 変数を特定の定数に固定することで、定式化全体からその変数を取り除き、問題の次元を減らす

このソルバーは、C、C++、Python、Java、.NET、Fortranを含む複数の言語と環境で利用可能で、Windows、Linux、MacOSに対応しています。利用可能な製品については、NAG数値計算ライブラリのページを参照してください。

参考文献

[1][ ]Vielma JP. Mixed integer linear programming formulation techniques. Siam Review. 2015;57(1):3-57.

[2][ ]Floudas CA, Lin X

関連情報
MENU
Privacy Policy  /  Trademarks