A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

DOI10.1007/s11590-009-0130-0zbMath1180.90205OpenAlexW2075799742MaRDI QIDQ732777

André R. S. Amaral

Publication date: 15 October 2009

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-009-0130-0

zbMATH Keywords

integer programmingminimum linear arrangementvertex ordering problems

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items (10)

Construction heuristics for the single row layout problem with machine-spanning clearances ⋮ A parallel ordering problem in facilities layout ⋮ Minimum linear arrangements ⋮ The single row facility layout problem: state of the art ⋮ An improved mixed-integer programming model for the double row layout of facilities ⋮ Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions ⋮ Simulated annealing and tabu search approaches for the Corridor Allocation Problem ⋮ Optimal linear arrangements using betweenness variables ⋮ New exact approaches to row layout problems ⋮ A compact quadratic model and linearizations for the minimum linear arrangement problem

Uses Software

• QAPLIB
• CPLEX

Cites Work

• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• Optimal linear labelings and eigenvalues of graphs
• QAPLIB - a quadratic assignment problem library
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• On the exact solution of a facility layout problem
• On Bipartite Drawings and the Linear Arrangement Problem
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Optimal Numberings of an $N \times N$ Array
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Optimal Linear Ordering
• Experiments on the minimum linear arrangement problem
• Graph minimum linear arrangement by multilevel weighted edge contractions
• Optimal Assignments of Numbers to Vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem