The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
The book is devoted to the linear ordering problem. The authors survey state-of-the-art optimization methods, approximation results and discuss open questions concerning the linear ordering problem. The reader is provided with the basic definitions and basic heuristic methods in optimization. The set of publicly available benchmark instances for conducting computational experiments is described. Separate chapters discuss meta-heuristics and branch-and-cut methods. The authors study the convex hull of feasible solutions of the linear ordering problem and present a special version of branch-and-cut algorithm based on polyhedral combinatorics. Computational experiments comparing different methods for the linear ordering problem are reported.
scientific article; zbMATH DE number 5827306