On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems

A function is introduced that characterizes the complexity of postoptimality analysis of discrete optimization problems. For this function, the upper O(2^poly(n)) and lower \( \Omega \left( {\frac{{{2^n}}}{{\sqrt {{n + 1}} }}} \right) \) 2 bounds are obtained in the class of branch and bound methods for the knapsack problem. A class of set covering problems with a polynomial estimate of this function is observed