Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity

DOI10.1007/s11590-019-01445-6zbMath1433.90137arXiv1811.01569OpenAlexW2963432189MaRDI QIDQ2300641

Seulgi Joung, Kyungsik Lee

Publication date: 27 February 2020

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.01569

zbMATH Keywords

submodularityheuristicrobust optimizationchance-constrained knapsack problem

Mathematics Subject Classification ID

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

Related Items (4)

Using submodularity in solving the robust bandwidth packing problem with queuing delay guarantees ⋮ Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness ⋮ Streaming submodular maximization with the chance constraint ⋮ Comparative analysis of linear programming relaxations for the robust knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust optimization approach for a chance-constrained binary knapsack problem
• Exact solution of the robust knapsack problem
• Polymatroids and mean-risk minimization in discrete optimization
• A robust approach to the chance-constrained knapsack problem
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Submodular function minimization
• The submodular knapsack polytope
• Robust solutions of uncertain linear programs
• Robust discrete optimization and network flows
• Lifting of probabilistic cover inequalities
• The Price of Robustness
• A Minimal Algorithm for the Bounded Knapsack Problem
• Allocating Bandwidth for Bursty Connections
• Lifting and separation of robust cover inequalities
• Network design with probabilistic capacities
• Convex Approximations of Chance Constrained Programs

This page was built for publication: Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity