Издательство: | Книга по требованию |
Дата выхода: | июль 2011 |
ISBN: | 978-3-8381-1760-7 |
Объём: | 160 страниц |
Масса: | 264 г |
Размеры(В x Ш x Т), см: | 23 x 16 x 1 |
The Minimum Linear Arrangement problem consists in finding an ordering of the nodes of a weighted graph, such that the sum of the weighted edge lengths is minimized. We report on the usefulness of a new model within a branch-and-cut-and-price algorithm for solving Minimum Linear Arrangement problems to optimality. The key idea is to introduce binary variables d_{ijk}, that are equal to 1 if nodes i and j have distance k in the permutation. We present formulations for complete and for sparse graphs and explain the realization of a branch-and-cut-and-price algorithm. Furthermore, its different settings are discussed and evaluated. To the study of the theoretical aspects concerning the Minimum Linear Arrangement problem, we contribute a characterization of a relaxation of the corresponding polyeder.
Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.