Numerical Methods for Convex Multistage Stochastic Optimization

\(\) Optimization problems involving sequential decisions in  a  stochastic environment    were studied  in  Stochastic Programming (SP), Stochastic Optimal Control  (SOC) and Markov Decision Processes (MDP). In this paper we mainly concentrate on SP and  SOC modelling   approaches. In these frameworks there are natural situations  when the considered problems are  convex. Classical approach to sequential … Read more

The min-Knapsack Problem with Compactness Constraints and Applications in Statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper we introduce an extension of the min-Knapsack problem with additional … Read more

Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

Truck-and-drone routing problems have become an important topic of research in the last decade due to their applications for last-mile deliveries. Despite the large number of publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact is true even for … Read more

A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

\(\) We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of … Read more

Multi-Echelon Inventory Management for a Non-Stationary Capacitated Distribution Network

We present an inventory management solution for a non-stationary capacitated multi-echelon distribution network involving thousands of products. Assuming backlogged sales, we revisit and leverage the seminal multi-echelon inventory management results in the literature to establish the structural properties of the problem, and derive an efficient and practical solution method. In particular, we describe how the … Read more

Convergence of Trajectory Following Dynamic Programming algorithms for multistage stochastic problems without finite support assumptions

We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximation of cost-to-go functions of multistage stochastic problems with independent random variables. This framework encompasses most variants of the Stochastic Dual Dynamic Programming algorithm. Leveraging a Lipschitz assumption on the expected cost-to-go functions, we provide a new convergence and … Read more

A Route-Based Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers with given demands. An upper limit is imposed on the duration of the routes. Vehicles have limited autonomy: they may need to stop en-route at recharge stations. Recharges can be … Read more

Dynamic programming in convex stochastic optimization

This paper studies the dynamic programming principle for general convex stochastic optimization problems introduced by Rockafellar and Wets in the 1970s. We extend the applicability of the theory by relaxing compactness and boundedness assumptions. In the context of financial mathematics, the relaxed assumptions are satisfied under the well-known no-arbitrage condition and the reasonable asymptotic elasticity … Read more

Targeted Multiobjective Dijkstra Algorithm

In this paper, we introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. The T-MDA is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. The resulting speedup is comparable to the speedup that the original A* algorithm achieves … Read more

Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound

In this paper, we discuss an application of the SDDP type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of … Read more