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

DOI10.1007/S11590-019-01445-6zbMATH Open1433.90137arXiv1811.01569OpenAlexW2963432189MaRDI QIDQ2300641FDOQ2300641

Authors: Seulgi Joung, Kyungsik Lee 

Publication date: 27 February 2020

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

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.

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

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

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)

Cites Work

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

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
• Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives
• A robust approach to the chance-constrained knapsack problem
• 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

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)