Python での整数計画法

整数計画問題は、問題に関係する変数の一部またはすべてが整数であることを提供することによって、数学的最適化または実現可能性を確保するために構築された問題です。

問題のいくつかの決定変数が離散的ではないことが判明したとします。 その場合、それらは混合整数問題として分類され、より一般的には MIP/MILP (混合整数線形計画法) として知られています。

そのため、この Python の記事では、Python でこの種の問題を解決するために使用できるさまざまな方法論とライブラリについて説明します。

Python における混合整数プログラミングの問題

混合整数計画法 (MIP) 問題は、いくつかの決定変数が最適解のために厳密に整数値であることが保証される問題です。

これらの整数変数を使用すると、プログラマが最も効率的かつ正確に定義して解決するために使用できる有用な最適化問題の範囲とスコアが広がります。

MIP の重要なシナリオは、バイナリと見なされる決定変数です。 つまり、0 または 1 としてのみ表すことができます。

これらは通常、バイナリ整数値と呼ばれます。 これらの決定変数は通常、慎重な計算に基づいて True/False または Yes/No の決定をモデル化するために使用されます。

現在、この種の問題に対処するために設計されたソルバーがいくつかあります。

これらには、最新の Gurobi と Python-MIP が含まれます。これらは、最も一般的に知られ、人気のある混合整数線形計画法ソルバーの 1つです。

別の高度に構成可能な MIP ソルバーは、CBC または COIN-OR Branch-&-Cut ソルバーです。 最後に、Python-MIP を使用すると、カスタム アプリケーション向けの高性能な MIP ベースのソルバーを簡単に開発できます。

これは、ハイエンドで最新の機能を提供します。詳細については、以下で説明します。

MIP/MILP 用の Python ツール: Python-MIP

Python には、MIP と呼ばれる膨大なライブラリがあります。これは基本的に、混合整数線形計画法の問題をモデリングして解決するための Python ベースのツールのコレクションです。

MIP は、Pulp に大きく影響を受けた構文を使用して、lazy Constraint、MIPstart、solution pools、および cut generation などの高度で効率的な機能へのアクセスをユーザーに提供します。

その顕著な機能の多くは次のとおりです。

これで、混合整数計画法とは何か、および最も効率的で有効に最適化された方法で解く必要がある整数計画問題をガイドするために使用できるさまざまなソルバーがわかりました。

特定の問題の解決策を見つけるために、言及されているすべてのソルバーの公式ドキュメントを調べることもできます。