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)