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

DOI10.1007/S11590-019-01445-6MaRDI QIDQ2300641zbMATH OpenOpenAlexFDO

Authors 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

heuristicrobust optimizationsubmodularitychance-constrained knapsack problem

Mathematics Subject Classification ID

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

Abstract: In this paper, we propose a robust optimization-based heuristic algorithm for the chance-constrained binary knapsack problem (CKP). We assume that the weights of items are independent normally distributed. By utilizing the properties of the submodular function, the proposed method approximates the CKP to the robust knapsack problem with a cardinality constrained uncertainty set parameterized by a uncertainty budget parameter. The proposed approach obtains a heuristic solution by solving the approximated robust knapsack problem whose optimal solution can be obtained by solving the ordinary binary knapsack problem iteratively. The computational results show the effectiveness and efficiency of the proposed approach.

Recommendations

• A robust approach to the chance-constrained knapsack problem
• Robust optimization approach for a chance-constrained binary knapsack problem
• Complexity results and exact algorithms for robust knapsack problems
• Distributionally robust stochastic knapsack problem
• Exact solution of the robust knapsack problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7561426 (Why is no real title available?)
• A Minimal Algorithm for the Bounded Knapsack Problem
• A PTAS for the chance-constrained knapsack problem with random item sizes
• A robust approach to the chance-constrained knapsack problem
• Allocating Bandwidth for Bursty Connections
• Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack
• Convex Approximations of Chance Constrained Programs
• Exact solution of the robust knapsack problem
• Improved approximation results for stochastic knapsack problems
• Lifting and separation of robust cover inequalities
• Lifting of probabilistic cover inequalities
• Network design with probabilistic capacities
• Polymatroids and mean-risk minimization in discrete optimization
• Robust discrete optimization and network flows
• Robust optimization approach for a chance-constrained binary knapsack problem
• Robust solutions of uncertain linear programs
• Submodular function minimization
• The Price of Robustness
• The submodular knapsack polytope

Cited in

(8)

• Streaming submodular maximization with the chance constraint
• Robust optimization approach for a chance-constrained binary knapsack problem
• Comparative analysis of linear programming relaxations for the robust knapsack problem
• A robust approach to the chance-constrained knapsack problem
• Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives
• Using submodularity in solving the robust bandwidth packing problem with queuing delay guarantees
• Tractable algorithms for chance-constrained combinatorial problems
• Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness

Describes a project that uses

Uses Software

• Knapsack

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

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