You are in: Home » Publications » PRIN-kakuro

Risolvere il PRIN-kakuro con la programmazione lineare

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:

max_funded[a]
Numero massimo di progetti di area a che possono venire finanziati;
max_proposed[u]
Numero massimo di progetti che possono essere complessivamente proposti dall'ateneo u. Tale valore viene calcolato tenendo conto del vincolo sul numero di docenti e ricercatori di cui al bando PRIN.

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 ###
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.

Riferimenti

This page validates as XHTML 1.0 strict This page validates as CSS Check the accessibility of this page with WAVE
This page was last updated on May 03 2014 informativa sulla privacy