Submitted manuscript, 191 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Decorous lower bounds for minimum linear arrangement
AU - Caprara, A
AU - Letchford, A N
AU - Salazar, J J
PY - 2011
Y1 - 2011
N2 - Minimum Linear Arrangement is a classical basic combinatorial optimization problem from the 1960s, which turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best known solution value often has one more digit than the best known lower bound value. In this paper, we propose a linear-programming based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best known solutions are indeed not far from optimal for most of the benchmark instances.
AB - Minimum Linear Arrangement is a classical basic combinatorial optimization problem from the 1960s, which turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best known solution value often has one more digit than the best known lower bound value. In this paper, we propose a linear-programming based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best known solutions are indeed not far from optimal for most of the benchmark instances.
KW - combinatorial optimisation
KW - cutting planes
KW - graph layout problems
U2 - 10.1287/ijoc.1100.0390
DO - 10.1287/ijoc.1100.0390
M3 - Journal article
VL - 23
SP - 26
EP - 40
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
SN - 1526-5528
IS - 1
ER -