Who can build the best city?
Quadratic Assignment Problem
Interactive Presentation, “Long Night of Research” at the University of Klagenfurt and
Workshop for several school classes at the University of Klagenfurt
27th of April 2012, 10th of April 2013 and 14th December 2014
Didn't you ever want to be the architect of a city? Through a practical experiment the visitors have this opportunity at our station. In a large room we draft a city on the ground that has several building areas. Now the visitors should decide which building (bank, shopping mall, factory, ...) should be constructed on which building area. We additionally specify flows (i.e. the average number of people who drive per day from one building to another one) between all pairs of buildings. The city should be planned such that the total traffic (i.e. the sum of flow times distance over all pairs of buildings) is minimal. For example pairs of buildings with a high associated flow should be constructed at nearby building areas. On a computer the decisions of the visitors are presented graphically and the quality of their cities planned is evaluated. The proposed city planning problem is a practical realization of a very well-known and difficult combinatorial optimization problem, the so-called quadratic assignment problem. Thus at our station the visitors gain insight into the world of combinatorial optimization in a playful way.