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.
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.
A branch-and-bound algorithm for the linear ordering problem with cumulative costs
G. RighiniPrimo
2008
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.