Dual SDDP for risk-averse multistage stochastic programs

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 … Read more

Central Limit Theorem and Sample Complexity of Stationary Stochastic Programs

In this paper we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem type asymptotics for the optimal values of the SAA problems. The main conclusion is that … Read more

Batch Learning in Stochastic Dual Dynamic Programming

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

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

Distributionally Robust Optimal Control and MDP Modeling

In this paper, we discuss Optimal Control and Markov Decision Process (MDP) formulations of multistage optimization problems when the involved probability distributions are not known exactly, but rather are assumed to belong to specified ambiguity families. The aim of this paper is to clarify a connection between such distributionally robust approaches to multistage stochastic optimization. … Read more

Discrete Multi-Module Capacitated Lot-Sizing Problems with Multiple Items

We study single-item discrete multi-module capacitated lot-sizing problems where the amount produced in each time period is equal to the summation of binary multiples of the capacities of n available different modules (or machines). For fixed n≥2, we develop fixed-parameter tractable (polynomial) exact algorithms that generalize the algorithms of van Vyve (2007) for n=1. We … Read more

Dual bounds for periodical stochastic programs

In this paper we discuss construction of the dual of a periodical formulation of infinite horizon linear stochastic programs with a discount factor. The dual problem is used for computing a deterministic upper bound for the optimal value of the considered multistage stochastic program. Numerical experiments demonstrate behavior of that upper bound especially when the … Read more

Dynamic Node Packing

We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable … Read more

A Simulated Annealing Algorithm for the Directed Steiner Tree Problem

In \cite{siebert2019linear} the authors present a set of integer programs (IPs) for the Steiner tree problem, which can be used for both, the directed and the undirected setting of the problem. Each IP finds an optimal Steiner tree with a specific structure. A solution with the lowest cost, corresponds to an optimal solution to the … Read more

Equal Risk Pricing and Hedging of Financial Derivatives with Convex Risk Measures

In this paper, we consider the problem of equal risk pricing and hedging in which the fair price of an option is the price that exposes both sides of the contract to the same level of risk. Focusing for the first time on the context where risk is measured according to convex risk measures, we … Read more