Test-assignment: a quadratic coloring problem

Jelle Duives, Andrea Lodi, Enrico Malaguti

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
44 Downloads (Pure)


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.
Original languageUndefined
Pages (from-to)549-564
Number of pages16
JournalJournal of heuristics
Issue number4
Publication statusPublished - Aug 2013


  • EWI-25229
  • Heuristics
  • Binary quadratic programming
  • METIS-309626
  • IR-92439
  • Reformulations

Cite this