From Optimization to Control: Quasi Policy Iteration

Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we make this analogy explicit across four problem classes with a unified solution characterization. This novel framework, in turn, allows for a systematic transformation of algorithms from one domain to the other. In … Read more

Neural Approximate Dynamic Programming for the Ultra-fast Order Dispatching Problem

Same-Day Delivery (SDD) services aim to maximize the fulfillment of online orders while minimizing delivery delays but are beset by operational uncertainties such as those in order volumes and courier planning. Our work aims to enhance the operational efficiency of SDD by focusing on the ultra-fast Order Dispatching Problem (ODP), which involves matching and dispatching … Read more

A Generic Hybrid Genetic Algorithm-based Framework for Solving Various Classes of Arc Routing Problems

Arc routing problems are combinatorial optimization problems that have many real-world applications, such as mail delivery, snow plowing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. Presented here is a generic algorithmic framework that can be applied to a variety of arc … Read more

Optimizing the Path Towards Plastic-Free Oceans

Increasing ocean plastic pollution is irreversibly harming ecosystems and human economic activities. We partner with a non-profit organization and use optimization to help them clean up oceans from plastic faster. Specifically, we optimize the route of their plastic collection system in the ocean to maximize the quantity of plastic collected over time. We formulate the … Read more

K-Shortest Simple Paths Using Biobjective Path Search

In this paper we introduce a new algorithm for the k-Shortest Simple Paths (k-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roddity and Zwick that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem … Read more

Solution Path of Time-varying Markov Random Fields with Discrete Regularization

\(\) We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to … Read more

A Multicut Approach to Compute Upper Bounds for Risk-Averse SDDP

Stochastic Dual Dynamic Programming (SDDP) is a widely used and fundamental algorithm for solving multistage stochastic optimization problems. Although SDDP has been frequently applied to solve risk-averse models with the Conditional Value-at-Risk (CVaR), it is known that the estimation of upper bounds is a methodological challenge, and many methods are computationally intensive. In practice, this … Read more

Duality of upper bounds in stochastic dynamic programming

For multistage stochastic programming problems with stagewise independent uncertainty, dynamic programming algorithms calculate polyhedral approximations for the value functions at each stage.  The SDDP algorithm provides piecewise linear lower bounds, in the spirit of the L-shaped algorithm, and corresponding upper bounds took a longer time to appear.  One strategy uses the primal dynamic programming recursion … Read more

Analysis of Monotone Policy Iteration for Interpretable Policies in Markov Decision Processes: Impact of State Ordering Rules

Optimizing interpretable policies for Markov Decision Processes (MDPs) can be computationally intractable for large-scale MDPs, e.g., for monotone policies, the optimal interpretable policy depends on the initial state distribution, precluding standard dynamic programming techniques. Previous work has proposed Monotone Policy Iteration (MPI) to produce a feasible solution for warm starting a Mixed Integer Linear Program … Read more

Distributionally Robust Linear Quadratic Control

Linear-Quadratic-Gaussian (LQG) control is a fundamental control paradigm that is studied in various fields such as engineering, computer science, economics, and neuroscience. It involves controlling a system with linear dynamics and imperfect observations, subject to additive noise, with the goal of minimizing a quadratic cost function for the state and control variables. In this work, … Read more