文章基本信息

标题：Optimal linear arrangements using betweenness variables
其他标题：Optimal linear arrangements using betweenness variables
本地全文：下载
作者：Caprara, Alberto ; Oswald, Marcus ; Reinelt, Gerhard 等
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2011
卷号：3
期号：3
页码：261-280
DOI：10.1007/mpc.v3i3.60
语种：English
出版社：Mathematical Programming Computation
摘要：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.
关键词：90C27; 90C57; 90C90