Robust optimization approach for a chance-constrained binary knapsack problem

DOI10.1007/s10107-015-0931-0zbMath1356.90096OpenAlexW1072890467MaRDI QIDQ291067

Sungsoo Park, Jinil Han, Chungmok Lee, Ki-Seok Choi, Kyungsik Lee

Publication date: 6 June 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-015-0931-0

zbMATH Keywords

combinatorial optimizationknapsack problemchance-constrained programmingrobust optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, Robust optimization for non-linear impact of data variation, A fully polynomial time approximation scheme for the probability maximizing shortest path problem, Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness, Comparative analysis of linear programming relaxations for the robust knapsack problem, Lifting of probabilistic cover inequalities, A robust optimization approach with probe-able uncertainty, Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact solution of the robust knapsack problem
• The static stochastic knapsack problem with normally distributed item sizes
• A robust approach to the chance-constrained knapsack problem
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
• A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem
• A note on the max-min 0-1 knapsack problem
• Robust solutions of uncertain linear programs
• Stochastic binary problems with simple penalties for capacity constraints violations
• Complexity results and exact algorithms for robust knapsack problems
• A note on upper bounds to the robust knapsack problem with discrete scenarios
• On distributionally robust chance-constrained linear programs
• Heuristic and exact algorithms for the max-min optimization of the multi-scenario knapsack problem
• The Dynamic and Stochastic Knapsack Problem
• Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem
• The Dynamic and Stochastic Knapsack Problem with Random Sized Items
• The Price of Robustness
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Allocating Bandwidth for Bursty Connections
• Technical Note—Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• On the Robust Knapsack Problem