It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it … Read more
In this paper we discuss time consistency of risk averse multistage stochastic programming problems. We show, in a framework of finite scenario trees, that composition of law invariant coherent risk measures can be law invariant only for the expectation or max-risk measures. Citation Preprint Article Download View Time consistency of dynamic risk measures
Abstract. It is well known that multistage programs, which maximize expectation or expected utility, allow a dynamic programming formulation, and that other objectives destroy the dynamic programming character of the problem. This paper considers a risk measure at the final stage of a multistage stochastic program. Although these problems are not time consistent, it is … Read more
We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with diff erent basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between … Read more
We study dynamic operational decision problems where risky cash flows are being resolved over a finite planning horizon. Financing decisions via lending and borrowing are available to smooth out consumptions over time with the goal of achieving some prescribed consumption targets. Our target-oriented decision criterion is based on the aggregation of Aumann and Serrano (2008) … Read more
We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more
This paper studies dynamic stochastic optimization problems parametrized by a random variable. Such problems arise in many applications in operations research and mathematical finance. We give sufficient conditions for the existence of solutions and the absence of a duality gap. Our proof uses extended dynamic programming equations, whose validity is established under new relaxed conditions … Read more
We consider the problem of dynamic portfolio optimization in a discrete-time, finite-horizon setting. Our general model considers risk aversion, portfolio constraints (e.g., no short positions), return predictability, and transaction costs. This problem is naturally formulated as a stochastic dynamic program. Unfortunately, with non-zero transaction costs, the dimension of the state space is at least as … Read more
In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more
This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more