Saturday, January 21, 2017

Fischetti on Benders Decomposition

I just came across slides for a presentation that Matteo Fischetti (University of Padova) gave at the Lunteren Conference on the Mathematics of Operations Research a few days ago. Matteo is both expert at and dare I say an advocate of Benders decomposition. I use Benders decomposition (or variants of it) rather extensively in my research, so it ends up being a frequent theme in my posts. Those posts tend to generate more comments than posts on other topics. Apparently Matteo and I are not the only BD users out there.

I don't know that I would recommend Matteo's presentation as the starting point for someone who has heard of BD but never used it, but I certainly recommend having a look at the slides for anyone who has any familiarity with BD. Matteo provides several interesting perspectives as well as a tip or two for potentially improving performance. I learned a few new things.

In a sad coincidence, Professor Jacques Benders, the originator of Benders decomposition, passed away at age 92 just eight days before Matteo's presentation.

3 comments:

  1. Hi Paul,
    I also read those slides and some of Dr. Fischetti's paper. I have one implementation of Benders Decomposition based on his formulation. I find the converging speed is quite fast when testing on uncapacitated facility location problem. However, after the algorithm has already reached the best solution for the benchmark, which is published on the internet, I find the algorithm still needs lots of time to handle the branching process.
    Could you please give me some suggestions, or recommend some papers on how to decrease the branching process faster?
    Thx.

    ReplyDelete
    Replies
    1. I'm not sure what you mean. If you're saying it takes a long time to prove optimality (slow-moving bound), that's common. Depending on what solver you use, you may be able to switch some parameter late in the search and have the solver put more effort into bound tightening. Frequently, though, the only alternative to patience is to find a tighter formulation for the problem (or find some problem-specific cuts you can add to tighten the bound).

      Delete
    2. Thanks. I think I have the answer of my question :) I should focus on the formulation of the model or tune the solver.

      Delete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.