I am trying to understand how to reproduce CPLEX’s automatic Benders decomposition using callbacks in Julia (via CPLEX.jl). CPLEX provides an automatic Benders mode, and the underlying procedure is described in the paper “Implementing Automatic Benders Decomposition in a Modern MIP Solver.”
In my experiments, I can partially replicate the in–out technique at the root node using callbacks, but I am not able to replicate CPLEX’s behavior deeper in the branch-and-bound tree.
I have two main questions:
Multithreading and callbacks:
CPLEX’s automatic Benders mode appears to generate cuts across multiple threads during the branch-and-bound search. If one tries to implement Benders via user callbacks, multithreading is typically unsafe unless the solver guarantees thread safety. How does CPLEX handle this internally? Are they avoiding callbacks entirely, or do they have a thread-safe mechanism not exposed to users?
Efficiency differences:
When I disable all other MIP cuts and restrict CPLEX to a single thread, the automatic Benders decomposition still produces far fewer Benders cuts and solves significantly faster than my callback-based implementation. I am unsure why this occurs. In my callback implementation, the branch-and-bound tree explores many integer nodes for capacitated facility-location problems, and this leads to the generation of a very large number of Benders cuts. What aspects of CPLEX’s internal Benders implementation allow it to use fewer cuts and avoid exploring so many nodes?
I attached the example code below. Any insights into how CPLEX’s automatic Benders decomposition differs from what can be implemented through user callbacks would be greatly appreciated.
Because CPLEX is proprietary software, we don’t know how they implement things internally. Unfortunately, that means you’re unlikely to get any concrete answers to your questions
That’s true lol. Since I’m trying to develop a JuMP-based generic Benders decomposition library, I ran into these questions and became very curious about how CPLEX manages this internally.
I took a read of the abstract and introduction of that paper and I feel like I can safely skip that paper. (one very minor reason is that they only mentioned “CGLP”, but nowadays we can also generate cuts from MILP subproblems)
Benders decomposition is under the umbrella of decomposition techniques for large-scale structured MILPs. Decomposition techniques just depend very much on specific problems.
I think the direction is not very appealing. The adj. “Generic” means the user just voluntarily give up opportunities to maximize algorithm performance for a specific class of problems.
I took a read of the abstract and introduction of that paper and I feel like I can safely skip that paper. (one very minor reason is that they only mentioned “CGLP”, but nowadays we can also generate cuts from MILP subproblems)
Benders decomposition is under the umbrella of decomposition techniques for large-scale structured MILPs. Decomposition techniques just depend very much on specific problems.
Yes, although the paper focuses mainly on CGLP, I agree that decomposition techniques are highly problem-dependent and that exploiting structure can certainly lead to much stronger cuts. However, that does not imply that generic techniques are useless. Methods like inout technique and GBC, for example, remain broadly applicable across many problem classes.
The adj. “Generic” means the user just voluntarily give up opportunities to maximize algorithm performance for a specific class of problems.
Regarding the second point, you are absolutely right. “Generic” was not the most accurate word for what I intended. What I mean is that, in my research, I often work with multiple problems, multiple model formulations, multiple Benders cut generation schemes, and various solving workflows. At the moment, I haven’t found an existing library that can conveniently support this diversity.
My goal is to design a modular framework that can accommodate different problem structures and algorithmic variants, so that I can use one unified codebase to conduct comprehensive computational experiments. The intention is to achieve a balance between flexibility, ease of use, and computational performance, and to provide a platform that facilitates developing, analyzing, and benchmarking Benders decomposition–based algorithms.
Cool! A generic benders library for JuMP is often asked for. Do you take monolithic problem and split it apart or make the user build separate sub problems (a la SDDP.jl)?
Manual construction:
Users can manually build the master and subproblems using macros, similar to the workflows in SDDP.jl and StochasticPrograms.jl.
Automatic decomposition:
There is also an automatic decomposition function that takes a JuMP model as input and returns the corresponding master problem and subproblem(s).
Problem-specific customization:
I provide an interface that allows users to define their own methods for constructing the master and subproblems, using multiple dispatch based on the problem type(data) and the chosen cut-generation strategy.
You’re just encouraging interface development, but @ASUKaiwenFang 's real concerns here are performance.
First, from my perspective, Benders decomposition aims to build a strong dual bound at the root node (i.e. before branch-and-bound is enacted). In other words, if I bother to use a Benders decomposition framework rather than solving a monolithic MIP, I wish I can get a narrow rgap at the root node before branch-and-bound happens.
If your Benders master problem is an MIP (e.g. a unit commitment problem), then typically you need at first generate trial points with an LP-relaxed master problem. In this phase you don’t need the callback APIs provided by CPLEX.
The branch-and-bound (combinatorial) phase is exactly why MIP is NP-hard. Therefore there are many issues at this phase, e.g. how should you generate cut, within a callback or not, at integer nodes or not… These things are just very tricky. I’ve discussed these issues with other researchers before.
Hi Walter, I’m going to ask that we keep discussions positive. Just because you don’t find a JuMP extension for Benders interesting doesn’t mean that others won’t. Kaiwen and I are both well aware of the numerical and algorithmic challenges with implementing Benders.
You’re just encouraging interface development, but @ASUKaiwenFang 's real concerns here are performance.
Both aspects are within the scope of what I am considering. Since there are not many publicly available reference implementations of Benders decomposition, I appreciate any suggestions or perspectives that others can share.
The branch-and-bound (combinatorial) phase is exactly why MIP is NP-hard. Therefore there are many issues at this phase, e.g. how should you generate cut, within a callback or not, at integer nodes or not… These things are just very tricky. I’ve discussed these issues with other researchers before.
You’re right — it is quite tricky. Even though there may be no universal criterion that works for all problems, if we can design modular interfaces to handle some techniques, users would be able to “play” with Benders decomposition like LEGO, assembling different components as needed.
