1. 概要

このチュートリアルでは、整数線形計画法（ILP）について詳しく説明します。ILPのバリエーションも例とともに示します。

2. 整数計画法（ILP）の概要

整数線形計画法は、線形コスト関数を最適化する方法であり、線形等式および線形不等式に関するさまざまな制限を満たす必要があります。 これは線形計画法の拡張であり、すべての変数は整数である必要があることを示す追加の制約があります。ILP問題を数学的に定義しましょう。

   

   

   

   

   

   

   

ここで、は決定変数を表し、はコスト、は係数、は要件を表します。

これは、マトリックス形式で表現することもできます。

   

   

   

   

ここで、はコストベクトルを表し、係数行列を表し、は要件ベクトルとです。

3. 最大化を使用したILPの例

ロブが2つの仕事をしているが、週に数時間以上働けない場合を考えてみましょう。 ロブは仕事で$を稼ぎ、仕事で$を稼ぎます。 ロブは自分の収入を最大化したいと考えています。

仕事に従事した時間数と仕事に従事した時間数とします。 時間数は正で丸められている必要があります。 したがって、目的関数は総収入であり、彼が働くことができる最大時間数は、時間の値とともに制約です。

これをILP問題として定式化しましょう。

   

   

   

   

4. 最小化されたILPの例

アレックスは低コレステロールの食事をしています。 彼は豆腐とパスタを食べる日数を選択して、少なくとも grのタンパク質を摂取しながら、コレステロール摂取量を最小限に抑える必要があります。パスタにgrタンパク質とgrコレステロールが含まれていると考えてみましょう。 豆腐にはgrタンパク質とgrコレステロールが含まれています。 これをILP問題として定式化できます。

   

   

   

   

ここでは、アレックスがパスタを食べる日数を表し、アレックスが豆腐を食べる日数を表します。

5. マキシミンILP

解決する問題で多数の決定変数の最小値を最大化する必要がある場合、マキシミンILPを使用できます。 マキシミンの目的を数学的に表すには、変数と定数を定義する必要があります。

  • の決定変数
  • およびの定数
  • の定数

マキシミン目的関数は次のように定義できます。

   

このモデルは、次のように補助決定変数を追加することにより、単純な最大化ILPに変換できます。

   

など：

   

   

   

たとえば、 整数の最小値を最大化し、それらの数の合計をにする必要がある場合、この問題を最大ILP問題として定式化できます。

   

   

このマキシミン問題は、補助変数を導入することによって代替的に表現することができます :

   

   

   

   

   

   

6. ミニマックスILP

解決する問題で多数の決定変数の最大値を最小化する必要がある場合、ミニマックスILPを使用できます。 ミニマックス目的関数は次のように定義できます。

   

これにはいくつかの制約があります。 このモデルは、次のように補助決定変数を追加することにより、単純な最大化に変換できます。

   

など：

   

   

   

整数の最大値を最小化し、それらの数の合計がでなければならない場合、この問題をミニマックスILP問題として定式化できます。

   

   

このマキシミン問題は、補助変数を導入することによって代替的に表現することができます :

   

   

   

   

   

   

   

7. 結論

このチュートリアルでは、整数線形計画法（ILP）を定義しました。 最大化、最小化、ミニマックス、マキシミンなど、ILPのバリエーションを実際の例で説明しました。