Tolerance analysis for 0-1 knapsack problems

DOI10.1016/J.EJOR.2016.10.054MaRDI QIDQ1751719zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David Pisinger, Alima Saidi

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) Combinatorial optimization (90C27) Dynamic programming (90C39) Sensitivity, stability, parametric optimization (90C31) Mixed integer programming (90C11) Boolean programming (90C09)

Recommendations

• Sensitivity analysis of a greedy heuristic for knapsack problems
• On the complexity of postoptimality analysis of 0/1 programs
• Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study
• Sensitivity analysis to perturbations of the weight of a subset of items: the single knapsack case study
• Sensitivity analysis of the Knapsack sharing problem: perturbation of the weight of an item

Cites work

• scientific article; zbMATH DE number 3687091 (Why is no real title available?)
• scientific article; zbMATH DE number 1114459 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A Minimal Algorithm for the 0-1 Knapsack Problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Core problems in knapsack algorithms
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Einige bemerkungen zur bestimmung you stabilitätsbereiehen in der rein ganzzahligen iinearen optimierang
• Exact solution of the robust knapsack problem
• Facets of the knapsack polytope
• Integer Programming Post-Optimal Analysis with Cutting Planes
• On the exact separation of mixed integer knapsack cuts
• On the robust knapsack problem
• 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 analysis to perturbations of the weight of a subset of items: the single knapsack case study
• Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem
• Stability, parametric, and postoptimality analysis of discrete optimization problems
• Testing integer knapsacks for feasibility
• The inverse-parametric knapsack problem

Cited in

(3)

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

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Tolerance analysis for 0-1 knapsack problems

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