We consider the problem of assigning the test variants of a written exam to the desks of a classroom in such a way that desks that are close-by receive different variants. The problem is a generalization of the Vertex Coloring and we model it as a binary quadratic problem. Exact solution methods based on reformulating the problem in a convex way and applying a general-purpose solver are discussed as well as a Tabu Search algorithm. The methods are extensively evaluated through computational experiments on real-world instances. The problem arises from a real need at the Faculty of Engineering of the University of Bologna where the solution method is now implemented.
Test-Assignment: A Quadratic Coloring Problem / J. Duives; A. Lodi; E. Malaguti. - In: JOURNAL OF HEURISTICS. - ISSN 1381-1231. - STAMPA. - 19:(2013), pp. 549-564. [10.1007/s10732-011-9176-0]
Test-Assignment: A Quadratic Coloring Problem
LODI, ANDREA;MALAGUTI, ENRICO
2013
Abstract
We consider the problem of assigning the test variants of a written exam to the desks of a classroom in such a way that desks that are close-by receive different variants. The problem is a generalization of the Vertex Coloring and we model it as a binary quadratic problem. Exact solution methods based on reformulating the problem in a convex way and applying a general-purpose solver are discussed as well as a Tabu Search algorithm. The methods are extensively evaluated through computational experiments on real-world instances. The problem arises from a real need at the Faculty of Engineering of the University of Bologna where the solution method is now implemented.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.