Dynamic Programming

Interpretable Policies and the Price of Interpretability in Hypertension Treatment Planning

Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Dynamic Programming Tags , , , , ,

Problem definition: Effective hypertension management is critical to reducing consequences of atherosclerotic cardiovascular disease, a leading cause of death in the United States. Clinical guidelines for hypertension can be enhanced using decision-analytic approaches, capable of capturing many complexities in treatment planning. However, model-generated recommendations may be uninterpretable/unintuitive, limiting their acceptability in practice. We address this … Read more

Dual SDDP for risk-averse multistage stochastic programs

Categories Dynamic Programming, Stochastic Programming Tags , , , ,

Risk-averse multistage stochastic programs appear in multiple areas and are challenging to solve. Stochastic Dual Dynamic Programming (SDDP) is a well-known tool to address such problems under time-independence assumptions. We show how to derive a dual formulation for these problems and apply an SDDP algorithm, leading to converging and deterministic upper bounds for risk-averse problems. … Read more

What is the optimal cutoff surface for ore bodies with more than one mineral?

Categories Applications - OR and Management Sciences, Control Applications, Dynamic Programming

In mine planning problems, cutoff grade optimization defines a threshold at every time period such that material above this value is processed, and the rest is considered waste. In orebodies with multiple minerals, which occur in practice, the natural extension is to consider a cutoff surface. We show that in two dimensions the optimal solution … Read more

Batch Learning in Stochastic Dual Dynamic Programming

Categories Dynamic Programming, Stochastic Programming Tags , , , ,

We consider the stochastic dual dynamic programming (SDDP) algorithm, which is a widely employed algorithm applied to multistage stochastic programming, and propose a variant using batch learning, a technique used with success in the reinforcement learning framework. We cast SDDP as a type of Q-learning algorithm and describe its application in both risk neutral and … Read more

Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

Categories Dynamic Programming, Graphs and Matroids, Polyhedra Tags , , , ,

The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more

Exact algorithms for the 0-1 Time-bomb Knapsack Problem

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Stochastic Programming Tags , ,

We consider a stochastic version of the 0–1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The objective is to maximize the expected profit of the selected items. The resulting problem, denoted as 0–1 Time-Bomb Knapsack … Read more

Optimal Hospital Care Scheduling During the SARS-CoV-2 Pandemic

Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags , , ,

The COVID-19 pandemic has seen dramatic demand surges for hospital care that have placed a severe strain on health systems worldwide. As a result, policy makers are faced with the challenge of managing scarce hospital capacity so as to reduce the backlog of non-COVID patients whilst maintaining the ability to respond to any potential future … Read more

Optimizing Active Surveillance for Prostate Cancer Using Partially Observable Markov Decision Processes

Categories Applications - OR and Management Sciences, Biomedical Applications, Dynamic Programming Tags , , , ,

We describe a finite-horizon partially observable Markov decision process (POMDP) approach to optimize decisions about whether and when to perform biopsies for patients on active surveillance for prostate cancer. The objective is to minimize a weighted combination of two criteria, the number of biopsies to conduct over a patient’s lifetime and the delay in detecting … Read more

A Framework for Multi-stage Bonus Allocation in Meal-Delivery Platform

Categories Applications - OR and Management Sciences, Dynamic Programming Tags , , , ,

Online meal delivery is undergoing explosive growth, as this service is becoming increasingly fashionable. A meal delivery platform aims to provide efficient services for customers and restaurants. However, in reality, several hundred thousand orders are canceled per day in the Meituan meal delivery platform since they are not accepted by the crowdsoucing drivers, which is … Read more

A dynamic programming approach to segmented isotonic regression

Categories Data-Mining, Dynamic Programming, Energy Tags , , , , ,

This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on … Read more