Atnaujintas knygų su minimaliais defektais pasiūlymas! Naršykite ČIA >>
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.
| Autorius: | Hanna Seitz |
| Leidėjas: | Südwestdeutscher Verlag für Hochschulschriften AG Co. KG |
| Išleidimo metai: | 2015 |
| Knygos puslapių skaičius: | 160 |
| ISBN-10: | 3838117603 |
| ISBN-13: | 9783838117607 |
| Formatas: | 220 x 150 x 11 mm. Knyga minkštu viršeliu |
| Kalba: | Anglų |
Parašykite atsiliepimą apie „Contributions to the Minimum Linear Arrangement Problem: On a Binary Distance Model for the Minimum Linear Arrangement Problem“
