什麼是混合整數線性規劃(MILP)模型？
12-06
要了解什麼是混合整數線性規劃模型，第一步是要了解什麼是線性規劃模型(Linear Programming, LP)。LP的定義比較簡單，它指的就是目標函數是線性的，所有約束也是線性的，最後，決策變數可以取任何的實數。舉個很經典的飲食問題：
超市裡頭有賣3種食品，玉米，牛奶和麵包，價格，所含的維他命A和卡路里的信息見上表。現在的問題是買多少份的玉米，牛奶，麵包，使得總價格最低，而維他命A的總攝取量不小於500但不大於50000，卡路里的總攝取量不小於2000但不大於2250。這個問題的數學描述如下
現在回到之前的問題，如果在線性規劃問題中有部分決策變數，比如上面的X_corn要求必須是整數， 那麼這時的規劃問題就轉變成混合整數線性規劃問題了。
混合整數規劃問題，顧名思義，就是優化問題里不止有continous variable,也有integer variable.
舉例： min x1+x2
subject to: x1-2x2&>=5
3x1+x2&>=2
x1in Integer, x2&>=0
這類問題一般是NP-hard，也就是一般沒有polynomal複雜度的演算法。
此外，該領域的科研熱點是，better formulation以及模型的分解方法，例如Benders" Decomposition, Column Generation, Row generation等等。
歡迎關注我的運籌學專欄，了解更多：
[運籌帷幄]大數據和人工智慧時代下的運籌學
離散/整數/組合/非凸優化概述及其在AI的應用
https://zhuanlan.zhihu.com/p/27659600 （混合整數規劃/離散優化的精確演算法--分支定界法及優化求解器）
推薦閱讀：