6533b81ffe1ef96bd1278487

RESEARCH PRODUCT

Branch-and-Bound

Gerhard ReineltRafael Martí

subject

Mathematical optimizationsymbols.namesakeBranch and boundBundle methodQuadratic assignment problemComputer scienceLagrangian relaxationCombinatorial optimization problemsymbolsLinear ordering

description

We now turn to the discussion of how to solve the linear ordering problem to (proven) optimality. In this chapter we start with the branch-and-bound method which is a general procedure for solving combinatorial optimization problems. In the subsequent chapters this approach will be realized in a special way leading to the so-called branch-and-cut method. There are further possibilities for solving the LOP exactly, e.g. by formulating it as dynamic program or as quadratic assignment problem, but these approaches did not lead to the implementation of practical algorithms and we will not elaborate on them here.

yearjournalcountryeditionlanguage
2010-09-12
https://doi.org/10.1007/978-3-642-16729-4_4