6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Would you see this link? $\endgroup$
    – A.Omidi
    Feb 22 at 5:57
  • 1
    $\begingroup$ @ A. Omidi Book chapters and papers are for the expert, not for the beginner. $\endgroup$ Feb 22 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.Omidi
    Feb 22 at 7:15
8
$\begingroup$

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.

$\endgroup$
2
  • 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 at 22:58
  • $\begingroup$ @MarkL.Stone Yeah, book prices are crazy high Down Under! $\endgroup$
    – rasul
    Feb 23 at 4:24
7
$\begingroup$

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.
$\endgroup$
4
$\begingroup$

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:

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.