The inverse-parametric knapsack problem

This paper deals with parametric knapsack problems where the costs or weights are replaced by linear functions depending on a parameter t. The aim is to find the smallest parameter t* such that the optimal solution value of the knapsack problem is equal to a prespecified solution value. For this inverse-parametric problem pseudopolynomial algorithms are developed and search methods making use of the special properties of the parametric value function are constructed. Using computational experiments the behaviour of these algorithms is investigated and the favourable practical performance of different search methods is exhibited.