I am looking for a textbook on linear programming decomposition fundamentals. The book should be clear and easy-to-follow for self study and should include examples to illustrate the concepts.
$\begingroup$ Would you see this link? $\endgroup$– A.OmidiFeb 22, 2021 at 5:57
1$\begingroup$ @ A. Omidi Book chapters and papers are for the expert, not for the beginner. $\endgroup$– DSPinfinityFeb 22, 2021 at 6:07
2$\begingroup$ AFAIK, implementing decomposition method is very tricky and needs special skills in theory and implementation and is not easy to many OR experts too. But, if you are interested to begin I recommended this resource. $\endgroup$– A.OmidiFeb 22, 2021 at 7:15
I propose reading the following textbook:
Linear Programming and Network Flows by by Hanif D. Sherali, John J. Jarvis, and M. S. Bazaraa
I read the first 7 chapters of the book a long time ago (during my Bachelor studies), and I really enjoyed it. Chapter 7 of the book titled
THE DECOMPOSITION PRINCIPLE introduces Dantzig-Wolfe decomposition and its relationships with Benders decomposition and Lagrangian relaxation (for linear programming). As in other chapters of the book, Chapter 7 includes quite a few numerical examples which are very insightful.
1$\begingroup$ Wow, Aussies are really getting the shafteroo. AUD 257.95 on Wiley Australian website, which is USD 204.17 at current exchange rate. Meanwhile, USD 155.00 on Wiley U.S. site, and USD 82.24 new at amazon.com . VAT can be only a modest portion of that. $\endgroup$ Feb 22, 2021 at 22:58
$\begingroup$ @MarkL.Stone Yeah, book prices are crazy high Down Under! $\endgroup$– rasulFeb 23, 2021 at 4:24
I took the course 42136 for Benders decomposition and Dantzig-Wolfe (DW) decomposition at Technical University of Denmark. Besides the textbook [conejo2006decomposition] (mentioned by @A.Omidi as well), following materials are recommended:
- [carøe1998l], chapter 5.1 in [birge2011introduction] for L-shaped Benders Decomposition, in terms of two-stage (stochastic) MILP with first-stage integer variables
- [desrosiers2005primer] for basics of DW
- [feillet2010tutorial] for vehicle routing with DW
- [merle1999stabilized] and [rousseau2007interior] for stabilization in column generation in DW
- [lübbecke2005selected] for DW in depth
By the way, Benders' decomposition is integrated in CPLEX Versions 12.7 and later. We got a guest lecture from IBM that time. See How to implement Benders' decomposition using CPLEX, IBM support. In particular:
The Benders' strategy parameter controls how CPLEX does the decomposition. The easiest way to use it consists of setting this parameter to 3 to instruct CPLEX to do the decomposition automatically, putting the constraints that intersect only integer variables into the master problem.
- [conejo2006decomposition] Conejo, A. J., Castillo, E., Minguez, R., & Garcia-Bertrand, R. (2006). Decomposition techniques in mathematical programming: engineering and science applications. Springer Science & Business Media.
- [carøe1998l] Carøe, C. C., & Tind, J. (1998). L-shaped decomposition of two-stage stochastic programs with integer recourse. Mathematical Programming, 83(1), 451-464.
- [birge2011introduction] Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.
- [desrosiers2005primer] Desrosiers, J., & Lübbecke, M. E. (2005). A primer in column generation. In Column generation (pp. 1-32). Springer, Boston, MA.
- [lübbecke2005selected] Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations research, 53(6), 1007-1023.
- [rousseau2007interior] Rousseau, L. M., Gendreau, M., & Feillet, D. (2007). Interior point stabilization for column generation. Operations Research Letters, 35(5), 660-668.
- [merle1999stabilized] Du Merle, O., Villeneuve, D., Desrosiers, J., & Hansen, P. (1999). Stabilized column generation. Discrete Mathematics, 194(1-3), 229-237.
- [feillet2010tutorial] Feillet, D. (2010). A tutorial on column generation and branch-and-price for vehicle routing problems. 4or, 8(4), 407-424.
Some more references, different than those in the other answers. I added some application papers too. I often find a practical example rather helpful to understand a specific technique.
Classical Benders decompositon:
- Martin R.K. (1999) Projection: Benders’ Decomposition. In: Large Scale Linear and Integer Optimization: A Unified Approach. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-4975-8_10
- Bonami P., Salvagnin D., Tramontani A. (2020) Implementing Automatic Benders Decomposition in a Modern MIP Solver. In: Bienstock D., Zambelli G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science, vol 12125. Springer, Cham. https://doi.org/10.1007/978-3-030-45771-6_7
- Lecture notes Benders Decomposition and Delayed Constraint Generation https://personal.eur.nl/birbil/ie606/05_Benders_Dec/05_Benders_Dec_Octave.html
Combinatorial Benders decomposition:
- Codato, Gianni, and Matteo Fischetti. "Combinatorial Benders' cuts for mixed-integer linear programming." Operations Research 54.4 (2006): 756-766.
- Trick, M. (2010) Combinatorial Benders Approaches to Hard Problems. https://mat.tepper.cmu.edu/trick/Talks/alio.pptx
- application: Bai, Lihui, and Paul A. Rubin. "Combinatorial benders cuts for the minimum tollbooth problem." Operations research 57.6 (2009): 1510-1522.
- application: Peterson, Benjamin, and Michael A. Trick. "A Benders’ approach to a transportation network design problem." International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer, Berlin, Heidelberg, 2009.
Logic-based Benders decomposition:
- Hooker, John N., and Greger Ottosson. "Logic-based Benders decomposition." Mathematical Programming 96.1 (2003): 33-60.
- Thorsteinsson, Erlendur S. "Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.
- Colin R. Reeves (Ed.). 1993. Lagrangean Relaxation (chapter 6). In: Modern heuristic techniques for combinatorial problems. John Wiley & Sons, Inc., USA.
- application: Göthe-Lundgren, Maud, Francesco Maffioli, and Peter Värbrand. A Lagrangean decomposition approach for a prize collecting traveling salesman type problem. Universitetet i Linköping/Tekniska Högskolan i Linköping. Department of Mathematics, 1994.