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
Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more
Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable … Read more
Distributionally robust optimization hedges a decision against an ambiguity set of candidate distributions. In a cold-start setting the target distribution is unobserved and no sample from it is available, so only related source distributions provide evidence for constructing that set. We propose an inclusive-exclusive Wasserstein ball model that jointly learns a center and radius from … Read more
We formulate offline tuning of Model Predictive Path Integral (MPPI) controllers as a chance-constrained black-box optimization problem and develop an update-aware framework based on Matrix Adaptation Evolution Strategy (MA-ES). We use statistical information from noisy controller evaluations to determine when the evolutionary update is sufficiently reliable. When the recombination direction is certified, a derivative-free nonmonotone … Read more
Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more
Large language models improve test-time accuracy by generating multiple rollouts and aggregating these answers. As generating additional rollouts consumes more tokens, test-time compute faces a fundamental cost accuracy trade-off, naturally raising the question: given a fixed token budget, how to allocate the budget to maximize accuracy? Existing approaches typically adapt the number of rollouts for … Read more
Stochastic dual dynamic programming (SDDP) and its variants are run in practice with forward passes that sample the noise at random. Recent iteration-complexity results favour another choice: when the trial points are selected deterministically, for instance along the scenario with the largest gap, the number of iterations is polynomial in the horizon $T$, whereas every … Read more
Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP ∩ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open … Read more