Dynamic Programming

Risk averse stochastic programming: time consistency and optimal stopping

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

Bellman formulated a vague principle for optimization over time, which characterizes optimal policies by stating that a decision maker should not regret previous decisions retrospectively. This paper addresses time consistency in stochastic optimization. The problem is stated in generality first. The paper discusses time consistent decision-making by addressing risk measures which are recursive, nested, dynamically … Read more

Improved Decision Rule Approximations for Multi-Stage Robust Optimization via Copositive Programming

Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization

We study decision rule approximations for generic multi-stage robust linear optimization problems. We consider linear decision rules for the case when the objective coefficients, the recourse matrices, and the right-hand sides are uncertain, and consider quadratic decision rules for the case when only the right-hand sides are uncertain. The resulting optimization problems are NP-hard but … Read more

Coordination of a two-level supply chain with contracts

Categories Dynamic Programming, Production and Logistics, Supply Chain Management Tags , , , ,

We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer, by using contracts. We assume that the retailer has the market power: he can impose his optimal replenishment plan to the supplier. Our aim is to minimize the supplier’s cost without increasing the … Read more

Optimal switching sequence for switched linear systems

Categories Combinatorial Optimization, Control Applications, Dynamic Programming Tags , , , , ,

We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of n-by-n matrices and an n-dimensional vector, find a sequence of K matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the K matrices and the … Read more

Monitoring With Limited Information

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

We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which he must choose, in conjunction with a suitable stopping policy, to maximize his reward. Dealing … Read more

Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality

Categories Dynamic Programming, Stochastic Programming

The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse … Read more

An algorithm for solving infinite horizon Markov dynamic programmes

Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

We consider a general class of infinite horizon dynamic programmes where state and control sets are convex and compact subsets of Euclidean spaces and (convex) costs are discounted geometrically. The aim of this work is to provide a convergence result for these problems under as few restrictions as possible. Under certain assumptions on the cost … Read more

Outer Approximation for Integer Nonlinear Programs via Decision Diagrams

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Dynamic Programming Tags , , , ,

As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more

Network Models for Multiobjective Discrete Optimization

Categories 0-1 Programming, Dynamic Programming, Multi-Criteria Optimization

This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework formulates these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest path problem in an auxiliary network. We design tools and techniques for exploiting the network model in … Read more

A deterministic algorithm for solving stochastic minimax dynamic programmes

Categories Dynamic Programming, Robust Optimization, Stochastic Programming Tags , , , , , , , , ,

In this paper, we present an algorithm for solving stochastic minimax dynamic programmes where state and action sets are convex and compact. A feature of the formulations studied is the simultaneous non-rectangularity of both `min’ and `max’ feasibility sets. We begin by presenting convex programming upper and lower bound representations of saddle functions — extending … Read more