• 整数最適化

一部の変数を整数にする必要がある線形最適化の問題は、混合整数プログラム（MIP）と呼ばれます。

これらの可変要素は、いくつかの方法で発生します。

  • 自動車やテレビなどのアイテムの個数を表す整数変数。問題は、利益を最大化するために製造するアイテムの数を決定することです。
    通常、このような問題は標準の線形最適化問題として設定できますが、変数は整数でなければならないという要件が追加されています。 次のセクションでは、このタイプの問題の例を示します。

  • 0 ～ 1 の値による決定を表すブール変数。
    例として、ワーカーをタスクに割り当てる際の問題について考えてみましょう（割り当てを参照）。このタイプの問題を設定するには、ワーカー i がタスク j に割り当てられている場合は 1 に、それ以外の場合は 0 に等しいブール値変数 xi,j を定義します。

整数の最適化の初歩については、Mosek モデリング クックブックをご覧ください。

ツール

Google では、MIP の問題を解決するいくつかの方法を提供しています。

  • MPSolver: 標準の分岐バインド手法を使用する複数のサードパーティ MIP ソルバーのラッパー。
  • CP-SAT ソルバー: SAT（適合性）方式を使用する制約プログラミング ソルバー。
  • 元の CP ソルバー: 制約プログラミング ソルバーです。

どの解法を使用すべきか

MIP ソルバーと CP-SAT ソルバーのどちらを使用するかを決定する明確なルールはありません。目安は次のとおりです。

  • MIP ソルバーは、標準の LP としてセットアップできるものの、上記の例のように任意の整数変数を使用して設定できる問題により適しています。
  • CP-SAT ソルバーは、上記の 2 番目の例のように、ほとんどの変数がブール値である問題により適しています。

整数変数とブール値変数の両方を持つ一般的な MIP では、通常、この 2 つの解法に明確な速度差がないため、選択は個人の好みによる場合があります。

MIP ソルバーと CP-SAT ソルバーの両方を使用する例については、割り当て問題の解決と、その他の割り当てのセクションをご覧ください。

整数計画の問題を解決するもう 1 つの方法は、ネットワーク フロー ソルバーを使用することです。
例については、最小コストフロー問題としての割り当てをご覧ください。
ネットワーク フローとして設定できる問題については、最小コストフロー ソルバーが MIP または CP-SAT ソルバーよりも高速になる場合があります。ただし、すべての MIP をこの方法で設定できるわけではありません。