Tolerance analysis for 0-1 knapsack problems

DOI10.1016/j.ejor.2016.10.054zbMath1394.90493OpenAlexW2547672618WikidataQ58826312 ScholiaQ58826312MaRDI QIDQ1751719

Alima Saidi, David Pisinger

Publication date: 25 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.10.054

zbMATH Keywords

dynamic programmingknapsack problempost-optimal analysisrobustness \& sensitivity analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27) Dynamic programming (90C39) Boolean programming (90C09)

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis ⋮ Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems

Uses Software

• Knapsack

Cites Work

• Exact solution of the robust knapsack problem
• On the exact separation of mixed integer knapsack cuts
• Reoptimizing the 0-1 knapsack problem
• Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem
• Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Testing integer knapsacks for feasibility
• The inverse-parametric knapsack problem
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Core Problems in Knapsack Algorithms
• Sensitivity Analysis to Perturbations of the Weight of a Subset of Items: The Single Knapsack Case Study
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Stability, parametric, and postoptimality analysis of discrete optimization problems
• Integer Programming Post-Optimal Analysis with Cutting Planes
• Einige bemerkungen zur bestimmung you stabilitätsbereiehen in der rein ganzzahligen iinearen optimierang
• Facets of the knapsack polytope
• A Minimal Algorithm for the 0-1 Knapsack Problem
• On the Robust Knapsack Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item