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

DOI10.1007/S10479-009-0577-5MaRDI QIDQ993710zbMATH OpenOpenAlexFDO

Authors Stefanie Kosuch, Abdel Lisser

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

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

Mathematics Subject Classification ID

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

Recommendations

• On two-stage stochastic knapsack problems
• A stochastic linear knapsack problem
• Static stochastic Knapsack problems
• scientific article; zbMATH DE number 1114460
• The static stochastic knapsack problem with normally distributed item sizes

Cites work

• scientific article; zbMATH DE number 3700586 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 1559582 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A Knapsack Secretary Problem with Applications
• A Stochastic Approximation Method
• A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem
• A robust approach to the chance-constrained knapsack problem
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• An exact algorithm for 0-1 polynomial Knapsack problems
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Applications of second-order cone programming
• Approximating the Value Functions of Stochastic Knapsack Problems: A Homogeneous Monge-Amp\'ere Equation and Its Stochastic Counterparts
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Budget-Dependent Convergence Rate of Stochastic Approximation
• New method of stochastic approximation type
• Stochastic Estimation of the Maximum of a Regression Function
• Stochastic on-line knapsack problems
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The Minimization of Semicontinuous Functions: Mollifier Subgradients
• The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing
• The sample average approximation method for stochastic discrete optimization
• The stochastic knapsack problem

Cited in

(26)

• A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints
• The Risk-Averse Static Stochastic Knapsack Problem
• Stochastic quadratic knapsack with recourse
• Robust optimization approach for a chance-constrained binary knapsack problem
• Stochastic shortest path problem with delay excess penalty
• Stochastic set packing problem
• Stochastic nonlinear resource allocation problem
• An adaptive stochastic knapsack problem
• A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
• Dynamic job assignment: a column generation approach with an application to surgery allocation
• The static stochastic knapsack problem with normally distributed item sizes
• On two-stage stochastic knapsack problems
• On a stochastic bilevel programming problem
• Exact algorithms for the 0-1 time-bomb knapsack problem
• A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
• Rapid screening algorithms for stochastically constrained problems
• Convexity and solutions of stochastic multidimensional 0-1 knapsack problems with probabilistic constraints
• A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem
• Static stochastic Knapsack problems
• The applications of 0-1 knapsack problem in limit investment decision and its recovery from disruption
• Stochastic binary problems with simple penalties for capacity constraints violations
• Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem
• Binary knapsack problems with random budgets
• A second-order cone programming approach for linear programs with joint probabilistic constraints
• Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem
• Optimal allocation of stock levels and stochastic customer demands to a capacitated resource

Describes a project that uses

Uses Software

• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q993710)