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.
Saturday, January 21, 2017
6 comments:
Due to intermittent spamming, comments are being moderated. 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 Operations Research Stack Exchange.
Subscribe to:
Post Comments (Atom)
Hi Paul,
ReplyDeleteI 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.
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).
DeleteThanks. I think I have the answer of my question :) I should focus on the formulation of the model or tune the solver.
DeleteHi Paul,
ReplyDeleteThere is a question confusing me. Can standard Benders decomposition (not generalized benders decomposition) be applicable to some special non-linear problem. For example, min 5*x*y, st: 2*x+x*y>=5, x∈R+,y∈Z+. The origin problem is a non-linear problem, but once we fix y's value, we can obtain a linear subproblem, and we keep the complicated variables in master problem. Benders cuts generate as usuall in standard Benders decomposition. It's seem to be correct. I try to find some examples which implies this method, but i can't find any examples like this. So, whether is Benders decomposition applicable to this kind of non-linear problem(with the term like x*y, x is continues variable, y is integer binary)? If not, how generalized Benders decomposition, or there has any other better methods?
Standard Benders definitely does not apply to your problem, nor can I see a way to apply any obvious generalization of Benders to it. The first difficulty is that, in the LP subproblem, the inherited value of $y$ appears in the constraint coefficients, which means that it affects the subproblem solution nonlinearly. For instance, in your example, the solution to the subproblem is $x=\frac{25\hat{y}}{2+\hat{y}}$ where $\hat{y}$ is the value of $y$ inherited from the master problem. The second difficulty is that you need to translate the subproblem solution into linear constraints on $y$, not the specific value $\hat{y}$. The genius of what Benders did was the recognition that LP duality would let him generalize a subproblem solution solution from one specific value of the discrete variable to a valid inequality on all (feasible) values. I do not see any way to do that when $y$ shows up in the subproblem constraint coefficients.
DeleteAs far as any better methods go, I am not up to date on mixed-integer nonlinear programming, and I am afraid I have nothing to suggest.
Thanks. This problem is belong to Bilinear problem. Maybe i should refer to more papers about that.
Delete