Optimal linear arrangements using betweenness variables

DOI10.1007/s12532-011-0027-7zbMath1257.90081OpenAlexW2090282626MaRDI QIDQ1762457

Marcus Oswald, Alberto Caprara, Emiliano Traversi, Gerhard Reinelt, Robert Schwarz

Publication date: 27 November 2012

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-011-0027-7

zbMATH Keywords

branch-and-bound algorithmcomputational resultspolyhedral combinatoricslinear arrangement problem

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Improved exact approaches for row layout problems with departments of equal length, Semidefinite relaxations of ordering problems, Minimum Linear Arrangement of Generalized Sierpinski Graphs, On a binary distance model for the minimum linear arrangement problem, A mixed-integer linear programming approach for the t-row and the multi-bay facility layout problem, Maximum incomplete recursive circulants in graph embeddings, Projection Methods in Conic Optimization, Global Approaches for Facility Layout and VLSI Floorplanning, New exact approaches to row layout problems, Unnamed Item, Unnamed Item, A compact quadratic model and linearizations for the minimum linear arrangement problem

Uses Software

• SCIP
• CPLEX
• ZIB Optimization Suite

Cites Work

• Unnamed Item
• Unnamed Item
• A polyhedral approach to the single row facility layout problem
• A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem
• A new lower bound for the single row facility layout problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Generating lower bounds for the linear arrangement problem
• On the exact solution of a facility layout problem
• Approximating Layout Problems on Random Geometric Graphs
• Laying Out Sparse Graphs with Provably Minimum Bandwidth
• Decorous Lower Bounds for Minimum Linear Arrangement
• An Exact Approach to the One-Dimensional Facility Layout Problem
• On the cut polytope
• Experiments on the minimum linear arrangement problem