A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs

DOI10.1016/j.cor.2018.04.013zbMath1391.90448OpenAlexW2740742622MaRDI QIDQ1652714

Dawid Kozlowski, Troels Martin Range, Niels Christian Petersen

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://findresearcher.sdu.dk:8443/ws/files/142981090/A_shortest_path_based_approach_for_the_stochastic_knapsack_problem_with_non_decreasing_expected_overfilling_costs.pdf

zbMATH Keywords

dynamic programmingshortest path problem with resource constraintsstochastic knapsack problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Stochastic programming (90C15) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

Exact algorithms for the 0-1 time-bomb knapsack problem, Dynamic job assignment: a column generation approach with an application to surgery allocation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands
• On an exact method for the constrained shortest path problem
• Heuristic decomposition approaches for an integrated task scheduling and personnel rostering problem
• Scheduler -- a system for staff planning
• The static stochastic knapsack problem with normally distributed item sizes
• A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems
• A robust approach to the chance-constrained knapsack problem
• The bilevel knapsack problem with stochastic right-hand sides
• Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
• Labeling algorithms for multiple objective integer knapsack problems
• Dynamic programming algorithms for the zero-one knapsack problem
• Robust surgery loading
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Resource extension functions: properties, inversion, and generalization to segments
• Vehicle routing problem with elementary shortest path based column generation
• New approaches to nurse rostering benchmark instances
• Chance-Constrained Programming
• The Dynamic and Stochastic Knapsack Problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• The Sample Average Approximation Method for Stochastic Discrete Optimization
• TECHNICAL NOTE—The Adaptive Knapsack Problem with Stochastic Rewards
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• Shortest path algorithms for knapsack type problems
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Packing a Knapsack of Unknown Capacity
• STATIC STOCHASTIC KNAPSACK PROBLEMS
• Shortest Path Problems with Resource Constraints
• The Theory and Computation of Knapsack Functions