Data di Pubblicazione:
2008
Citazione:
A branch-and-bound algorithm for the linear ordering problem with cumulative costs / G. Righini. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 186:3(2008), pp. 965-971.
Abstract:
The linear ordering problem with cumulative costs is an -hard combinatorial optimization problem arising from an application in UMTS mobile-phone communication systems. This paper presents a polynomially computable lower bound that is particularly effective when embedded in a branch-and-bound algorithm. The same idea can be further exploited to sort the children nodes at each node of the search tree, in order to find the optimal solution earlier. A suitable truncation of the resulting branch-and-bound algorithm results in a fast constructive heuristic.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Branch-and-bound ; Combinatorial optimization ; Linear ordering problem
Elenco autori:
G. Righini
Link alla scheda completa: