9
$\begingroup$

A year ago, I had taken my master's degree class Optimisation Theory, and we were learning Dantzig-Wolfe Decomposition and Benders' Decomposition. I found it very challenging to use these algorithms since there are many iterations inside of them.

I would like to ask that is it now used commonly in research papers, or is it still applicable?

$\endgroup$

3 Answers 3

15
$\begingroup$

I don't know about "commonly" used, but Benders is still definitely in use, and I'm pretty sure D-W also is. Benders in particular has evolved beyond the original version created by Jack Benders. In particular, there is work on "combinatorial Benders cuts" [1], where "big M" constraints are replaced by a form of Benders cut, and "logic-based Benders decomposition". I have used a version of the latter a couple of times, where the subproblem is not necessarily a linear program and the Benders cuts are not derived from dual solutions. (In one case, our subproblem identified negative cycles in a network, and each cut was designed to break one such cycle.) There is also recent work on what was coined "implicit hitting set" problems [2], where cuts are generated using an "oracle" (a subproblem that is not necessarily a linear program).

[1] Codato, G. & Fischetti, M. Combinatorial Benders' Cuts for Mixed-Integer Linear Programming Operations Research, 2006, 54, 756-766

[2] Moreno-Centeno, E. & Karp, R. M. The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment Operations Research, 2013, 61, 453-468

$\endgroup$
1
  • $\begingroup$ I am grateful for your information Professor! Our professor likes to teach Optimization in a mathematical approach, and it interested me last year. Nevertheless, I was a little bit confused about Master algorithms, and their computational complexity. Now, everything is more straightforward! $\endgroup$
    – dozgunay
    Commented Aug 30, 2022 at 17:29
10
$\begingroup$

If you search for "Dantzig Wolfe" on Google Scholar, and remove all articles before 2022, you still have 427 papers that come out. So I think it is safe to say that DW is still popular and trendy in the OR field.

This is probably due to the fact that many industrial applications rely on the powerful Dantzig-Wolfe decomposition.

$\endgroup$
5
$\begingroup$

Yes. They are very popular for solving real world problems. Just search for “column generation”.

https://documentation.sas.com/doc/en/ormpug/v_003/ormpug_decomp_overview.htm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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