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
This paper investigates a presolving method for handling symmetries in mixed-binary programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables will produce an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for … Read more
Inverse optimization (IO) has emerged as a powerful framework for analyzing prescriptive model parameters that rationalize observed or prescribed decisions. Despite the prevalence of discrete decision-making models, existing work has primarily focused on continuous and convex models, for which the corresponding IO problems are far easier to solve. This paper makes three contributions that broaden … 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
We introduce the notion of projection-width for systems of separable constraints, defined via branch decompositions of variables and constraints. We show that several fundamental discrete optimization and counting problems can be solved in polynomial time when the projection-width is polynomially bounded. These include optimization, counting, top-k, and weighted constraint violation. Our results identify a broad … Read more
We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair … Read more
The interdiction defense (ID) problem solves a defender-attacker-defender model where the defender and attacker share the same set of components to harden and target. We build upon the best response intersection (BRI) algorithm by developing the BRI with suboptimal solutions (BRI-SS) algorithm to solve the ID problem. The BRI-SS algorithm utilizes off-the-shelf optimization solvers that … Read more
Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always … 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
This paper investigates the a-posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree’s branching … Read more