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

Dynamic programming for the time-dependent traveling salesman problem with time windows

The recent growth of direct-to-consumer deliveries has stressed the importance of last-mile logistics, becoming one of the critical factors in city planning. One of the key factors lies in the last-mile deliveries, reaching in some cases nearly 50% of the overall parcel delivery cost. Different variants of the the well-known Traveling Salesman Problem (TSP) arise … Read more

Automatic generation of FPTASes for stochastic monotone dynamic programs made easier

In this paper we go one step further in the automatic generation of FPTASes for multi-stage stochastic dynamic programs with scalar state and action spaces, in where the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is … Read more

Stochastic Optimization Models of Insurance Mathematics

The paper overviews stochastic optimization models of insurance mathematics and methods for their solution from the point of view of stochastic programming and stochastic optimal control methodology, with vector optimality criteria. The evolution of an insurance company’s capital is considered in discrete time. The main random variables, which influence this evolution, are levels of payments, … Read more