How Python Language Models with MindOpt

本稿は連載記事の第 2 回です。混合整数線形計画法に関する個人的な定義を共有し、例を示します。最後に、MindOpt Python 言語 API を使用して、混合整数線形計画問題の例をモデリングして求解し、解の結果を示します。

MindOpt Python、C、C++ 言語で LP、MILP、QP 問題を求解するシリーズ

• Python：線形計画法の LP 問題、混合整数線形計画法の MILP 問題 (本章)、二次計画法の QP 問題

• C：線形計画法の LP 問題、混合整数線形計画法の MILP 問題、二次計画法の QP 問題

• C++：線形計画法の LP 問題、混合整数線形計画法の MILP 問題、二次計画法の QP 問題

インストール

MindOpt 最適化ソルバーはこちらから無料でダウンロードしてインストールできます。インストール手順が見つからない場合はこちらを参照してください。

混合整数線形計画法

個人的な見解ですが、混合整数線形計画法と線形計画法の違いは、線形計画で目的関数の最適値を求める際、決定変数が連続変数であり、整数でも小数でも構わないのに対し、混合整数線形計画法では 1 つ以上の変数が必ず整数でなければならない点にあると考えます。

たとえば、古典的なナップサック問題があります。テーブル上に複数のアイテムがあり、それぞれ固有の価値と重みがありますが、バッグの重量には制限があります。どのアイテムをバッグに入れるべきでしょうか。バッグの重量範囲内で、バッグ内のアイテムの総価値が最大になるのはどの組み合わせでしょうか。ここで選択するアイテムは整数単位であり、小数で分割することはできません。たとえば、ドライヤーは半分に切ることができず、半分だけ持っていくことはできないということです。

数学的形式による混合整数線形計画問題：

混合整数線形計画法は、多くの場合、求解がより困難です。求解には分枝限定法や切除平面法などの手法を使用でき、部分問題に分割して線形計画 (LP) 求解モジュールを呼び出します。MindOpt も今年、混合整数線形計画 (MILP) の求解機能をリリースしました。次に、その使い方を例で示します。

例

前章の線形計画と同様に、混合線形計画問題の例について仮定を設け、数式のように抽象的ではなく、実生活の具体的な例として捉えます。

工場に 1 種類の原料があり、さまざまな部品の毛坯を生産できるとします。各部品の生産方法も複数あります。各生産方法で異なる部品の毛坯の数と各部品の必要数量を得られますが、部品のうちの 1 つは必ず整数でなければなりません。各部品の必要数量を満たしつつ、使用する原料を最少にするにはどう生産すればよいでしょうか。

数式による例

混合整数線形計画問題の例：

Python + MindOpt コード実装

コア部分で使用する主な API は次のとおりです：

model = MdoModel()

model.set_ int_ attr(MDO_INT_ATTR.MIN_SENSE, 1)

x.append(model.add_var(0.0, 10.0, 1.0, None, "x0", True))

model.add_ cons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0")

model.solve_ prob()

model.display_ results()

以下は完全なコード例です。コピーして test_MILP.py ファイルとして保存できます。

MindOpt による求解結果

次に、コマンドラインで python test_MILP.py のようにコードを実行すると、以下のように解の結果が得られます。その後には私が追加したコメントが続きます。