Alcuin's Transportation Problems and Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-1932
- The need to solve {\it 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 {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the $8$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. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's 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 Alcuin's 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.
Author: | Ralf BorndörferORCiD, Martin Grötschel, Andreas Löbel |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1995/11/08 |
Series (Serial Number): | ZIB-Report (SC-95-27) |
ZIB-Reportnumber: | SC-95-27 |
Published in: | 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 |