Best case exponential running time of a branch-and-bound algorithm using an optimal semidefinite relaxation

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,

Article

Download

View Best case exponential running time of a branch-and-bound algorithm using an optimal semidefinite relaxation