Tolerance analysis for 0–1 knapsack problems

David Pisinger and Alima Saidi

European Journal of Operational Research, 2017, vol. 258, issue 3, 866-876

Abstract: Post-optimal analysis is the task of understanding the behavior of the solution of a problem due to changes in the data. Frequently, post-optimal analysis is as important as obtaining the optimal solution itself. Post-optimal analysis for linear programming problems is well established and widely used. However, for integer programming problems the task is much more computationally demanding, and various approaches based on branch-and-bound or cutting planes have been presented. In the present paper, we study how much coefficients in the original problem can vary without changing the optimal solution vector, the so-called tolerance analysis. We show how to perform exact tolerance analysis for the 0–1 knapsack problem with integer coefficients in amortized time O(clog n) for each item, where n is the number of items, and c is the capacity of the knapsack. Amortized running times report the time used for each item, when calculating tolerance limits of all items. Exact tolerance limits are the widest possible intervals, while approximate tolerance limits may be suboptimal. We show how various upper bounds can be used to determine approximate tolerance limits in time O(log n) or O(1) per item using the Dantzig bound and Dembo–Hammer bound, respectively. The running times and quality of the tolerance limits of all exact and approximate algorithms are experimentally compared, showing that all tolerance limits can be found in less than a second. The approximate bounds are of good quality for large-sized instances, while it is worth using the exact approach for smaller instances.

Keywords: Robustness & sensitivity analysis; Knapsack problem; Post-optimal analysis; Dynamic programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716309043
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:3:p:866-876

DOI: 10.1016/j.ejor.2016.10.054

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().