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

DOI10.1007/S10479-009-0577-5zbMATH Open1194.90073OpenAlexW2058409291MaRDI QIDQ993710FDOQ993710

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Applications of second-order cone programming
• Stochastic on-line knapsack problems
• The sample average approximation method for stochastic discrete optimization
• A Knapsack Secretary Problem with Applications
• Stochastic Estimation of the Maximum of a Regression Function
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• A robust approach to the chance-constrained knapsack problem
• The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing
• 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
• A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem
• Title not available (Why is that?)
• Approximating the Value Functions of Stochastic Knapsack Problems: A Homogeneous Monge-Amp\'ere Equation and Its Stochastic Counterparts
• New method of stochastic approximation type
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• An exact algorithm for 0-1 polynomial Knapsack problems
• Title not available (Why is that?)

Cited In (26)

• The Risk-Averse Static Stochastic Knapsack Problem
• Stochastic quadratic knapsack with recourse
• Stochastic shortest path problem with delay excess penalty
• Robust optimization approach for a chance-constrained binary knapsack problem
• 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
• On a stochastic bilevel programming problem
• The static stochastic knapsack problem with normally distributed item sizes
• On two-stage stochastic knapsack problems
• 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
• Static stochastic Knapsack problems
• A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem
• 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
• A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints

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)