In October 2026 two independent groups claimed deterministic algorithms that count the satisfying assignments of a k-CNF formula in time 2^{o(n)}, refuting the Exponential Time Hypothesis (ETH). We ask what these claims imply for the exact analysis of equilibria in games where each player interacts with a bounded number of others. Conditional on the claimed … Read more
Explainability is a growing concern for optimization models used as decision-making tools. It aims to help a stakeholder understand why a model recommends a given outcome, typically by exhibiting the elements of the input that account for this outcome. We study this question for linear two-stage stochastic programs, and explain the returned decision by a … Read more
Classic linear bilevel optimization assumes that the upper-level decision impacts only the right-hand side of the lower-level constraints, which guarantees a solution under mild conditions. We study existence of solutions for linear bilevel problems with rotations (LBPR, for short), i.e., problems for which the upper-level decision modifies the left-hand side coefficients of the linear follower … Read more
Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce … Read more
The fortification problem (FP) is commonly formulated as a defender-attacker-defender (DAD) model. In this setting, a planner first hardens up to h components, then an attacker interdicts up to k components, and finally the defender solves a recourse problem to maintain system operations. A key limitation of the DAD model is the assumption that the … Read more
We study pessimistic bilevel optimization with bilinear objectives and linear constraints. Assuming a compact polyhedral leader domain, nonempty follower solution sets, and a finite pessimistic infimum, we derive mixed-integer linear optimization formulations that attain this infimum, even when the original problem has no optimal solution. This setting has applications such as pricing, security, and decision-focused … Read more
Interdiction for the direct current optimal power flow problem is commonly modeled in two stages, where an attacker disables components in the first stage and an operator makes remedial adjustments in the second stage. The resulting bilevel mathematical program is often solved via transformation into a single-level mixed-integer program using duality. A drawback of this … Read more
For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more
We consider an electricity supplier for a large commercial electric vehicle (EV) fleet. The supplier uses a dynamic pricing scheme for buying and selling energy from and to the fleet, enabling the supplier to trade any deviations from the agreed day-ahead (DA) position in the intraday auction (IDA) market, while taking into account the behavior … Read more
We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which … Read more