Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm

DOI10.1007/s10479-009-0577-5zbMath1194.90073OpenAlexW2058409291MaRDI QIDQ993710

Abdel Lisser, Stefanie Kosuch

Publication date: 20 September 2010

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-009-0577-5

zbMATH Keywords

stochastic gradient algorithmSOCPsimple recoursearrow-hurwiczchance constrainedexpectation constrainedstatic stochastic Knapsack problems with random weights

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Related Items (19)

Stochastic Shortest Path Problem with Delay Excess Penalty ⋮ On a stochastic bilevel programming problem ⋮ Robust optimization approach for a chance-constrained binary knapsack problem ⋮ An adaptive stochastic knapsack problem ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ Stochastic nonlinear resource allocation problem ⋮ Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Optimal allocation of stock levels and stochastic customer demands to a capacitated resource ⋮ Rapid screening algorithms for stochastically constrained problems ⋮ The Risk-Averse Static Stochastic Knapsack Problem ⋮ Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem ⋮ STATIC STOCHASTIC KNAPSACK PROBLEMS ⋮ Stochastic binary problems with simple penalties for capacity constraints violations ⋮ On two-stage stochastic knapsack problems ⋮ A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints ⋮ Dynamic job assignment: a column generation approach with an application to surgery allocation ⋮ A second-order cone programming approach for linear programs with joint probabilistic constraints ⋮ The static stochastic knapsack problem with normally distributed item sizes

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A robust approach to the chance-constrained knapsack problem
• A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem
• Applications of second-order cone programming
• New method of stochastic approximation type
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Stochastic on-line knapsack problems
• An exact algorithm for 0-1 polynomial Knapsack problems
• The Sample Average Approximation Method for Stochastic Discrete Optimization
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing
• A Knapsack Secretary Problem with Applications
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The stochastic knapsack problem
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• Budget-Dependent Convergence Rate of Stochastic Approximation
• The Minimization of Semicontinuous Functions: Mollifier Subgradients
• Approximating the Value Functions of Stochastic Knapsack Problems: A Homogeneous Monge-Amp\'ere Equation and Its Stochastic Counterparts
• Stochastic Estimation of the Maximum of a Regression Function
• A Stochastic Approximation Method

This page was built for publication: Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm