Approximate solution of infinite-horizon risk-sensitive Markov decision processes

Categories Dynamic Programming, Other Topics Tags , ,

Infinite-horizon risk-sensitive Markov decision processes (MDPs) under the discounted cost criterion are challenging to solve because the optimal policy may be non- stationary. Existing solution methods reformulate the problem as a continuous-state (risk-neutral) MDP and solve it using state-discretization or value function approximation. Such approaches typically lack explicit stopping conditions or error bounds. In this … Read more

Exploring polynomial models in the Search Step of Direct Multisearch

Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

Direct Multisearch (DMS) is a class of direct-search algorithms designed for multiobjective derivative-free optimization. Its framework consists of an optional search step and a poll step, the latter ensuring the corresponding theoretical convergence properties. Recently, a search strategy based on the minimization of quadratic polynomial models, constructed from previously evaluated points, was proposed to improve … Read more

Model-Uncertainty-Aware Residuals-Based Sample Average Approximation

Categories Robust Optimization, Stochastic Programming Tags , , ,

We consider a contextual stochastic optimization (CSO) problem, where one has observations of the uncertain parameters together with concurrent observations of covariates, and the goal is to choose decisions that minimize expected cost conditioned on new covariate observations. The empirical residuals-based sample average approximation (ER-SAA) of the CSO problem constructs scenarios of uncertainty by combining … Read more

Accelerated Kernel Stein Discrepancy with Rényi Landmark Selection for GAN Training

Categories Data Science Algorithms

Our project investigates replacing the classical adversarial discriminator in GAN training with a kernel-based distance metric, namely Kernel Stein Discrepancy (KSD). We assess whether a kernelized objective can improve training stability and efficiency without compromising sample quality, and we evaluate accelerated Nystrom approximations with Renyi landmark selection on CIFAR-10. ArticleDownload View PDF

PaNGEA: Parallel Node Generation and Exploration Algorithm

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

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining … Read more

A Dynamic-Programming Labeling Approach to Hydrogen-Powered Route Selection in Aviation Networks

Categories Airline Optimization, Applications - OR and Management Sciences Tags , ,

We study passenger routing in an aviation network that blends hydrogen‐ and kerosene‐powered aircraft. Under our assumptions, hydrogen enables carbon‐free short‐ and medium‐haul flights but requires capital‐intensive supply facilities, which lead to varying prices and availabilities of hydrogen at specific airports, creating strong interdependencies between routing, technology choice, and infrastructure availability. To capture these trade‐offs, … Read more

A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting

Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according … Read more

Route `Em and Count `Em: A Two-Stage Stochastic Programming Model for Anti-Submarine Operations

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

Tracking targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets in the search region over the planning horizon. We develop a two-stage stochastic integer programming model that maximizes the expected total reward for target detections under uncertainty in target motion … Read more

Stochastic Queens Elimination

Categories (Mixed) Integer Linear Programming, Dynamic Programming Tags , , , ,

This research introduces the Stochastic Sequential Queens Elimination Problem, where on the \(n\)-queens board, each activated queen simultaneously attempts to eliminate all queens in her unblocked neighborhood, each independently succeeding with probability \(p\). The objective is to minimize the expected cumulative conflict count over the trajectory. This research proposes a Markov decision process for this … Read more

Adaptive Scenario Partitioning for Stochastic Bilevel Linear Programs

Categories Bilevel Optimization, Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

This paper develops an adaptive scenario partitioning approach for stochastic bilevel linear programs. The method extends the Adaptive Partitioning Method, originally designed for two-stage stochastic programs, to settings in which a leader makes a first-stage decision while anticipating scenario dependent optimal responses from a follower. The proposed approach solves a sequence of aggregated master problems … Read more