An Automatically Designed Recombination Heuristic for the Test-Assignment Problem
Marcelo de Souza, Marcus Ritt · 2018
A way of minimizing the opportunity of cheating in exams is to assign different tests to students. The likelihood of cheating then depends on the proximity of the students' desks, and the similarity of the tests. The test-assignment problem is to find an assignment of tests to desks that minimizes that total likelihood of cheating. The problem is a variant of a graph coloring problem and is NP-hard. We propose a new heuristic solution for this problem. Our approach differs from the usual way of designing heuristics in two ways. First, we reduce test-assignment to the more general unconstrained binary quadratic programming. Second, we search for a good heuristic using an automatic algorithm configuration tool that evolves heuristics in a space of algorithms built from known components for binary quadratic programming. The best hybrid heuristics found repeatedly recombine elements of a population of elite solutions and improve them by a tabu search. Computational tests suggest that the resulting algorithms are competitive with existing heuristics that have been designed manually.