Prolog, Web Semantico e Social Network

All'università e per scopi personali, per 3-4 anni ho sperimentato il Prolog. Tale linguaggio fa parte della famiglia dei linguaggi della Logical Programming, molto interessante e basato su predicati e clausule, con uno schema tipico Soggetto Predicato Valore.

Dopo una fase in cui il Prolog si era stagnato, ecco che i progetti Open Source tirano fuori dal cilindro
il pacchetto software SWI-PROLOG, dal nome dell'università di Amsterdam "Sociaal-Wetenschappelijke Informatica", e il cui autore principale è Jan Wielemaker (Vedi http://it.wikipedia.org/wiki/SWI-Prolog ).

L'importanza del SWI-Prolog e della sua ripresa risiede tutto dietro a 4 cose:  il Web semantico e la Social Network Analysis, i motori di ricerca e la problematica del knowledge Management nelle aziende.

Il concetto è questo: "Se nel pubblicare su Web i dati, essi sono accompagnati da particolari metadati semantici che permettono di relazionare le informazioni e la loro rilevanza, allora successivamente è possibile studiare i grafi, statici e dinamici, che si formano a seguito delle relazioni di aggregazione stabilite naturalmente tra le persone e comprendere il loro comportamento. In tal modo si possono a scopo di marketing segmentare le persone, sui gusti etc e poter fare advertising mirato, pubblicità e offerte".

Il fine ultimo è la Social Network Analisys, analizzando i grafi e i "cluster di dati" che si formano, con algoritmi particolari (vedi l'articolo "Introduzione agli algoritmi di clustering http://www.gruppoeratostene.com/articoli/Algoritmi%20di%20clustering.pdf).

Per ottenere tali dati, il "trucco" è di offrire tools di aggregazione sociale: Facebook, Google, Twitter, etc. I vostri dati saranno valutati, verrete osservati come interagite nel gruppo, se siete dei leader, se siete l'anello di congiunzione tra più gruppi, se avete peso sugli altri, quanto interagite etc. (leggetevi cosa sono le Social Network e i grafi associati è interessante tutta la teoria, altrimenti suggeritemi cosa non avete ben compreso e proverò a spiegarvelo).

Ma per ottenere qualcosa di meglio non si può rinunciare al Web semantico: non basta HTML, XML etc. Si devono introdurre concetti di relazione e gli strumenti adatti a tale scopo  discendono da concetti di Prolog: Soggetto Predicato Valore.
Ad esempio questo si può ottenere con tre risorse già esistenti: l'XML, gli URI e i namaspace ma in una forma più attinente. Difatti si usano:
- RDF (Resource Description Framework)
- N3  ed N3 con namespace (un miglioramento rispetto a RDF)
- OWL
- etc.

Se occorre aggiungere metadati in abbondanza, occorre anche produrre strumenti di produttività che possano snellire la fase di aggiunta dei metadati tra le pagine web o tra i Referee dei documenti scientifici o altro etc. In tal modo si avrà un web che "ragiona", che possa trovare cose attinenti con una maggiore precisione, distinguire se un riferimento è già stato trovato e presentato.

Si possono creare Page Searcher logici o meta-crowler logici (Meta-PrologCrowler) ed efficaci XML-PrologParser per rendere migliori i motori di ricerca attuali e far decollare il Knowledge Management.

A tal proposito si potranno creare anche Web server ad hoc, o aggiungere plug-in a quelli esistenti. Intanto sono nate librerie come PiLLoW per integrare la Logic Programming ed il WWW.

Comunque il prolog è efficace anche nell'analisi dei grafi (e non solo). Non ci credete? Installatevi SWI-Prolog e ricopiate il programmino che vi propongo (mettendolo in un file grafo.pl):

arco(a,b,5).
arco(b,c,5).
arco(c,d,7).
arco(d,a,4).
arco(b,d,9).
arco(d,e,5).
arco(a,e,7).
arco(c,e,8).

/* connessione a doppio senso di marcia */
andare(X,Y,K) :- arco(X,Y,K).
andare(X,Y,K) :- arco(Y,X,K).

/* raggiungibile con 1,2,3 passi */
raggiungibili(A,B) :- andare(A,B,_).
raggiungibili(A,B) :- andare(A,X,_), andare(X,B,_).
raggiungibili(A,Z) :- andare(A,X,_), andare(X,Y,_), andare(Y,Z,_).

/* raggiungibile con calcolo della LUNGHEZZA */
percorso1(A,Z,K) :- andare(A,Z,K).
percorso2(A,Z,K) :- andare(A,Z,K1), percorso1(X,Z,K2), K is K1+K2.
percorso3(A,Z,K) :- andare(A,Z,K1), percorso2(X,Z,K2), K is K1+K2.

A questo punto avviate SWI-Prolog. Fate: File->Consult->grafo.pl ed ora proviamo a fare delle domande.

Vogliamo sapere se esiste un percorso tra a e d (attenzione a digitare il punto che è importante).
percorso1(a,d,X).
X=4
La risposta è Sì: è a distanza 4

Vogliamo sapere se esistono altri percorsi tra a e d? digitiamo ";" ed esce false.

Proviamo:
percorso1(b,e,X).
false.

Proviamo:
percorso2(a,e,X).
X=12;
X=14;
X=15;
false.

Proviamo invece:
percorso3(a,e,X).
X = 17 ;
X = 19 ;
X = 20 ;
X = 19 ;
X = 21 ;
X = 22 ;
X = 20 ;
X = 22 ;
X = 23 ;
false.

Come si vede realizza anche una base dati di conoscenza tutto sommato, e potrebbe essere utile, questo esempio, per delle tabelle di routing di rete.

Alla prox.

Riferimenti
www.swi-prolog.org
http://it.wikipedia.org/wiki/Web_semantico

Schedulazioni vincenti e labirinti tenebrosi, con il bastone da maresciallo nello zaino ...

Il vantaggio di usare strumenti LP è di astrarsi dalla programmazione software e concentrarsi solo sulla formulazione matematica. Ciò non toglie che si può programmare in progetti più grandi con C/C++/Java e librerie LP disponibili (come le API offerte da GNUWin32 o anche per Linux/Unix con l'uso di Database).
 
Vediamo un classico: dovete fare con Microsoft Project un diagramma di GANTT con risorse, task in cascata o parallelizzabile e le milestone con ogni opportuna data e descrizione; poi vi hanno richiesto il diagramma di Pert per comprendere i task critici. Sapete l'inizio e la fine desiderata, quanto serve per ogni attività, quante persone, ma occorre far entrare il tutto nel  periodo richiesto. E' possibile o impossibile? Come e quali attività si devono parallelizzare? Quello ottenuto è il meglio possibile o esistono anche altre soluzioni?

Al di là di ulteriori elementi che dipendono dal tipo di lavoro in gioco, stiamo parlando di un problema di pianificazione o scheduling, che rientra tra i problemi NP-completi!

In sostanza le stesse informazioni accennate sopra, come barre nel GANTT e le timeline si possono tradurre in un grafo matematico dove i nodi possono essere i nomi dei task, gli archi orientati il cambio di sequenza da un task ad un altro (e la dipedendenza anche tra essi sequenziale), mentre i pesi sugli archi possono rappresentare il tempo necessario allo svolgimento del task. Nel grafo potremmo avere anche parallelizzazioni di task , cioè situazioni in cui da un nodo escono contemporaneamente più archi verso altri nodi.

Con un grafo, quindi, si possono formulare varie tipologie di problemi. Per grafo pesato orientato intendiamo
una struttura G(N, A), con N insieme dei nodi e cardinalità | N |, ed A insieme degli archi e cardinalità | A |.
L'insieme degli archi, A, è caratterizzato da un orientamento da nodo origine ad uno destinazione i,j.

In generale l'obiettivo di un "problema di scheduling" matematico è di ottimizzare una o più grandezze di
performance tra le seguenti:
- minimizzare la massima "lateness" o il massimo ritardo (non dite che ve l'ho detto io!)
- minimizzare i costi/tempi del setup
- minimizzare il "makespan" (la massima lunghezza temporale o l'elapsed time totale)

Per risolvere, nel miglior modo possibile, un tale problema sono possibili varie strategie:
1 - algoritmi tipici della teoria dello scheduling
2 - algoritmi legati ai grafi

Un algoritmo tipico della teoria dello scheduling è quello MST (Minimum Spanning Tree) o minimo albero ricoprente. Nel MST il problema è definito nel seguente modo: sia dato un grafo orientato pesato G(N, A), con un insieme di interi senza segno definito sugli archi, allora l'obiettivo è quello di determinare una struttura che connetta tutti i nodi del grafo con archi di peso minimo.

Un albero ricoprente di costo minimo è tipicamente una struttura con un unico nodo origine, detto radice, ed una serie di rami; il "cammino" da individuare è composto dall'insieme dei nodi in una sequenza tale che la somma dei pesi sui rami sia la minima possibile.

E' evidente che l'MST ci porta a minimizzare il "makespan". Poichè abbiamo a che fare con un grafo a numero di nodi fissi, (ricordate cosa abbiamo detto circa il problema di Steiner?) allora è possibile usare l'algoritmo di Kruskal (vi rimando al blog precedente per tale algoritmo).

Ma dobbiamo aprire una parentesi sui labirinti per comprendere il punto 2 precedente e concludere il discorso sullo scheduling. Quindi c'è un interrupt e salvate un attimo il contesto sullo stack.

Come vedremo le tecniche di ottimizzazione congiunte spesso vengono utilizzate per risolvere problemi complessi che non ricadono in una branca specifica dell'ottimizzazione.

Un tipico algoritmo per trattare i labirinti è l'algoritmo di Tremaux. Ne esistono anche altri per la robotica, euristici e random (vedi Wikipedia) ma qui è sufficiente quello classico.

L'algoritmo di Tremaux consiste nel seguire un percorso, scelto a caso all'interno del labirinto, fino a raggiungere un incrocio, marcando la via che è stata percorsa fino a quel momento (nel caso in cui il corridoio conduca a un vicolo cieco è necessario tornare indietro fino all'incrocio precedente, marcando la via all'andata e al ritorno).

Quando si giunge a un incrocio di più corridoi si prende preferibilmente una via che non è stata segnata come percorsa in precedenza, e se ciò non è possibile si prende una via percorsa una sola volta. In ogni caso non è permesso scegliere una via che è stata già marcata due volte. Iterando il procedimento per ogni incrocio che si trova sul proprio percorso, l'algoritmo permette di raggiungere l'uscita (o se il labirinto non ha altre uscite oltre a quella imboccata per entrare, di tornare all'entrata).

La "tecnica di backtracking" è una tecnica euristica generale utilizzabile nei grafi e negli alberi; serve a tracciarsi i percorsi e durante esso appena si ottiene una informazione che il cammino fatto è peggiore di un altro si scarta e si ritorna indietro per un ramo non percorso. Alla fine si rimane col miglior percorso tracciato.

Se ci riflettiamo, una pianificazione assomiglia un pò all'attraversamento di un labirinto, dove ci sono un ingresso/inizio ed una uscita/fine, e dove occorre scegliere i percorsi e marcandoli, in che direzione li percorriamo (grafo orientato) e se una o due volte.

Il percorso o cammino in effetti è l'insieme dei rami/task da scegliere da legare insieme; mentre lungo il ramo del percorso troviamo degli oggetti di un certo peso da mettere in uno zaino, che potrebbero essere anche dei job da fare per ottenere un oggetto finito.

Mi direte ma nel labirinto non c'è parallelismo ... non è detto: dipende da quante persone lo percorrono contemporaneamente.

E' come se il problema dello scheduling fosse riconducibile a vari sottoproblemi:
- teoria dei grafi e dei labirinti
- algoritmi della teoria scheduling
- il problema dello zaino

In effetti di un labirinto, almeno inizialmente, nessuno ne conosce i percorsi, così come nelle pianificazioni che occorre studiare bene come ottenere una pianificazione decente e coerente.

Da quanto detto un labirinto è rappresentabile con un grafo orientato ed in esso occorre:
- individuare il percorso
- individuare gli elementi secondo una tecnica di backtracking

In particolare durante l'attraversamento di un labirinto ci si segna i nodi e gli archi orientati e il relativo peso.

Una volta individuato il labirinto occorre iniziare a vedere quale oggetto/task ooccorre estrarre per arrivare alla successiva lavorazione. Occorre stare attenti a semplificare il problema altrimenti si arriva ad aggiungere molte condizioni e vincoli che aumentano il costo dell'elaborazione. La strategia di scelta degli oggetti/task deve essere, difatti, quella che è in relazione alla sequenza ottima che minimizza il makespan, il peso degli oggetti e i tempi di computazione.

Non si può usare prima la tecnica dello zaino e poi la tecnica del MST perchè si arriverebbe ad una soluzione non necessariamente la migliore in termini di schedulazione; per cui la soluzione migliore è di fare prima un algoritmo che restittuisca il makespan a cui si applica la tecnica dello zaino.

Supponiamo che ci siano n task che m macchine possono lavorare in parallelo, col vincolo di preemption, e che un task startato su una macchina può continuare su una macchina differente, a seguito di interruzione sulla macchina precedente.

Chiamiamo Cmax il tempo massimo di lavorazione in cui le m macchine devono completare gli n task:

Cmax = max(1<=j<=n) Cj

Mentre xij= frazione di task j lavorata sulla macchina i, col vincolo che Sum(i=1,m, xji) = 1 (Che esprime che una sola macchina per volta lavora un task: non è consentita la preemption). In particolare xji={0,1}.

Il tempo totale di lavoro della macchina i è: ki=Sum(j=1,n,pj*xji).

Riassumendo la formulazione in LP è:

min Cmax
Sum(j=1,n,pj*xji) <= Cmax
Sum(i=1,m, xij) = 1
xji>=0

E' vera la seguente affermazione: Sia x* una soluzione che soddisfa tutte le condizioni e vincoli, allora x* è la soluzione ottima.

Infatti rispetto a x* tutte le macchine hanno lo stesso carico e terminano in Cmax. Se x* non fosse la soluzione ottima e le macchine lavorassero con carico sbilanciato, significa che si potrebbe ridurre lo stesso il makespan ridistribuendo il lavoro sulle varie macchine il carico che era maggiore su una delle macchine. Ma questo ci riporterebbe a dire che x* non era ottimo ma che ne esiste un altro valore ottimo (ma che soprattutto non erano soddisfatte bene tutte le condizioni).

In particolare Cmax(x*) = 1/m * Sum(j=1,m,pj). Quindi siamo alla ricerca di un vettore x* delle variabili decisionali e una volta trovato x* si può passare a studiare il problema del sacco (knapsack).

Il problema, come già più volte evidenziato, può essere formulato nel seguente modo. Si hanno a disposizione n oggetti, ciascuno con valore vi e costo ci; nella fattispecie, tali parametri possono essere rivisti come tempo di processamento e peso. In questo caso il problema può essere espresso come massimizzazione del valore, nel rispetto della sequenza makespan e minimizzazione del peso, visto che dovranno essere effettuati diversi viaggi.

Se C è la disponibilità massima del trasporto, si avrà:

max F = Sum(i=1,n,vi*xi)
Sum(i=1,n,ci*xi)<=C con xi={0,1}

La programmazione dinamica si può espletare nel seguente modo:
- determinare il cammino e la lista di oggetti;
- implementare il makespan e determinare la sequenza di schedulazione;
- entrare nel labirinto e con la procedura di knapsack riempire il sacco, uscire ed avviare il processamento; mentre ciò avviene, rientrare nel labirinto e prelevare un altro sottoinsieme di oggetti fintantochè tutti gli oggetti non sono stati rimossi dal labirinto stesso.

Un'ulteriore complicazione può essere data dall'inserimento nel vincolo di rispetto della sequenza, e che negli intervalli di tempo in cui l'operatore sta asportando gli oggetti dal labirinto, almeno un processamento sia in atto; cioè l'insieme delle macchine non deve mai essere inoperoso. Chiaramente tale fatto complica notevolmente la soluzione del problema.

Per fissare i concetti di sopra vediamo però un esempio concreto in LP di una pianificazione di task e risorse umane, potrebbe essere anche un orario scolastico ad esempio.

Si possono risolvere problemi molto complessi (in questi ambiti basta poco per complicarli) e realizzare sistemi con Database Oracle, PL/SQL e con un motore risolutore GPLK. Nel seguito esamineremo un
problemino di schedulazione semplice.

Problemino di schedulazione
In un impianto di produzione di tutti i giorni un certo numero di personale è necessario. Il personale può essere essere assunto per un minimo fino ad un numero massimo di giorni consecutivi, richiede un numero minimo di giorni di ferie prima di poter essere nuovamente utilizzati. Il compito è di trovare
l'orario di lavoro riducendo al minimo salario totale da pagare.

Ecco come formuliamo il problemqa in CMLP:

# Personnel assignment problem
#
#


# workload (day, workload)
set L, dimen 2;

# workers (name, min workdays, max workdays, minimum leave, wage)
set W, dimen 5;

# names of workers
set V := setof{(v, b, c, d, e) in W} v;

# periods
set B := ( (min{(b,c) in L} b) .. (max{(b,c) in L} b) );

# minimum number of workdays in row
param ri{v in V} := min{(v, b, c, d, e) in W} b;

# maximum number of workdays in row
param ra{v in V} := min{(v, b, c, d, e) in W} c;

# minimum leave days in row
param ml{v in V} := min{(v, b, c, d, e) in W} d;

# wage
param wa{v in V} := min{(v, b, c, d, e) in W} e;

# work offer [worker, start, duration]
# (for large problems consider column generation to create work offers)
set O := setof{ v in V, s in B, d in {ri[v]..ra[v]}}( v, s, d);

# workday
param wd{b in B, (v, s, d) in O} :=
  if b < s then 0 else if b - s > d - 1 then 0 else 1;

# leaveday
param ld{b in B, (v, s, d) in O} :=
  if b < s + d then 0 else if b - s > d + ml[v] - 1 then 0 else 1;

# work offer used
var x{(v,s,d) in O}, binary;

# minimze total wage
minimize wage :
  sum{b in B, (v,s,d) in O} x[v,s,d] * wd[b,v,s,d] * wa[v];

# worker can do one job only
s.t. j1{b in B, v in V} :
  sum{(v,s,d) in O} x[v,s,d] * ( wd[b,v,s,d] + ld[b,v,s,d] ) <= 1;

# do all jobs
s.t. ja{b in B} :
  sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] >= sum{(b, w) in L} w;

solve;

# output solution
printf "\n%-10s", "Day";
for {v in V}
  printf "| %-10s", v;
printf "\n";
printf "%-10s", '----------';
for {v in V}
  printf "+-%-10s", '----------';
printf "\n";
for {b in B}
{
  printf "%9i ", b;
  for {v in V}
    printf "| %-9s ",
      if sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] then "working" 
      else "on leave";
  printf "\n";
}
printf "\n";

data;

# workload
set L := # day, workload
  ( 1, 3)
  ( 2, 1)
  ( 3, 1)
  ( 4, 1)
  ( 5, 1)
  ( 6, 2)
  ( 7, 2)
  ( 8, 2)
  ( 9, 3)
  (10, 2)
  (11, 2)
  (12, 2)
  (14, 1)
  (15, 2)
  (17, 3)
  (18, 3)
  (19, 2)
  (21, 3)
  (23, 1)
  (24, 3)
  (25, 3)
  (26, 3)
  (27, 2)
  (28, 1)
  (29, 1)
  (30, 2)
  (31, 1)
  (32, 3)
  (33, 2)
  (35, 3)
  (36, 3)
  (37, 1)
  (38, 3)
  (39, 2)
  (40, 3)
  (43, 1)
  (44, 1)
  (45, 2)
  (46, 2)
  (47, 3)
  (48, 2)
  (49, 1)
  (50, 2);

# workers
set W := # name, min workdays, max workdays, minimum leave, wage
  ( 'Anna',   5, 8, 2,  470 )
  ( 'Isabel', 5, 8, 2,  500 )
  ( 'Jack',   1, 8, 2, 1000 )
  ( 'John',   5, 8, 2,  600 )
  ( 'Lisa',   3, 5, 3,  640 );
end;

Ora eseguiamo il file scritto.

K:\Work\LP>glpsol --model workload.txt
Reading model section from workload.txt...
Reading data section from workload.txt...
147 lines were read
Generating wage...
Generating j1...
Generating ja...
Model has been successfully generated
ipp_basic_tech:  8 row(s) and 8 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 293 rows, 1142 columns, 13200 non-zeros
glp_intopt: 1142 integer columns, all of which are binary
Scaling...
 A: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 293
Solving LP relaxation...
      0: obj =  0.000000000e+000  infeas = 8.700e+001 (0)
*   100: obj =  8.699000000e+004  infeas = 0.000e+000 (0)
*   200: obj =  5.981000000e+004  infeas = 6.106e-016 (0)
*   338: obj =  5.253000000e+004  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   338: mip =     not found yet >=              -inf        (1; 0)
+   361: >>>>>  5.263000000e+004 >=  5.254000000e+004   0.2% (3; 0)
+   371: mip =  5.263000000e+004 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.2 secs
Memory used: 20.6 Mb (21554667 bytes)

Day       | Anna      | Isabel    | Jack      | John      | Lisa
----------+-----------+-----------+-----------+-----------+-----------
        1 | on leave  | working   | working   | on leave  | working
        2 | on leave  | working   | on leave  | on leave  | working
        3 | on leave  | working   | on leave  | on leave  | working
        4 | on leave  | working   | on leave  | on leave  | on leave
        5 | on leave  | working   | on leave  | on leave  | on leave
        6 | working   | working   | on leave  | on leave  | on leave
        7 | working   | working   | on leave  | on leave  | on leave
        8 | working   | on leave  | on leave  | working   | on leave
        9 | working   | on leave  | working   | working   | on leave
       10 | working   | on leave  | on leave  | working   | on leave
       11 | working   | on leave  | on leave  | working   | on leave
       12 | working   | on leave  | on leave  | working   | on leave
       13 | on leave  | on leave  | on leave  | on leave  | on leave
       14 | on leave  | working   | on leave  | on leave  | on leave
       15 | working   | working   | on leave  | on leave  | on leave
       16 | working   | working   | on leave  | on leave  | on leave
       17 | working   | working   | on leave  | on leave  | working
       18 | working   | working   | on leave  | on leave  | working
       19 | working   | on leave  | on leave  | on leave  | working
       20 | working   | on leave  | on leave  | on leave  | on leave
       21 | working   | working   | working   | on leave  | on leave
       22 | on leave  | working   | on leave  | on leave  | on leave
       23 | on leave  | working   | on leave  | on leave  | on leave
       24 | working   | working   | on leave  | on leave  | working
       25 | working   | working   | on leave  | on leave  | working
       26 | working   | working   | on leave  | on leave  | working
       27 | working   | working   | on leave  | on leave  | on leave
       28 | working   | on leave  | on leave  | on leave  | on leave
       29 | working   | on leave  | on leave  | on leave  | on leave
       30 | working   | on leave  | on leave  | on leave  | working
       31 | on leave  | on leave  | on leave  | on leave  | working
       32 | on leave  | working   | on leave  | working   | working
       33 | on leave  | working   | on leave  | working   | on leave
       34 | on leave  | working   | on leave  | working   | on leave
       35 | working   | working   | on leave  | working   | on leave
       36 | working   | working   | on leave  | working   | on leave
       37 | working   | working   | on leave  | on leave  | on leave
       38 | working   | working   | on leave  | on leave  | working
       39 | working   | on leave  | on leave  | on leave  | working
       40 | working   | on leave  | working   | on leave  | working
       41 | on leave  | on leave  | on leave  | on leave  | on leave
       42 | on leave  | on leave  | on leave  | on leave  | on leave
       43 | working   | on leave  | on leave  | on leave  | on leave
       44 | working   | on leave  | on leave  | on leave  | on leave
       45 | working   | on leave  | on leave  | on leave  | working
       46 | working   | on leave  | on leave  | on leave  | working
       47 | working   | working   | on leave  | on leave  | working
       48 | working   | working   | on leave  | on leave  | on leave
       49 | on leave  | working   | on leave  | on leave  | on leave
       50 | on leave  | working   | on leave  | working   | on leave

Model has been successfully processed

Un consiglio. E' ovvio che lo strumento vi calcola il tutto in base ai dati che gli avete fornito e funziona benissimo quando la durata del tempo è ben fissata da regole, come nell'organizzazione di orari, turni etc.

Mentre nelle pianificazioni di lavori come realizzazione di un software,  molto della pianificazione dipende da voi nel saper ben valutare il tempo, le persone disponibili e l'organizzazione e professionalità necessarie per svolgere un task, etc. Per questo vi affiderete a statistiche che avete raccolto nel tempo nell'effettuare quel lavoro o a metodologie specifiche o a regolamentazioni previste per quel lavoro.

Alla prox

Un sacco di mal di testa: Il problema dello zaino (Knapsack)

Il problema dello zaino è uno dei “21 problemi NP-completi della lista di Karp”. Esso si può formulare nel seguente modo: sia N, il numero totale di oggetti xi, sia wi il peso del singolo oggetto xi, ci il valore del singolo oggetto xi e W il peso totale sopportabile dallo zaino.

La funzione obiettivo da massimizzare è in tal caso, considerando xi=1 se si inserisce nello zaino o 0 in caso
contrario:  maxZ=Sum{i=1..N}c_{i}*x_{i} mentre il vincolo impone che:sum_{i=1..N} x_{i}*w_{i} <= W

In sostanza maxZ è il massimo valore ottenibile come oggetti che posso mettere nello zaino, non necessariamente N, ma nello stesso tempo il massimo numero di oggetti è limitato dal massimo peso trasportabile.

Ovviamente il problema dello zaino è isomorfo ad altri problemi simili, anzicchè dello zaino potrebbe essere la stiva di un aereo, o di una barca etc. e il valore ed il peso possono avere un differente significato, ma trattabile allo stesso modo matematicamente.

A seconda dei valori assunti da xi il problema è classificato in modalità diversa. Se xi={0,1} allora si definisce
“problema dello zaino binario o 0-1”; se xi <= bi si definisce “problema dello zaino con limiti” ed infine se
xi appartiene a N e per ogni i appartenente a N con i>0 allora si parla di “problema dello zaino senza limiti”.

Esso è risolvibile attraverso una “programmazione dinamica”, termine non finalizzato ad un fine informatico, ma entrato in uso negli anni Quaranta ad indicare la suddivisione in sottoproblemi e strutture ottimali. Sulla strada del “Subset-sum” furno ideate anche tecniche crittografiche a chiave pubblica, come quella Markle-Hellman successivamente abbandonata poichè facilmente risolvibile con algoritmi lineari.

Facciamo un esempio, Nella tabella successiva abbiamo 9 possibili oggetti, con peso e valore, che potremmo mettere nello zaino tenendo presente che il massimo peso trasportabile è W=27Kg :

Oggetto    Peso (kg)    Valore (euro)    Valore/Peso
x1               10                    200            20
x2               12                    225            18,75
x3               15                    250            16,67
x4                 9                    150            16,67
x5                 7                    125            17,86
x6                 6                    125            20,83
x7                 6                    120            20
x8                 6                    120            20
x9                 4                      75            18,75

Esistono varie strategie algoritmiche euristiche e di rilassamento che per la sua soluzione non richiede molto tempo, ad esempio con tecnica “Branch e bound” in ambito della Linear Programming e dovuto a A.H. Land e A.G.Doig nel 1960. Tale tecnica è una enumerazione implicita cioè prova a enumerare tutte le possibilità, individuando quella ottima o quella possibile, scartando le altre.

L'algoritmo Greedy di tipo euristico è dovuto, invece, a Martello e Toth (1990). Esso ordina gli oggetti in ordine decrescente di peso, per inserirli nello zaino fino all'esaurimento dello spazio disponibile. Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo Greedy garantisce che ne siano inseriti nello zaino almeno k/2.

Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire ci/wi ed inserirli in ordine decrescente (euristica CUD). Questi algoritmi essendo euristici non garantiscono l'ottimalità della soluzione ma sono in grado di fornire una "buona" soluzione in tempo ragionevole. Possiamo usare GnuWin32 (gplsol), scrivendo un file in formato GMPL oppure LP; ma se volessimo adottare strategie senza “aiuti software” potremmo avere diverse soluzioni (esaminiamo il problema dello zaino binario):

• Soluzione 1: prendo gli oggetti più pesanti che non superano i 27 kg: ad esempio x2+x3 che mi danno 27 kg ed un valore di 475 euro

• Soluzione 2: prendo gli oggetti più leggeri per aumentarne il numero ad esempio x6+x7+x8+x9 in questo caso si ottiene 22Kg ed un valore di 530 euro (meno peso e maggior valore).

• Soluzione 3: prendo gli oggetti di maggiore valore in base al rapporto valore/peso x1+x6+x7+x9 ovvero 26kg e 520 euro

• Soluzione 4: raggiungo i 27 kg con gli oggetti di maggiore valore x1+x5+x6+x9 ovvero 27Kg e 525 euro

La soluzione 4, come si vede, massimizza la funzione del valore. In questo caso erano poche le variabili in gioco ma se fossero state molte sarebbe stato necessario l'”aiuto software”.

OK, vi do la formulazione del problema di sopra in formato GMPL da risolvere con GLPSOL.

Eccola:

# This file shows how to model a knapsack problem in GMPL.

# Size of knapsack
param c;

# Items: index, size, profit
set I, dimen 3;

# Indices
set J := setof{(i,s,p) in I} i;

# Assignment
var a{J}, binary;

maximize obj :
  sum{(i,s,p) in I} p*a[i];

s.t. size :
  sum{(i,s,p) in I} s*a[i] <= c;

solve;

printf "The knapsack contains:\n";
printf {(i,s,p) in I: a[i] == 1} " %i", i;
printf "\n";

data;

# Size of the knapsack
param c := 27;

# Items: index, size, profit
set I :=
  1 10 200
  2 12 225
  3 15 250
  4  9 150
  5  7 125
  6  6 125
  7  6 120
  8  6 120
  9  4  75;

end;

Ora che avete il file knapsack.txt lanciate il comando:

glpsol --model knapsack.txt

e otterrete l'output:

K:\Work\LP>glpsol --model knapsack.txt
Reading model section from knapsack.txt...
Reading data section from knapsack.txt...
44 lines were read
Generating obj...
Generating size...
Model has been successfully generated
ipp_basic_tech:  1 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 1 row, 9 columns, 9 non-zeros
glp_intopt: 9 integer columns, all of which are binary
Scaling...
 A: min|aij| = 4.000e+000  max|aij| = 1.500e+001  ratio = 3.750e+000
GM: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
EQ: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
2N: min|aij| = 7.500e-001  max|aij| = 1.250e+000  ratio = 1.667e+000
Crashing...
Size of triangular part = 1
Solving LP relaxation...
      0: obj =  5.400000000e+002  infeas = 1.360e+001 (0)
*     2: obj =  3.500000000e+002  infeas = 0.000e+000 (0)
*     8: obj =  5.450000000e+002  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     8: mip =     not found yet <=              +inf        (1; 0)
+    15: >>>>>  5.150000000e+002 <=  5.350000000e+002   3.9% (4; 0)
+    25: >>>>>  5.200000000e+002 <=  5.350000000e+002   2.9% (6; 4)
+    29: >>>>>  5.250000000e+002 <=  5.250000000e+002   0.0% (1; 11)
+    29: mip =  5.250000000e+002 <=     tree is empty   0.0% (0; 17)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.1 Mb (155039 bytes)
The knapsack contains:
 1 5 6 9
Model has been successfully processed

Alla prox

Problemi matematici minori ?

In Matematica esistono innumerevoli problemi, apparentemente minori, nel senso che non sono direttamente classificati tra i "problemi del Millennio"; ma che tuttavia se risolti avrebbero un impatto tecnologico notevole nella vita odierna.

Soprattutto permetterebbero pianificazioni ed uso di risorse in modo mirato e a minor costo. 

Non solo ma risolvendo un problema, si risolverebbero problemi "isomorfi in altri contesti".

Per farvi comprendere di che si tratta pensate a: traffico aereo, percorsi idrici, gas, fognature in una città, distensione dei cavi e delle fibre ottiche, creazione di circuiti integrati con aggiunta di nuovi nodi o vertici, ma anche nelle trasmissioni audio, video, etc. 

Avete mai fatto delle audio col numero verde 800 dove si collegano e si scollegano varie persone? Ebbene un sistema efficiente deve ricalcolare ogni volta l'albero di Steiner più efficace per poter riequilibrare QoS (Quality of Service) e percorsi di minor costo o banda.

In poche parole si tratta del “problema di Steiner”. Per introdurvi al problema immaginate di avere un grafo G di cui inizialmente avete solo i nodi (i vertici) V e volete creare un albero (albero di Steiner) col numero minimo di collegamenti pesati. 

Chiariamo subito che  per “pesati” occorre immaginare un costo che può essere, ad esempio, in un’audio telefonica il tempo di trasmissione o di ritardo e la qualità del segnale QoS; mentre per albero intendiamo dei collegamenti senza percorsi chiusi (no ad anelli o a circuiti). Ad esempio con quattro vertici colleghiamo solo 3 lati di un quadrato (l'ultimo lato non lo disegniamo).

Se il grafo fosse statico cioè con vertici fissi, l’algoritmo ottimizzato di Kruskal risolverebbe benissimo la cosa; ma se c’è una dinamicità nel tempo dei vertici n=|V|, allora la cosa si complica di parecchio (anche se è risolvibile ma non in maniera ottimale assoluta). 

La tecnica dell'algoritmo di Kruskal con vertici statici è semplice. Immaginiamo di avere di ogni coppia di vertici il costo e ordiniamoli dal costo più basso al costo più alto. A questo punto colleghiamo (senza creare percorsi chiusi altrimenti non avremo un albero) i nodi a costo minore, via via arrivando a quelli di costo maggiore e ci arrestiamo se abbiamo collegato già tutti i vertici statici. 

Siamo, quindi, nella teoria dei grafi, quella iniziata nel Settecento con Eulero e il problema dei ponti di Konigsberg.

Nel problema di Steiner l'obiettivo è di cercare, ad ogni variazione del numero di vertici(aggiunta o rimozione) , l’albero dei collegamenti minimi che ottimizza le risorse (i costi) che variano nel tempo. 

Pensate alla banda di trasmissione e il QoS che deve essere rispettato all'aumentare dei nodi che si collegano o alla variazione delle località dei nodi.

E’ dimostrato che il problema di Steiner è NP-completo; per cui il problema di Steiner rientra 'indirettamente' nel "problema del millennio P=NP".

A questa famiglia ne appartengono molti : il problema dello zaino o sacco da viaggio, del commesso viaggiatore, il problema di Steiner, il problemino dell'individuare il maggior numero di mopnetine di ogni taglio disponibile per pagare un conto, la fattorizzazione del RSA, il logaritmo discreto etc. 

Come tutti i problemi NP-completi,  non riuscendo a trovare un algoritmo deterministico polinomiale si cerca di trovare almeno non l’ "ottimo in assoluto" ma il "miglior ottimo disponibile" con tecniche euristiche o altre. Il che non significa che non esiste una soluzione, anzi la soluzione esiste ma è di tipo esponenziale rispetto ai dati di input e, quindi, poco efficiente.

Sono nati,a tal proposito, molto algoritmi a risoluzione del problema; ad esempio troviamo tra:

Algoritmi ottimi

• Spanning Tree Enumeration Algorithm (STEA)
• Dynamic Programming Algorithm (DPA)

Euristiche per il problema di Steiner

• Pruned Dijkstra Heuristic (PDH)
• Distance Network Heuristic (DNH)
• Shortest Path Heuristic (SPH)
• Kruskal based – Shortest Path Heuristic (K-SPH)
• Repetitive Shortest Path Heuristics
• Average Distance Heuristic (ADH)

Tecniche di Post-processing

Ma esistono anche tanti altri SAT, 3SAT etc.

Come in tutte le discipline ingegneristiche, dove non esiste una soluzione ottima assoluta, allora ognuno degli algoritmi trovati è forte in un "certo range di quantità", per cui anche quelli di cui parlavo prima hanno una efficienza che li avvantaggia o li svantaggia all’aumentare del numero di vertici. Spesso un software di gestione delle risorse dispone più algoritmi, che sceglie in base alla quantità di vertici in cui si ritrova.

OK, starete già su Wikipedia a vedere la corretta definizione del problema. Bravi! Si inizia da lì, altrimenti vi ritrovereste a risolvere un problema mal definito e vi illudereste di aver trovato la soluzione!

Esistono anche varie versioni del problema di Steiner:

• problema di Steiner nelle reti (la versione generale che interessa)
• problema di Steiner rettilineo: la topologia è data dal piano R^2 con la metrica indotta dalla 'distanza Manhattan';
• problema di Steiner euclideo: anche in questo caso la topologia è data dal piano R^2, con la metrica indotta dalla distanza euclidea;

Il problema che interessa dovrebbe esser formulato come segue:

"Data una rete connessa e non diretta G = (V, E, w), w : E -> R, e un insieme Z sottoinsieme di V,trovare il sottografo connesso Gs = (Vs, Es, w) di G tale che:
a) Z sottoinsieme di Vs (strettamente incluso o incluso in Vs);
b) w(Gs) = Sum(i,j,w(i,j)) sia minimo con i,j appartenenti a Es".


L’insieme Z è detto, con riferimento al problema trattato, 'insieme di multicast'; mentre l’insieme Vs – Z viene denotato con S ed è costituito dai 'nodi di Steiner'.


Se la funzione di costo w(i, j) degli archi assume sempre valori positivi il sottografo soluzione è un albero, detto 'albero di Steiner', che verrà indicato nel seguito con Tz. Si pone inoltre n = |V|, m = |E|, p = |Z|, s = |S|.Alcuni casi limite del problema di Steiner però ricadono in problemi ben noti della teoria dei grafi:

• p = 2: si tratta di trovare il percorso più breve che connetta i due nodi dell’insieme Z; il problema viene risolto dall’algoritmo di Dijkstra, che restituisce un albero di cammini minimi da un nodo verso tutti gli altri nodi della rete;

• p = n, cioè Z = V: si tratta di calcolare il minimum spanning tree o MST del grafo dato;in questo caso il problema viene risolto dall’algoritmo di Prim o dalla variante di Kruskal.

La valutazione della qualità degli algoritmi di questo genere di solito avviene su due fattori di merito:

• la competitività di costo, intesa come bontà della soluzione trovata Th (l'albero di STeiner trovato) rispetto a quella ottima Tz e in formule : 

                        ch = w(Th)/w(Tz)

• la complessità computazionale, in notazione O(f(n))

Molti altri problemi sono importanti per l'industria alimentare come quello dell'impacchettamento (pensate al problema dell'impacchettamento delle sfere di Keplero) o della realizzazione di scatole al minor costo e con determinate qualità.

Pensate alle buste del latte o ai nuovi contenitori ideati i cosiddetti 'tetrapack' o anche a mobili in alluminio/acciao o a macchine per catene di montaggio; ma ne parleremo la prossima volta. Aggiungo solo una nota di colore: Steiner era svizzero e la sua cultura era autodidatta. Imparò a leggere e scrivere a 14 anni e si dimostrò un genio matematico tale da insegnare a 20 anni.



Ma soprattutto era uno genio della geometria: molti teoremi li dimostrava visivamente, grazie alla geometria, come la dimostrazione del "problema di Didone" e del "problema isoperimetrico".

Alla prox

Programmazione lineare

Esiste una categoria di problemi di matematica che rientrano nella Linear Programming (LP) o anche programmi interi misti (MIPS). In questi problemi l'obiettivo è di massimizzare o minimizzare una risorsa (funzione obiettivo), che è soggetta a dei vincoli.

Con queste tecniche si possono risolvere problemi come quello del commesso viaggiatore, il SUDOKU, tecniche bancarie etc.

Molti di questi problemi possono risolversi sia graficamente che con strumenti di calcolo usando, nel caso LP, il metodo del simplex (vedi Wikipedia), del punto intermedio (primal-dual interior point); mentre nel caso MIPS tecniche come "Branch and bound".

Spesso un problema di massimizzazione è anche affrontabile come una minimizzazione al contrario.

La tecnica grafica, che deve essere altrettanto dominata, va bene se il problema ha poche dimensioni in gioco; appena il numero di dimensioni diventano moltissime, serve uno strumento automatico che risolvi il problema.

Molti di questi problemi sono isomorfi, nel senso che capito come si risolve uno di essi, tutti gli altri problemi, anche se con descrizione diversa, possono essere ricondotti ad una tale tecnica.

Un sito proposto per gli approfondimenti è http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html


Esempio
Supponiamo che la Fargo è una società che produce barattoli di pittura bianca, gialla, nera e rossa. Per
fare queste pitture la Fargo usa tre materiali grezzi: 40 litri di olio, 25 litri di solvente e 20 litri di pigmenti.

Per fare il bianco si spendono 12 euro, con 0.8 litri di pigmento, 0.4 di solvente e 0.5 di olio.
Per fare il giallo si spendono 8 euro, con 0.5 litri di pigmento, 0.2 di solvente e 0.7 di olio.
Per fare il nero si spendono 9 euro, con 0.2 litri di pigmento, 0.5 litri di solvente, 0.6 di olio.
Per fare il rosso si spendono 11 euro, con 0.3 litri di pigmento, 0.6 litri di solvente e 0.4 litri di olio.

L'obiettivo è di massimizzare il profitto della Fargo.

Si possono usare molti strumenti: alcuni professionali (LINDO etc) ed altri open source (GNUWin32 con GLPSOL). Noi useremo GNUWin32 nel seguito per l'esempio didattico (http://www.gnu.org/software/glpk).

Installiamo GNUWin32 e inseriamo nel PATH di windows il percorso fino alla directory bin.

Il primo passo è formalizzare il problema. Esistono molti formati per farlo (GMPL, LP etc).

Nel seguito useremo il formato più intuitivo LP per la formalizzazione algebrica, poi successivamente quello GMPL.

Scriviamo con Notepad un file Fargo.txt del tipo:

\\ Problem Fargo.txt - LP format

Maximize
    obj: 12 x1 + 8 x2 + 9 x3 + 11 x4
   
Subject to
    c1:    .8 x1 + .5 x2 + .2 x3 + .3 x4 <= 20
    c2:    .4 x1 + .2 x2 + .5 x3 + .6 x4 <= 25
    c3:    .5 x1 + .7 x2 + .6 x3 + .4 x4 <= 40
End   
   
Da DOS sotto Windows (comando cmd) ci posizioniamo nella directory del file Fargo.txt.

Proviamo prima l'help per vedere se l'installazione funziona:  glpsol --help

Adesso dobbiamo istruire GLPSOL che abbiamo un file in formato LP:
glpsol --cpxlp fargo.txt --output fargo.out

e otterrete la soluzione a video e sul file di output fargo.out. Se c'è la scritta OPTIMAL SOLUTIONS FOUND, significa che ha trovato anche la soluzione ottimale.

L'output si presenta come segue
Problem:   
Rows:       3
Columns:    4
Non-zeros:  12
Status:     OPTIMAL
Objective:  obj = 553.7037037 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 c1           NU            20                          20       9.25926
     2 c2           NU            25                          25        12.963
     3 c3           NU            40                          40       1.11111

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                    -1.14815
     2 x2           B        23.4568             0              
     3 x3           B        37.6543             0              
     4 x4           B        2.46914             0              

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 1.48e-015 on row 2
        max.rel.err. = 5.68e-017 on row 2
        High quality

KKT.PB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

KKT.DE: max.abs.err. = 8.68e-016 on column 4
        max.rel.err. = 7.24e-017 on column 4
        High quality

KKT.DB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

End of output


Potreste usare anche le opzioni:
glpsol --cpxlp fargo.txt --output fargo.out --bound fargo.bnd

In questo modo otterrete anche un file di spiegazione. Il vantaggio di GLPK è che è open source e fornisce non solo il tool GLPSOL per la risoluzione interattiva di problemi, ma anche API per linguaggio C/C++.

In formato GMPL occorre scrivere prima il file modello fargo.gmpl:

# FARGO’S PRODUCTION PLANNING MODEL
# MODEL file
set R; /* resources */
set P; /* paint products */
param b{r in R}; /* on-hand levels of paint resources (in liters) */
param c{p in P}; /* profit contribution (per liter of paint) */
param a{p in P, r in R}; /* amount of resource consumed from producing paint */
var x{p in P} >= 0; /* amount of paint p to be produced */
s.t. rc{r in R}: sum{p in P} a[p,r] * x[p] <= b[r];
/* resource capacity */
maximize profit: sum{p in P} c[p] * x[p];
/* total profit (dollars) */
end;

poi va scritto il file dati fargo.data:

data;
set R := Pigment Solvent Oil;
set P := PaintA PaintB PaintC PaintD;
param : b :=
Pigment 20 /* liters */
Solvent 25 /* liters */
Oil 40 /* liters */ ;
param : c :=
PaintA 12 /* euros */
PaintB 8 /* euros */
PaintC 9 /* euros */
PaintD 11 /* euros */ ;
param a : PaintA PaintB PaintC PaintD :=
Pigment 0.8 0.5 0.2 0.3
Solvent 0.4 0.2 0.5 0.6
Oil 0.5 0.7 0.6 0.4 ;
end;

I comandi dovranno usare questa volta le opzioni --model e --data

Per una introduzione teorica dei problemi LP vi segnalo il pdf "Linear Programming
A Concise Introduction - Thomas S. Ferguson" che potrete scaricare da internet.

Alla prox