About
Benders Day is a one day workshop featuring invited talks on topics related to the work of Jacques Benders, in particular, Benders decomposition. The workshop takes place at Eindhoven University of Technology on May 31, 2024.
The workshop takes place at Filmzaal (first floor) of the Zwarte Doos building of Eindhoven University of Technology. The Zwarte Doos building is the first building when entering the campus from the direction of the central station, click here for directions.
Program
| 9:30 - 9:55 | registration |
| 9:55 - 10:00 | opening |
| 10:00 - 10:40 | John Hooker: Logic-Based Benders Decomposition |
| 10:40 - 11:20 | Ivana Ljubić: Benders Adaptive-Cuts Method for Two-Stage Stochastic Optimization |
| 11:20 - 11:40 | coffee break |
| 11:40 - 12:20 | Ward Romeijnders: Benders' Decomposition Algorithms for Stochastic Mixed-integer Programs |
| 12:20 - 12:35 | Cor Hurkens: Jacques Benders - a personal decomposition |
| 12:35 - 14:00 | lunch break |
| 14:00 - 14:40 | Stephen Maher: Should you implement Benders' decomposition? |
| 14:40 - 15:20 | Karen Aardal: Benders decomposition, a seminal result in the infancy of optimization |
| 15:20 - 15:40 | coffee break |
| 15:40 - 16:20 | Elina Rönnberg: Some experiences from designing acceleration techniques for logic-based Benders decomposition |
| 16:20 - 17:00 | Dries Goossens : How Benders decomposition changed sports scheduling |
Abstracts
Please click on a talk to see the corresponding abstract.
Karen Aardal: Benders decomposition, a seminal result in the infancy of optimization
I present the ideas behind the decomposition method by J.F. Benders, or the "partitioning procedure"
as he called it himself, and put it into historical context. Further, I link his method to other
decomposition methods and give some illustrations related to mixed-integer optimization.
Dries Goossens: How Benders decomposition changed sports scheduling
Even for sports leagues with a small number of teams, the construction of an (all-play-all) round-robin timetable taking into account various constraints (e.g., venue availability or travel distance), can be computationally challenging. It is therefore common to decompose the problem with a so-called first-break-then-schedule approach, which first decides when teams play home or away, and afterwards determines a compatible assignment of opponents. When there are more time slots available than games per team (and teams therefore do not play on all time slots), an alternative is the first-day-off-then-schedule approach which starts by deciding when teams receive a day of rest.
Despite the popularity of these approaches, a major unsolved question is how to efficiently backtrack between the different phases of the algorithm. Moreover, existing backtracking schemes can only cope with a very limited set of timetable requirements. In this talk, we discuss how traditional Benders' decomposition relates to the aforementioned approaches, and how Benders' cuts can be used to organize backtracking. To show the effectiveness and versatility of the proposed framework, we construct compact timetables that minimize the total number of travel trips, and time-relaxed timetables that either balance the games over the season or minimize the total differences in rest time of opposing teams. Furthermore, we discuss the quality of the obtained Benders' cuts.
John Hooker: Logic-Based Benders Decomposition
Benders decomposition is a highly successful optimization tool that has been applied to countless problems since its publication by Jacques Benders more than 60 years ago. Yet, its essential problem-solving idea is more general than is often recognized. The derivation of Benders cuts from the dual of the linear programming subproblem can be interpreted as a special case of logical inference. This insight allows extension of the classical method to a logic-based method in which the subproblem can in principle be any optimization problem, thus opening the door to much wider application. This talk explains the idea and surveys a rapidly growing literature that reports hundreds of new applications in such diverse areas as supply chain logistics, computer processor scheduling, organ transplantation, wind turbine maintenance, and search-and-rescue operations.
Ivana Ljubić: Benders Adaptive-Cuts Method for Two-Stage Stochastic Optimization
Benders decomposition is one of the most applied methods to solve two-stage stochastic problems (TSSP) with a large number of scenarios. The main idea behind the Benders decomposition is to solve a large problem by replacing the values of the second-stage subproblems with individual variables and progressively forcing those variables to reach the optimal value of the subproblems, dynamically inserting additional valid constraints, known as Benders cuts. Most traditional implementations add a cut for each scenario (multicut) or a single cut that includes all scenarios. In this talk, we present a novel Benders adaptive-cuts method, where the Benders cuts are aggregated according to a partition of the scenarios, which is dynamically refined using the LP-dual information of the subproblems. This scenario aggregation/disaggregation is based on the Generalized Adaptive Partitioning Method, which has been successfully applied to TSSPs. Our new method can be interpreted as a compromise between the Benders single-cuts and multicuts methods, drawing on the advantages of both sides, by rendering the initial iterations faster (as for the single-cuts Benders) and ensuring the overall faster convergence (as for the multicuts Benders). We will demonstrate how Benders adaptive-cuts can be applied to the Stochastic Multi-Commodity Network Design Problem and the conditional value-at-risk (CVaR) Facility Location Problem. The new method outperforms the other implementations of Benders methods, as well as other standard methods for solving TSSPs, in particular when the number of scenarios is very large. Moreover, our study demonstrates that the method is not only effective for the risk-neutral decision makers, but also that it can be used in combination with the risk-averse CVaR objective.
References: C. Ramirez-Pico, I. Ljubic, E. Moreno: Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs, Transportation Science, online first, (2023), https://doi.org/10.1287/trsc.2022.0073
Stephen Maher: Should you implement Benders' decomposition?
Benders' decomposition is an extremely popular mathematical programming technique commonly applied to solve computationally challenging problems.
While the basic algorithm of Benders' decomposition is quite simply described, the extensive literature on the topic has shown that many sophisticated, problem specific techniques must be implemented to make the Benders' decomposition algorithm effective.
The implementation burden of an effective Benders' decomposition algorithm has motivated to the development of numerous general frameworks, such as those available in CPLEX and SCIP, that aim to high performance general solvers.
While these frameworks exist, the question still remains: are the frameworks enough to effectively apply Benders' decomposition to most problems, or is it necessary to develop a custom implementation with problem specific enhancement techniques?
This talk will discuss the benefits and limitations of general Benders' decomposition frameworks and provide an assessment on whether custom implementations are still the most effective.
Finally, this talk will propose an alternative structure for general Benders' decomposition frameworks that aims to address the limitations of those currently available and hopefully eliminate the need for custom Benders' decomposition implementations.
Ward Romeijnders: Benders' Decomposition Algorithms for Stochastic Mixed-integer Programs
We discuss new and existing Benders' decomposition algorithms for two-stage stochastic mixed-integer programs. In our new algorithm, we iteratively construct tighter lower bounds of the expected second-stage cost function using a new family of so-called scaled optimality cuts. We derive these cuts by parametrically solving extended formulations of the second-stage problems using deterministic mixed-integer programming techniques. The advantage of these scaled cuts is that they allow for parametric non-linear feasibility cuts in the second stage, but that the optimality cuts in the master problem remain linear. We establish convergence by proving that the optimality cuts recover the convex envelope of the expected second-stage cost function.
Elina Rönnberg: Some experiences from designing acceleration techniques for logic-based Benders decomposition
Thanks to its general nature, logic-based Benders decomposition can be applied to a variety of problem types. In particular, there are many successful implementations for solving large-scale discrete optimisation problems where the decomposition allows for hybridisation of solution methods. In addition to making the decomposition in a way that exploits problem structure and choosing the right type of solution methods for the master problem and subproblem, the computational efficiency relies on appropriate use of acceleration techniques. These are often tailored to the problem structure and the most common ones include strengthening the master problem by a subproblem relaxation, designing analytical Benders cuts, and performing cut strengthening. In addition, heuristic strategies can further improve the computational performance.
In this talk, I will give a unified description of some generic strategies for cut strengthening based on making searches that systematically evaluate different subsets of master problem variables and share some experiences from computational experiments made for a large and diverse set of problem instances. Based on this description, we propose how the cut strengthening can be extended to also search systematically for feasible solutions. The impact of applying acceleration techniques will be demonstrated for some practical applications that we have addressed.
Sponsors
