Formulations and algorithms for the recoverable -robust knapsack problem

DOI10.1007/S13675-018-0107-9MaRDI QIDQ2329707zbMATH OpenOpenAlexFDO

Authors Christina Büsing, Sebastian Goderbauer, Arie M. C. A. Koster, Manuel Kutschka

Publication date 18 October 2019

Published in EURO Journal on Computational Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1007/s13675-018-0107-9

zbMATH Keywords

\({\varGamma}\)-robustnessbudget uncertaintyinteger programming under uncertaintyknapsackrecoverable robustness

Mathematics Subject Classification ID

Integer programming (90C10) Minimax problems in mathematical programming (90C47) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Recoverable robust knapsacks: -scenarios
• Recoverable robust knapsacks: the discrete scenario case
• Cover inequalities for robust knapsack sets -- application to the robust bandwidth packing problem
• Complexity results and exact algorithms for robust knapsack problems
• The multi-band robust knapsack problem -- a dynamic programming approach

Cites work

• Canonical Cuts on the Unit Hypercube
• Cover inequalities for robust knapsack sets -- application to the robust bandwidth packing problem
• Cutting plane versus compact formulations for uncertain (integer) linear programs
• Cutting-set methods for robust convex optimization with pessimizing oracles
• Exact solution of the robust knapsack problem
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• On the robust knapsack problem
• Recoverable robust knapsacks: -scenarios
• Recoverable robust knapsacks: the discrete scenario case
• Recoverable Robustness in Shunting and Timetabling
• Reducibility among combinatorial problems
• Robust discrete optimization and network flows
• Robustness concepts for knapsack and network design problems under data uncertainty. Gamma-, multi-band, submodular, and recoverable robustness
• Separation algorithms for 0-1 knapsack polytopes
• The concept of recoverable robustness, linear programming recovery, and railway applications
• The Price of Robustness
• The recoverable robust two-level network design problem
• Where are the hard knapsack problems?

Cited in

(11)

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Cover inequalities for robust knapsack sets -- application to the robust bandwidth packing problem
• Recoverable robust knapsacks: -scenarios
• Recoverable Robust Combinatorial Optimization Problems
• Comparative analysis of linear programming relaxations for the robust knapsack problem
• Benchmarking problems for robust discrete optimization
• Recoverable robust shortest path problem under interval budgeted uncertainty representations
• Recoverable robust cardinality constrained maximization with commitment of a submodular function
• Recoverable robust knapsacks: the discrete scenario case
• Recoverable robust cardinality constrained maximization with commitment of a submodular function
• On the complexity of recoverable robust optimization in the polynomial hierarchy

This page was built for publication: Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem

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