Dynamic Programming

Fully Polynomial Time (Sigma,Pi)-Approximation Schemes for Continuous Nonlinear Newsvendor and Continuous Stochastic Dynamic Programs

Categories Approximation Algorithms, Dynamic Programming Tags , , , , ,

We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, … Read more

Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

Categories Combinatorial Optimization, Dynamic Programming Tags ,

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 dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

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

We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which … Read more

An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more

Stochastic Dual Dynamic Integer Programming

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

Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and … Read more

MIDAS: A Mixed Integer Dynamic Approximation Scheme

Categories Dynamic Programming, Stochastic Programming Tags ,

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

A Polyhedral Approach to Online Bipartite Matching

Categories Dynamic Programming, Polyhedra Tags , ,

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

A joint routing and speed optimization problem

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Transportation

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

A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

Categories Approximation Algorithms, Dynamic Programming Tags , ,

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 with Unit Upgrading Cost

Categories Combinatorial Optimization, Dynamic Programming, Network Optimization Tags , , ,

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