R&E 8

Catalogue of all
Book Series

List of Books
in this Series

Previous Book

Next Book

Research and Exposition in Mathematics -- Volume 8

   Enlarged Picture

G. Reinelt

The Linear Ordering Problem.
Algorithms and Applications

168 p., soft cover, ISBN 3-88538-208-3, EUR 20.00, 1985

Instances of the linear ordering problem occur in many practical applications. Examples are the one machine scheduling problem with preference constraints, aggregation of individual preferences in the social sciences, triangulation of input-output matrices in economics, paired comparison ranking in sociology or even tournaments in sports.

This monograph applies methods of polyhedral combinatorics to the linear ordering problem. New results on the facial structure of a polytope related to this problem leads to the "linear ordering polytope". Embedded into a branch and bound framework, a computer implementation of this approach is shown to be able to solve real-world instances of the triangulation problem which could not be solved by previous methods. The optimum triangulation of a large number of European input-output tables makes this book not only an interesting theoretical and computational study in applied mathematics, but also a valuable source for economists.

"The book represents an important contribution to polyhedral combinatorics. ... also valuable for economists". (Optimization).

"This book ... is a convincing documentation of the power and the beauty of the ... cutting plane approach ...". (OR Spectrum)