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

DOI10.1007/S11590-009-0130-0MaRDI QIDQ732777zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Minimum linear arrangements
• Contributions to the minimum linear arrangement problem.
• A compact quadratic model and linearizations for the minimum linear arrangement problem
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Lower bounds for the minimum linear arrangement of a graph

Cites work

• scientific article; zbMATH DE number 4070955 (Why is no real title available?)
• scientific article; zbMATH DE number 3700882 (Why is no real title available?)
• scientific article; zbMATH DE number 3526692 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1795730 (Why is no real title available?)
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A genetic hillclimbing algorithm for the optimal linear arrangement problem
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Experiments on the minimum linear arrangement problem
• Graph minimum linear arrangement by multilevel weighted edge contractions
• On bipartite drawings and the linear arrangement problem
• On the exact solution of a facility layout problem
• Optimal Assignments of Numbers to Vertices
• Optimal Linear Ordering
• Optimal Numberings of an $N \times N$ Array
• Optimal linear labelings and eigenvalues of graphs
• QAPLIB - a quadratic assignment problem library

Cited in

(16)

• A compact quadratic model and linearizations for the minimum linear arrangement problem
• Minimum linear arrangements
• An improved mixed-integer programming model for the double row layout of facilities
• Simulated annealing and tabu search approaches for the Corridor Allocation Problem
• Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
• Construction heuristics for the single row layout problem with machine-spanning clearances
• The scaling of the minimum sum of edge lengths in uniformly random trees
• The single row facility layout problem: state of the art
• Contributions to the minimum linear arrangement problem.
• New exact approaches to row layout problems
• Optimal linear arrangements using betweenness variables
• An improved approximation ratio for the minimum linear arrangement problem
• A parallel ordering problem in facilities layout
• A genetic hillclimbing algorithm for the optimal linear arrangement problem
• On a binary distance model for the minimum linear arrangement problem
• A new hybrid evolutionary algorithm for the MinLA problem

Describes a project that uses

Uses Software

• QAPLIB
• CPLEX

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q732777)