Benders’ decomposition (BD) is a framework for solving optimization problems by removing some variables and modeling their contribution to the original problem via so-called Benders cuts. While many advanced optimization techniques can be applied in a BD framework, one central technique has not been applied systematically in BD: symmetry handling. The main reason for this … Read more
The Stochastic Unit Commitment (SUC) problem models the scheduling of power generation units under uncertainty, typically using a two-stage stochastic program with integer first-stage and continuous second-stage variables. We propose a new Benders decomposition approach that leverages an extended formulation based on interval variables, enabling decomposition by both unit and time interval under mild technical … Read more
In the aftermath of an earthquake, one of the most critical needs is medical care for the injured. A large number of individuals require immediate attention, often overwhelming the available healthcare resources. The sudden surge in demand, coupled with limited resources, route congestion and infrastructure damage, makes immediate medical care provision a significant challenge. This … Read more
Tsunamis, primarily triggered by earthquakes, pose critical threats to coastal populations due to their rapid onset and limited evacuation time. Two main protective actions exist: sheltering in place, which requires substantial retrofitting investments, and evacuation, which is often hindered by congestion, mixed travel modes, and tight inundation times. Given pedestrians’ slower movement and restricted evacuation … Read more
Bulk-robust optimization is a recent paradigm for addressing problems in which the structure of a system is affected by uncertainty. It considers the case in which a finite and discrete set of possible failure scenarios is known in advance, and the decision maker aims to activate a subset of available resources of minimum cost so … Read more
Benders decomposition is a technique to solve large-scale mixed-integer optimization problems by decomposing them into a pure-integer master problem and a continuous separation subproblem. To accelerate convergence, we propose Random Partial Benders Decomposition (RPBD), a decomposition method that randomly retains a subset of the continuous variables within the master problem. Unlike existing problem-specific approaches, RPBD … Read more
We introduce a novel technique to generate Benders’ cuts from a conic relaxation (“corner”) derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation … Read more
We show how to extract alternative solutions for optimization problems solved by Benders Decom- position. In practice, alternative solutions provide useful insights for complex applications; some solvers do support generation of alternative solutions but none appear to support such generation when using Benders Decomposition. We propose a new post-processing method that extracts multiple optimal and … Read more
We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more
Efficient operation of underground railway systems is critical not only for maintaining punctual service but also for minimizing energy consumption, a key factor in reducing operational costs and environmental impact. To evaluate the energy consumption of the timetables, this paper delves into the development of mathematical models to accurately represent energy dynamics within the underground … Read more