Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

DOI10.1137/15M1036233zbMath1346.90606OpenAlexW2508968471MaRDI QIDQ2817835

Weihong Hu, Daniel Blado, Alejandro Toriello

Publication date: 2 September 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1036233

zbMATH Keywords

relaxationstochastic knapsackdynamic program

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Dynamic programming (90C39) Semi-infinite programming (90C34)

Related Items (11)

Stochastic Knapsack Revisited: The Service Level Perspective ⋮ Recent contributions to linear semi-infinite optimization ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ Approximations to Stochastic Dynamic Programs via Information Relaxation Duality ⋮ Recent contributions to linear semi-infinite optimization: an update ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ Unnamed Item ⋮ Dynamic node packing ⋮ Adaptive Bin Packing with Overflow

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The static stochastic knapsack problem with normally distributed item sizes
• Approximate formulations for 0-1 knapsack sets
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Generalized polynomial approximations in Markovian decision processes
• Stochastic linear knapsack programming problem and its application to a portfolio selection problem
• A note on the extension complexity of the knapsack polytope
• The Dynamic and Stochastic Knapsack Problem
• A Dynamic Traveling Salesman Problem with Stochastic Arc Costs
• TECHNICAL NOTE—The Adaptive Knapsack Problem with Stochastic Rewards
• A Preference Order Dynamic Program for a Knapsack Problem with Stochastic Rewards
• Information Relaxations and Duality in Stochastic Dynamic Programs
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The Linear Programming Approach to Approximate Dynamic Programming
• Preference Order Stochastic Knapsack Problems: Methodological Issues
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• A Renewal Decision Problem
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• The Dynamic and Stochastic Knapsack Problem with Deadlines
• Allocating Bandwidth for Bursty Connections
• A Price-Directed Approach to Stochastic Inventory/Routing
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• The Theory and Computation of Knapsack Functions

This page was built for publication: Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes