• 整數最佳化

需要部分變數為整數的線性最佳化問題稱為混合整數程式 (MIP)。

這些變數可透過以下方式產生：

  • 「整數變數」，代表汽車或電視組合等項目的數量。問題在於判斷要產生多少商品才能盡可能提高利潤。
    這類問題通常可以設為標準線性最佳化問題，但新增要求變數必須為整數。下一節則顯示這類問題的示例。

  • 代表含 0 到 1 值的決定布林值變數。
    舉例而言，假設有一個問題涉及將工作站指派給工作 (請參閱「指派」)。如要設定這類問題，您可以定義當工作站 i 指派給工作 j 時，等於 1 的布林變數 xi,j，反之則為 0。

如需整數最佳化的入門入門，建議您參閱 Mosek 模型教戰手冊。

工具

Google 提供幾種解決 MIP 問題的方法：

  • MPSolver：這個包裝函式適用於多個第三方 MIP 解決方案的包裝函式，使用的是標準分支版本與繫結技術。
  • CP-SAT 解題工具：使用 SAT (滿意度) 方法的限製程式設計解決方案。
  • 原始 CP 解析器：限製程式設計解析工具。

我該使用哪個求解器？

沒有硬性規定，無法判斷要使用 MIP 解析器還是 CP-SAT 溶液。一般指南：

  • MIP 解題工具更適合可設為標準 LP，但使用任意整數變數 (例如上方第一個範例) 的問題。
  • 如果問題中的大部分變數是布林，例如上述的第二個範例，就更適合使用 CP-SAT 解題工具。

對於同時具有整數和布林值變數的一般 MIP，這兩個解析器之間的速度通常沒有明顯差異，因此您的選擇可能會按照個人偏好選擇。

如需同時使用 MIP 和 CP-SAT 解析器的範例，請參閱解決指派問題和其他指派區段。

另一個解決整數程式設計問題的方法是使用網路流程解析工具。
如需範例，請參閱「指派為最低費用流程問題」。
對於可設為網路流程的問題，最低成本流量解析工具的速度可能比 MIP 或 CP-SAT 解析器更快。不過，並非所有 MIP 都能以這種方式設定。