Minimal Equivalent Binary Knapsack Inequalities

It is known that a knapsack inequality can be reduced to one having the same solutions but with ‘minimal’ integer coefficients. Although this procedure is not practical because an exponential amount of work may be required to find such minimal equivalent knapsacks, knowledge of minimal equivalent knapsacks can reduce hard knapsacks to trivial ones, as we show for both Todd and Avis knapsacks. In this paper, we show that even with an oracle able to supply minimal equivalent knapsacks at no computational cost, their practical value may not materialize because there are minimal knapsack inequalities with exponential values.