Moreno Marzolla, gennaio 2012
Aggiornamento 30/1/2012: Il prin-kakuro non è l'unico problema di ottimizzazione combinatoria che è necessario risolvere per cercare di procurarsi fondi di ricerca: guarda come affrontare il VQR 2004-2010 con la programmazione lineare intera!
Aggiornamento 16/1/2012: Questa pagina compare al primo posto nella ricerca Google dei termini prin e progetti finanziabili
Il PRIN-kakuro è un problema di ottimizzazione combinatoria proposto da Giuseppe De Nicolao per decidere quanti progetti PRIN ciascun ateneo può proporre nel rispetto dei vincoli numerici espressi (direttamente o indirettamente) dal bando.
Il PRIN-kakuro può essere espresso come un problema di programmazione lineare intera come segue. Sia U l'insieme degli atenei, e A l'insieme delle aree disciplinari. Sono dati i seguenti parametri:
Definiamo le variabili funded[u,a] per denotare il numero effettivamente finanziato di progetti di area a all'ateneo u. I vincoli minimi che la soluzione funded[u,a] deve soddisfare sono i seguenti: (i) ciascun ateneo non può aver finanziati più progetti di quelli massimi che può presentare; (ii) Il numero totale di progetti finanziati per ciascuna area a non può eccedere max_funded[a].
In base ai vincoli precedenti, il problema in generale ammette più di una soluzione ottima. Naturalmente non tutte le soluzioni che soddisfano (i) e (ii) sono ugualmente plausibili. A titolo puramente esemplificativo, il modello include i due vincoli seguenti del tutto arbitrari: (iii) il numero funded[u,a] di progetti di area a finanziati all'ateneo u non può superare 2; (iv) ogni ateneo deve avere almeno un progetto finanziato.
Il modello è descritto nel file prin-kakuro.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.
/* PRIN-KAKURO v2.1 ----------------- Autore : Moreno Marzolla <moreno (at) moreno.marzolla.name> Data : gennaio 2012. Licenza: Questo file e' rilasciato nel pubblico dominio. Si veda http://www.moreno.marzolla.name/prin-kakuro/ per informazioni sul modello */ ### INSIEMI ### set U; # Lista degil atenei set A := 1..14; # Elenco delle aree di ricerca ### PARAMETRI ### param max_funded{A} > 0 integer; # max_funded[a] e' il massimo numero di progetti finanziabili per l'area a param max_proposed{U} > 0 integer; # max_proposed[u] e' il massimo numero di progetti che l'ateneo u puo' complessivamente proporre ### VARIABILI ### var funded{U, A} >= 0 integer; # funded{u,a} e' il numero di progetti nell'area a finanziati per l'ateneo u ### FUNZIONE OBIETTIVO ### ## Massimizzare il numero di progetti finanziati maximize funded_projects: sum{u in U, a in A} funded[u,a]; ### VINCOLI ### ## Il numero di progetti totali effettivamente finanziati per ogni area ## non deve eccedere il numero massimo di progetti finanziabili per quell'area' ## tale numero massimo e' calcolato in http://www.roars.it/online/?p=3073 s.t. limit_funded "limit funded" {a in A}: sum{u in U} funded[u,a] <= max_funded[a]; ## Il numero di progetti finanziati per ciascun ateneo non puo' ## eccedere il numero massimo di progetti presentabili da ## quell'ateneo. s.t. max_limit_proposed "max limit proposed" {u in U}: sum{a in A} funded[u,a] <= max_proposed[u]; ## [IPOTESI ARBITRARIA] Ogni universita' puo' avere al massimo 2 progetti ## finanziati per ogni area. s.t. max_limit_funded "max limit funded" {u in U, a in A}: funded[u,a] <= 2; ## Imponiamo che ogni universita' abbia almeno un progetto finanziato s.t. fairness {u in U}: sum{a in A} funded[u,a] >= 1; ### CALCOLO SOLUZIONE ### solve; ### VISUALIZZAZIONE SOLUZIONE ### printf "\t\t\t\t\t\t\t\tAree\n"; printf "\t\t\t\t "; for {a in A} { printf " %2d ", a; } printf "\n"; for {u in U} { printf "%25s ", u; printf "(%2d su %2d) | ", sum{a in A} funded[u,a], max_proposed[u]; for {a in A} { printf "%2d | ", funded[u,a]; } printf "\n"; } printf "\nTotale progetti finanziati: %d su %d\n", sum{a in A, u in U} funded[u,a], sum{a in A} max_funded[a];
Il modello può essere utilizzato come strumento di supporto
nella fase 2 dell'algoritmo divide et
impera
proposto da Giuseppe De Nicolao per risolvere il
rompicapo del PRIN
. In questa fase ciascun ateneo ha definito
delle preferenze a livello interno su quali (e quanti) progetti
vorrebbe presentare in ciascuna area. Tali preferenze possono essere
descritte mediante vincoli; ad esempio, supponiamo che l'ateneo
XYZ abbia deciso di non presentare alcun progetto per le aree
1, 3 e 4. Questo può essere espresso come:
s.t. cXYZ1 : funded["XYZ",1] = 0; s.t. cXYZ2 : funded["XYZ",3] = 0; s.t. cXYZ3 : funded["XYZ",4] = 0;
o meglio, in forma compatta:
s.t. cXYZ1 {a in {1, 3, 4} } : funded["XYZ",a] = 0;
(GNU MathProg richiede di dare un nome simbolico a ciascun vincolo, cXYZn denota tali nomi). Supponiamo altresì che lo stesso ateneo XYZ desideri presentare tra 2 e 4 proposte nell'area 2, e un numero massimo di 3 proposte nell'area 5. Questi requisiti possono essere espressi come:
s.t. cXYZ4: 2 <= funded["XYZ",2] <= 4; s.t. cXYZ5: funded["XYZ",5] <= 3;
Quindi, una volta che ciascun ateneo avrà espresso le proprie preferenze, il modello sopra può essere usato per determinare se esiste una soluzione ammissibile (ossia se i vincoli esprimono un dominio non vuoto), e in caso affermativo individuare una soluzione ottima.
Per risolvere il modello sono necessari dei parametri numerici, forniti separatamente nei file dati-bando1.dat (prima versione del bando PRIN), e dati-bando2.dat (seconda versione del bando PRIN). Per calcolare una soluzione è sufficiente dare il comando (in ambiente Linux/Unix):
glpsol --math -m prin-kakuro.mod -d dati-bando2.dat
(per effettuare il calcolo usando i parametri della prima versione
del bando PRIN basta sostituire dati-bando2.dat
con
dati-bando1.dat
nel comando sopra). La soluzione
verrà mostrata in forma tabellare, come ad esempio:
Bari (13 su 13) | 0 | 9 | 0 | 3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Politecnico Bari ( 3 su 3) | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | LUM J. Monnet ( 1 su 1) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
Ogni riga contiene: il nome dell'ateneo, il numero di progetti finanziati sul numero di domande presentate, seguito da 14 colonne contenenti il numero di progetti finanziabili per ciascuna delle 14 aree.
Nonostante i problemi di programmazione lineare intera siano in genere NP-hard, la formulazione sopra descritta del problema del PRIN-kakuro può essere risolta efficientemente anche su hardware poco potente.