Chvatal (1980) has given a simple example of a knapsack problem for which a branch-and-bound algorithm using domination and linear relaxations to eliminate subproblems will use an exponential number of steps in the best case. In this short note it is shown that Chvatals result remains true when the LP relaxation is replaced with a semidefinite relaxation that is best possible in a certain sense.
Citation
Preprint, Mathematisches Institut, Heinrich-Heine-Universitaet Duesseldorf, July 2018,