On the Complexity of the Paper Selection Problem for the Italian Research Quality Evaluation (VQR)

ABSTRACT

This work addresses the paper selection problem that each Italian university and department faced in the context of the research quality evaluation (VQR) of the Italian university system for the period 2020–2024. Given the set of researchers of a university and their associated papers, the problem consists of selecting a fixed number of researcher, paper pairs, as established by the Ministry, while respecting bounds on the minimum and maximum number of papers selectable for each researcher, as well as the maximum number of times a paper can be selected. Each pair is associated with a score, which depends on several bibliometric parameters related to both the paper and the author, and the goal of the problem is to select the pairs so as to maximize the total score. In this paper, we consider two versions of the problem, modeling the departments' and the university's perspectives, and for each of them, we provide an integer linear programming formulation. Moreover, we present two proofs showing that the problem can be solved optimally in polynomial time. The first proof consists of a polynomial‐time reduction to the capacitated minimum cost flow problem and is introduced to allow the problem to be solved without the need for commercial solvers (and the associated license costs); this is the ideal approach for any commercial software that already faces this problem. The second proof shows that the constraint matrices of the two formulations are totally unimodular. This property, together with the integrality of the right‐hand sides, ensures that the linear relaxations yield integer optimal solutions, which can be easily computed using the simplex method.