Risolvere il PRIN-kakuro con la programmazione lineare

Moreno Marzolla, gennaio 2012

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

• G. De Nicolao, PRIN 2011: la strategia del Kakuro
• G. De Nicolao, PRIN 2011: Kakuro reloaded