Mixed Integer Dynamic Approximation Scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description of MIDAS, and prove its almost-sure convergence to an epsilon-optimal policy when … Read more
We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various … Read more
Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and … Read more
Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,u_n)$, we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most $C$. We give a deterministic algorithm that estimates the number of solutions to within … Read more
The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we … Read more
The choice of a risk measure reflects a subjective preference of the decision maker in many managerial, or real world economic problem formulations. To evaluate the impact of personal preferences it is thus of interest to have comparisons with other risk measures at hand. This paper develops a framework for comparing different risk measures. We … Read more
This paper presents an approach to non-stationary policy search for finite-horizon, discrete-time Markovian decision problems with large state spaces, constrained action sets, and a risk-sensitive optimality criterion. The methodology relies on modeling time variant policy parameters by a non-parametric response surface model for an indirect parametrized policy motivated by the Bellman equation. Through the interpolating … Read more
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more
We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more
In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are … Read more