Textbook recommendation for linear programming decomposition fundamentals

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Lagrangean Decomposition:

• 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.