| SC 95-27 | Ralf Borndörfer, Martin Grötschel, Andreas Löbel
Alcuins Transportation Problems and Integer Programming Appeared in: Charlemagne and his Heritage : 1200 Years of Civilization and Science in Europe. P. L. Butzer et al. (eds.) Vol. 2: The Mathematical Arts. Brepols, Turnhout, Belgium, 1998. Pp. 379-409 |   |
Abstract: The need to solve transportation problems was
and still
is one of the driving forces behind the development of the mathematical
disciplines of graph theory, optimization, and operations research.
Transportation problems seem to occur for the first time in the literature in the
form of the four River Crossing Problems in the book Propositiones ad
acuendos iuvenes. The Propositiones --the oldest collection of
mathematical problems written in Latin-- date back to the 
th century A.D. and
are attributed to Alcuin of York, one of the leading scholars of his time, a
royal advisor to Charlemagne at his Frankish court.
Alcuins river crossing problems had no impact on the development of mathematics.
However, they already display all the characteristics of todays large-scale real
transportation problems. From our point of view, they could have been the
starting point of combinatorics, optimization, and operations research. We show
the potential of Alcuins problems in this respect by investigating his
problem 18 about a wolf, a goat and a bunch of cabbages with current mathematical
methods. This way, we also provide the reader with a leisurely introduction into
the modern theory of integer programming.