Optimal linear arrangements using betweenness variables

  • We solve for the first time to proven optimality the small instances in the classical literature benchmark of Minimum Linear Arrangement. This is achieved by formulating the problem as an ILP in a somehow unintuitive way, using variables expressing the fact that a vertex is between two other adjacent vertices in the arrangement. Using (only) these variables appears to be the key idea of the approach. Indeed, with these variables already the use of very simple constraints leads to good results, which can however be improvedwith amore detailed study of the underlying polytope.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Alberto Caprara, Marcus Oswald, Gerhard Reinelt, Robert Schwarz, Emiliano Traversi
DOI:https://doi.org/10.1007/s12532-011-0027-7
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2011
Tag:Software; Theoretical Computer Science
Volume:3
Issue:3
Page Number:20
First Page:261
Last Page:280
Mathematical Programming Computation :MPC 2011 - Issue 3
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.