Affrontare la VQR 2010 con la programmazione lineare

Moreno Marzolla, febbraio 2012

Il VQR 2004-2010 si propone di valutare la qualità della ricerca prodotta da docenti e ricercatori di università ed enti pubblici di ricerca italiani. Ciascun soggetto seleziona per la valutazione un certo numero di pubblicazioni (che ritiene in qualche modo "migliori"), che verranno sottoposte a giudizio analitico da parte di revisori esterni. Ciascuna pubblicazione riceverà un punteggio numerico (1=eccellente, 0.8=buono, 0.5=accettabile, 0=limitato, -1=non valutabile, -2=frode o plagio).

Il bando VQR ufficiale prevede una serie di vincoli relativi alla scelta delle pubblicazioni da inviare, che rendono la procedura descritta sopra piuttosto complessa. Innanzitutto, ciascun soggetto presenta un numero di pubblicazioni pari ad un valore fissato nel bando (esempio, un professore ordinario deve sottoporre a valutazione 3 pubblicazioni, un ricercatore da un minimo di 0 ad un massimo di 3, in base alla data di presa di servizio; altri valori sono previsti per il personale degli enti pubblici di ricerca). Ogni pubblicazione in meno rispetto al numero fissato del bando comporta una punteggio negativo pari a -0.5 punti.

Un ulteriore vincolo consiste nel fatto che, all'interno di ogni struttura, una pubblicazione potrà essere sottoposta a valutazione da al più un solo autore afferente a tale struttura. Ad esempio, se Tizio, Caio e Sempronio lavorano per la stessa struttura e hanno coautorato una pubblicazione X, al più uno tra Tizio, Caio e Sempronio potrà presentare X alla valutazione.

Lo scopo di ciascuna struttura è quello di ottenere il punteggio massimo possibile, ottenuto facendo in modo che (i) ciascun soggetto sottoposto presenti tante pubblicazioni quante richieste, della qualità più elevata possibile, e (ii) ogni pubblicazione inviata a valutazione non venga contemporaneamente presentata da un altro soggetto appartenente alla stessa struttura. Si noti che i punteggi vengono assegnati dopo la presentazione delle pubblicazioni, e quindi non sono noti a priori. È comunque plausibile supporre che i soggetti abbiano più o meno chiaro quali siano i prodotti "migliori" in loro possesso, e ovviamente tenderanno a sottoporre a valutazione proprio quelli.

È evidente che soddisfare i vincoli di cui sopra non è facile. Anche l'ANVUR sembra avere presente il problema (ma non la soluzione), poiché nel bando si legge:

I prodotti con più autori possono essere presentati una sola volta da parte della struttura, pena l’esclusione del prodotto dalla valutazione. In caso di uno stesso prodotto presente nella lista predisposta da più soggetti valutati, la struttura provvede a risolvere al suo interno i conflitti di attribuzione, a livello di soggetti valutati, dipartimenti, aree. Per evitare una seconda tornata di inserimenti di prodotti da parte dei soggetti valutati, questi devono inserire nella lista un numero di prodotti tale da consentire margini sufficienti di scelta alle strutture. Ciò vale in particolare nel caso in cui il soggetto valutato inserisca prodotti con più coautori appartenenti alla struttura.

L'approccio di inserire nella lista un numero di prodotti tale da consentire margini sufficienti di scelta è certamente molto approssimativo. Allo scopo di fornire uno strumento di supporto ai soggetti valutati e alle strutture che devono scegliere le pubblicazioni, verrà di seguito illustrata la formulazione del problema come problema di programmazione lineare intera (lo stesso tipo di problema del PRIN-kakuro). È importante sottolineare che quanto segue deriva dalla mia personale interpretazione del problema del VQR, che potrebbe non coincidere con l'interpretazione ministeriale. Al momento attuale molti dettagli pratici non sono ancora stati chiariti, è pertanto probabile che l'algoritmo risolutivo dovrà essere aggiornato alla luce delle eventuali novità.

Sia Authors l'insieme dei soggetti sottoposti a valutazione (ossia gli autori degli articoli), Papers l'insieme degli articoli, e Authored un insieme di coppie (a,p) che denotano il fatto che l'autore a ha coautorato la pubblicazione p. Definiamo i seguenti parametri:

nump[a]

Numero di prodotti che l'autore a deve sottoporre a valutazione;

weights[p]

Il punteggio (presunto) che verrà assegnato alla pubblicazione p;

Definiamo la variabile binaria sel[a,p] che vale 1 se e solo se l'autore a sottopone a valutazione la pubblicazione p. I vincoli che la soluzione sel[a,p] deve soddisfare sono i seguenti: (1) ogni autore a non puo' presentare più di nump[a] pubblicazioni; (2) ogni pubblicazione p non puo' essere presentata da più di un autore; (3) ogni autore puo' presentare solo articoli di cui è (co)autore. La funzione obbiettivo da massimizzare è la somma dei punteggi attribuiti a tutti gli articoli presentati, tenendo conto che se qualcuno presenta meno articoli di quanto richiesto, ogni articolo mancante vale -0.5 punti.

I vincoli di cui sopra sono rappresentati nel file vqr.mod utilizzando GNU MAthProg (un sottoinsieme del linguaggio di modellazione AMPL). GNU MathProg è parte del GNU Linear Programming Kit (GLPK), un software libero in grado di risolvere efficientemente problemi di ottimizzazione lineare.

La funzione obbiettivo consiste nel massimizzare il punteggio delle pubblicazioni presentate, tenendo conto che ogni pubblicazione in meno di quanto richiesto comporta una penalizzazione di 0.5 punti. I vincoli c1, c2 e c3 del file MathProg rappresentano i vincoli (1), (2) e (3), rispettivamente, descritti sopra.

/*

  VQR  v1.1
  ---------

  Autore : Moreno Marzolla <moreno (at) moreno.marzolla.name>
  Data   : febbraio 2012. 
  Licenza: Questo file e' rilasciato nel pubblico dominio.

  Si veda http://www.moreno.marzolla.name/vqr/ per informazioni sul 
  modello

*/

set Authors; # Insieme degli autori

set Papers; # Insieme delle pubblicazioni

set Authored within (Authors cross Papers); 
## (a,p) appartiene all'insieme Authored se e solo se l'autore a ha 
## (co-)autorato il paper p

param nump{Authors} > 0, integer; 
## nump[a] e' il numero di pubblicazioni che l'autore a dovrebbe inviare

param weights{Papers} >= 0; 
## weights[p] e' il peso presunto assegnato alla pubblicazione p

var sel{Authors, Papers} binary; 
## sel[a,p]=true sse l'autore a presentera' l'articolo p alla valutazione

## Funzione obbiettivo: massimizzare la valutazione complessiva,
## tenendo conto che ogni articolo in meno di quanto richiesto vale -0.5 punti
maximize obj: 
  (sum{a in Authors, p in Papers} sel[a,p]*weights[p]) +
  (sum{a in Authors} -0.5 * (nump[a]-sum{p in Papers} sel[a,p]));

## L'autore a deve presentare al piu' nump[a] pubblicazioni
s.t. c1 {a in Authors}: sum{p in Papers} sel[a,p] <= nump[a];

## Una pubblicazione puo' essere scelta al piu' da un autore
s.t. c2 {p in Papers}: sum{a in Authors} sel[a,p] <= 1;

## Un autore non puo' sottoporre a valutazione un articolo che non ha coautorato
s.t. c3 {(a,p) in (Authors cross Papers) diff Authored}: sel[a,p] = 0;

solve;

## Stampa per ogni autore la lista delle pubblicazioni che deve presentare
for {a in Authors} {
  printf "%s\n", a;
  for {p in Papers : sel[a,p] = 1} {
    printf "\t%s %f\n", p, weights[p];
  }
}

data;
## Esempio di parametri ##

## Definizione dell'insieme degli autori
set Authors := 
"A1",
"A2",
"A3";

## Definizione dell'insieme degli articoli
set Papers :=
"P1",
"P2",
"P3",
"P4",
"P5",
"P6";

## Definizione dei pesi degli articoli
param weights :=
"P1" 0.5
"P2" 0.5
"P3" 0.8
"P4" 0.8
"P5" 1.0
"P6" 1.0 ;

## Definizione del numero di pubblicazioni che ciascun autore deve presentare
param nump :=
"A1" 3
"A2" 2
"A3" 1 ;

## Ciascuna coppia (a,p) rappresenta il fatto che a e' tra gli autori della
## pubblicazione p
set Authored :=

# Autore A1
(A1, P1)
(A1, P4)
(A1, P5)

# Autore A2
(A2, P1)
(A2, P2)
(A2, P5)
(A2, P6)

# Autore A3
(A3, P2)
(A3, P3)
(A3, P6) ;

È interessante osservare come il problema abbia qualche somiglianza con i problemi di matching su grafi. L'esempio incluso nel modello vqr.mod puo' essere rappresentato dalla figura seguente:

I nodi verdi di sinistra rappresentano i tre autori A1, A2 e A3. I nodi azzurri a destra rappresentano le pubblicazioni, etichettate da P1 a P6. I numeri accanto agli autori indicano il numero di pubblicazioni che ciascuno deve presentare, mentre i numeri accanto alle pubblicazioni indicano il peso. Ogni arco tra un autore a e una pubblicazione p rappresenta il fatto che a ha coautorato p. Gli archi in grassetto rappresentano la soluzione calcolata da GLPK: si noti che in questo caso ogni nodo autore ha un numero di archi incidenti selezionati esattamente pari al numero di pubblicazioni da presentare; ogni pubblicazione ha al più un singolo arco incidente selezionato, come richiesto dal vincolo (2).

A partire dalla rappresentazione sopra, è possibile ricondurre il problema del VQR ad un problema di assegnazione che può essere risolto in tempo polinomiale. Un problema di assegnazione è definito come segue: dati n agenti, n task, e una matrice C(i,j) di valori reali che rappresenta il costo in cui si incorre per far eseguire il task j all'agente i, si individui una allocazione degli agenti ai task tale che (i) ogni agente esegua esattamente un task, (ii) ogni task sia eseguito esattamente da un agente, e (iii) il costo complessivo sia minimo.

Il problema del VQR può essere ricondotto ad un problema di assegnazione come segue. Ogni nodo autore a viene replicato tante volte quante sono le pubblicazioni che deve presentare (quindi un autore che deve presentare 3 pubblicazioni sarà associato a tre nodi). Questo fa sì che ciascun autore "virtuale" debba presentare esattamente una singola pubblicazione, come richiesto dal problema di assegnazione in forma canonica. Per ciascuna istanza di ogni nodo autore si aggiunge anche una pubblicazione "virtuale" di peso -0.5, che viene scelta solamente quado non è disponibile alcuna altra pubblicazione di peso positivo e rappresenta la pubblicazione non presentata. Infine, per rendere il numero di pubblicazioni uguale al numero di autori, si inseriscono autori fittizi associati con peso zero a tutte le pubblicazioni esistenti. Per rendere il grafo completo, come richiesto in generale dagli algoritmi risolutivi dei problemi di assegnazione, si può associare ciascun autore a tutte le pubblicazioni non sue con costo infinito; questo fa sì che tali associazioni non verranno mai prese in considerazione. Una ultima osservazione: scopo dei problemi di assegnazione è di rendere il costo complessivo minimo, mentre l'obbiettivo del VQR è di massimizzare il peso delle pubblicazioni presentate. Nella trasformazione, quindi, sarà necessario negare il peso delle pubblicazioni per ottenere un problema di assegnazione in forma canonica.

Il problema di assegnazione può essere risolto in tempo polinomiale utilizzando l'algoritmo di Kuhn—Munkres.