如何理解benders decomposition在混合整數規劃中的應用？

義大利潘多瓦的Matteo Fischetti - DEI是Benders世界級的專家，有幸和他吃過飯，還有和他的得意門生Andrea Lodi合作過。
簡單得說，約束不等式太多，比如1000個，但是optimal solution裡面，bounding/active的不等式可能只有100個，另外900個都是多餘的。所以先從很小一部分不等式開始算master problem，比如10個，然後有個subproblem，用來add constraints on the fly。如此循環。然後加到100個不等式的時候，subproblem找不到新的不等式了，就optimal了。
一般情況下，master problem仍舊是一個integer or mixed integer programming, subproblem是一個LP，用來加Benders" feasibility cut or optimal cut,前者是那個LP問題的extreme ray（換句話說LP unbounded）,後者是LP bounded 情況下的最優解（一般是唯一的？）。當LP unbounded的時候，一般每一次subproblem可以加不止一條feasiblity cut，然後optimality cut的質量一般比前者要好。
關於什麼問題適用於benders，如開頭所說，當constraints個數很大，或者exponentially many的時候（這種情況比如TSP的subtour elimination constaints，不過這個已經可以算cutting plane method了）。Benders應用得很成功的案例，比如multi-commodity network flow problem.另外一種情況，是當master problem的係數矩陣有特殊性質，即decomposible的時候，這樣可以把master problem分成一個個小的MP。

歡迎關注我的運籌學專欄，會陸續發布運籌相關知識：

[運籌帷幄]大數據和人工智慧時代下的運籌學 - 知乎專欄

最後按照慣例廣告一波

優化數據科學領域尋博士碩士學術合作，承接工業界項目，歡迎訪問海德堡組合優化實驗室 - Ruobing Shen的文章 - 知乎專欄