Stage-wise hybrid nested Benders’ decomposition-stochastic dual dynamic programming for virtual power plants

Categories Dynamic Programming, Energy, Stochastic Programming Tags , , ,

Participants in energy markets make sequential decisions across multiple time horizons under uncertainty, leading to large-scale multistage stochastic optimization problems. Stochastic dual dynamic programming is widely used for its tractability, but its application to modern energy markets is challenged by nested dependencies induced by participation across multiple interrelated markets under increasing uncertainty from distributed energy … Read more

Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results

Categories 0-1 Programming, Combinatorial Optimization, Integer Programming Tags , , ,

This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic … Read more

On the existence of Lagrange multipliers in conic programming

Categories Constrained Nonlinear Optimization Tags ,

The existence of Lagrange multipliers at a solution of a nonlinear optimization problem constitutes one of the cornerstones of modern optimization theory, with many important consequences for guiding algorithmic procedures towards a solution, defining stopping criteria, performing stability analysis, and several other aspects. However, the proof of this result is often intricate, relying on non-trivial … Read more

Scalable Finite Adaptability via Polyhedral Partition and Learning

Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , ,

We study finite adaptability for decision-making under uncertainty, where a small set of candidate solutions is prepared in advance and the best response is selected after uncertainty is realized. While existing methods have made significant progress on exact formulations, scalability remains a persistent challenge due to (i) the combinatorial nature of assigning decisions to uncertainty … Read more

Exact Approaches for the Maximum Mortality Rate Clique Problem

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , ,

This paper develops exact solution methods for the maximum mortality rate clique problem, which aims to identify a cluster of diseases in a comorbidity graph associated with the highest mortality rate among patients whose healthcare encounters are recorded in electronic health records. We establish the NP-hardness of the problem and propose two mixed-integer linear programming … Read more

Inexactly Smooth Performance Estimation and New Optimized Gradient Methods

Categories Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

  We consider a general class of “inexactly smooth” convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and H\”older smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient … Read more

Relief-based Anesthesiologist Scheduling with Stochastic Surgery Durations

Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , ,

We present a two-stage stochastic programming model for scheduling anesthesiologists to operating rooms under uncertainty in surgery durations. The proposed model takes a relief order to balance anesthesiologists’ workload as input and captures the trade-offs between anesthesiologist relief times, handoffs and under-staffing. To address the computational challenges of solving the proposed model, we derive supervalid … Read more

Covering for Set-Valued Mappings in the Absence of Metric Regularity

Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

Covering properties build the foundation of stability and sensitivity analysis of solutions to a generalized equation and more specific optimization-related stationarity and equilibrium problems. It has been well-understood that metric regularity of the mapping defining the generalized equation is a key to furnish Lipschitzian stability of the solution of interest. With this work, we want … Read more

Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization

Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise … Read more