Optimization Online


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

Florian Jarre (jarre***at***hhu.de)

Abstract: 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.

Keywords: Semidefinite relaxation, branch-and-bound algorithm, exponential running time

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Preprint, Mathematisches Institut, Heinrich-Heine-Universitaet Duesseldorf, July 2018,

Download: [PDF]

Entry Submitted: 07/20/2018
Entry Accepted: 07/22/2018
Entry Last Modified: 08/04/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society