|
Ottimizzazione del trasporto con tecniche algebrico-geometriche.
La programmazione intera è una tecnica
matematica che permette di formulare delle decisioni su come risorse limitate
di natura qualsiasi devono essere ripartite tra concorrenti in modo che ne
risulti il migliore utilizzo; in particolare si prefigge di risolvere
speciali problemi nei quali intervengono variabili o parametri a numeri
interi; ad esempio problemi di investimento di capitale, o i cosiddetti
problemi di trasporto. Questi ultimi vengono concretizzati nel seguente modo:
la rete è composta da i, con i=1, ... , s, punti di produzione detti origini,
con quantità relative prodotte ai
(o con aik se si tiene anche conto del tempo;
per es.nell'anno k o nel mese k) e da j, con j=1, ... , t, punti di consumo,
detti destinazioni con quantità relative richieste bj (bjk). Il costo del
trasporto dal generico centro di produzione i-esimo al generico punto di
consumo j-esimo è indicato con wij (wijk). Occorre
determinare il livello ottimale di trasporti xij (xijk),
ovvero la quantità che si deve trasportare dall'origine i alla destinazione j
(nel tempo k), affinché tutte le produzioni giungano a destinazione e siano
tali da minimizzare i costi dell'operazione.
La generica formulazione di un problema di programmazione intera è la
seguente:
Data una matrice A ad entrate intere, un vettore b a
coordinate intere, ed un vettore costo reale w, decidere se il sistema
lineare Ax = b ammette qualche soluzione intera positiva ed, in
caso affermativo, trovare quella che minimizza il prodotto scalare con w.
Classicamente, uno degli algoritmi più noti per risolvere problemi di questo
tipo è il metodo del “cutting plane” di Gomory (“Outline of an algorithm for integer
solutions to linear programs”, Bulletin of the AMS 64, (1958), 275 -
278) che essenzialmente utilizza il famoso “metodo del simplesso”
di Dantzig (“Activity Analysis of Production and Allocation”,
Wiley (New York 1951)) per la programmazione lineare. Tuttavia, mentre la
programmazione lineare può essere risolta in tempo polinomiale, è ben
noto che il problema generale di programmazione intera è NP-completo. Questo
fatto giustifica la ricerca di algoritmi che, in casi particolari, siano più
efficienti di quelli tradizionali.
I primi a proporre algoritmi che utilizzano modelli e tecniche
algebrico-geometriche per risolvere problemi di programmazione intera, sono
stati Conti e Traverso, (“Buchberger algorithm and integer
programming”, proceedings AAECC-9 539,
Lectures Notes in Comp.Sci., (1991), 130 - 139). Tali metodi sono stati
ripresi e continuamente migliorati in una serie di lavori di vari autori, fra
i quali Sturmfels (“Gröbner bases and convex polytopes”,
University Lecture Series (Providence, R.I.) American Mathematical Society 8, (1998)), Thomas
(“Applications to Computational Algebraic Geometry”, Proceedings
of Symposia in Applied Mathematics 53,cap.
“Applications to Integer Programming” (1998)), Weismantel
(“TestSets of Integer programming”, Mathematical Methods of
Operations Research 47, (1998),
1-37), Thomas e Weismantel (“Truncated Gröbner bases for integer
programming”, Applicable
Algebra in Engineering, Communication and Computing 8 (1997), 241-257),
Urbaniak, Weismantel e Ziegler (“A variant of Buchberger’s
Algorithm for integer programming”, SIAM J. On Discrete Mathematics,
Vol 1, 10 (1997), 96-108),
Bigatti, LaScala e Robbiano (“Computing toric ideals”, Journal of
Symbolic Computation 27, (1999),
351--365), Hemmecke (“Computation of Hilbert bases, Graver
bases, toric Groebner bases, and more”. Software freely
available at http://www.4ti2.de/).
Test computazionali mostrano, tuttavia, che gli algoritmi prodotti con queste
tecniche lavorano bene per risolvere problemi di “limitate
dimensioni” , mentre non sono molto efficienti per risolvere problemi
piu’ complessi come, ad esempio, concreti problemi di trasporto
tridimensionali o problemi di campionatura.
Alcune simulazioni al computer svolte a Trieste nell’ambito di un lungo
seminario su queste problematiche (autunnno ‘97 – primavera
’99) hanno mostrato che una combinazione fra le tecniche succitate,
metodi di geometria poliedrale e tecniche tipiche della teoria delle matrici
multi dimensionali, puo` efficacemente essere utilizzata per migliorare
ulteriormente le performances degli algoritmi in modo da renderli idonei a
risolvere anche problemi di ”grosse dimensioni”.
Negli articoli “Gröbner bases related to 3-dimensional transportation
problems”, Quaderni matematici Univ. Trieste, II, 482 (2000) e
"Lexicographic Gröbner bases of 3-dimensional transportation
problems", Symbolic computation: solving equations in algebra, geometry,
and engineering (South Hadley,
MA, 2000), 145 -168,
Contemp. Math. 286, Amer.
Math.Soc., Providence, RI, (2001),
scritti in collaborazione con G. Boffi, sviluppiamo l'idea di
descrivere le basi di Gröbner necessarie alla risoluzione dei problemi di
trasporto tridimensionale mediante opportuni cicli su grafi nel tentativo di
evitare, in tale modo, l'uso dell'algoritmo di Buchberger per il loro
calcolo. In tali articoli si e` preso essenzialmente in esame il caso 3x3x3
ma, dopo ulteriori esperimenti computazionali fatti a Genova nell'estate 2002
utilizzando il prototipo di CoCoA 4.2 e con il determinante aiuto di Anna
Bigatti, siamo stati in grado di provare che la base di Gröbner ridotta lessicografica
per i casi rx3x3 si "stabilizza" per r=5. Cioe' da 6x3x3
all'infinito, non appaiono binomi nuovi ma solamente quelli calcolati fino a
5 "distribuendo i primi indici su tutti i posti disponibili". Per
esempio, se in un binomio per r=5 nel termine di testa (e quindi in quello di
coda) compaiono come primi indici 1,2,3,4,5 allora questo da origine a 6
binomi diversi nella base ridotta lessicografica di 6x3x3 con primi indici
rispettivamente 1,2,3,4,5; 1,2,3,4,6; 1,2,3,5,6; 1,2,4,5,6; 1,3,4,5,6; 2,3,4,5,6
e secondi e terzi indici sempre "uguali" ( nel senso che se nella
prima pentupla compare (x_213)^4, allora esso compare nella seconda, nella
terza e nella quarta, mentre nella quinta e nella sesta compare (x_313)^4).
Tali risultati sono contenuti nell’articolo “Lexicographic
Gröbner bases for transportation problems of format rx3x3”, febbraio
2003, in corso di stampa sul Journal of Symbolic Computation e si capiscono
molto bene utilizzando le tecniche sui grafi ivi sviluppate ed, in
particolare il concetto di “RG-sequenza”. Nel marzo 2003, Santos e Sturmfels (“Higher Lawrence
configurations”, Journal of Combinatorial Theory, Ser. A 103, (2003), 151-164) mostrano che una simile proprietà di stabilità
vale per la base di Graver di ogni formato rxsxt con s e t fissi. Poiché la
base di Graver contiene la base universale di Gröbner e quindi tutte le basi
ridotte di Gröbner per ogni termorder, è ora chiaro che ogni base ridotta di
Gröbner si stabilizza. Rimane aperto
il problema di vedere qual è il “minimo indice di
stabilizzazione” (msti) nei casi rx3x3 per termorders diversi dal
lessicografico (per il quale è 5) e nel caso generale di rxsxt. Per quanto
riguarda i casi rx3x3, sappiamo da Aoki e Takemura (“Minimal basis for
connected Markov chain over 3x3xK contingency tables with fixed
two-dimensional marginals”, Australian and New Zealand Journal of
Statistics, l45, (2003), 229
– 249) che tale indice è maggiore o uguale a 5 e da Santos e Sturmfels
(op. cit.) che è minore o uguale a 9. Un primo approccio
“sperimentale” potrebbe
essere quello di calcolare la base ridotta di Gröbner nel caso 9x3x3 per
qualche termorder diverso dal lessicografico (cosa attualmente quasi
impossibile da gestire) e da tale calcolo trarre qualche informazione; da un
punto di vista più teorico, sarebbe interessante vedere come si
“deformano” le RG-sequenze al variare del termorder. Per ciò che concerne il caso generale rxsxt
con s e t fissi, attualmente non sembra esserci alcun
feeling. Notiamo che la conoscenza del msti nei vari termorders risulta
particolarmente utile perché permette di ottenere degli algoritmi puramente
combinatori (e quindi molto efficienti) per il calcolo delle varie basi di
Gröbner ridotte (per i casi lessicografici di tipo rx3x3 tale algoritmo è
ancora da implementare ma se ne può dedurre facilmente la sua architettura
dal nostro succitato articolo del 2003). Un altro interessante problema è
quello di esplorare la possibilita` di estendere i risultati ottenuti per il
trasporto tridimensionale alle basi di Gröbner che modellano problemi di
campionamento pluridimensionale (cfr. Sturmfels, “Gröbner Bases and Convex Polytopes”,
University Lecture Series, 8,
(1995) , AMS, Providence, RI).
Un altro recente approccio a queste
problematiche e` quello che si fonda
sul calcolo dell' ideale di deformazione di un sistema di equazioni
differenziali ipergiometriche di Gel'fand,Kapranov e Zelevinsky (Saito,Sturmfels,
Takayama, “Gröbner deformations of hypergeometric differential
equations”, Algorithms and computation in mathematics , 6, Springer (1999)). Tale approccio,
che richiede l'uso di tecniche tipiche della teoria delle algebre di Weyl,
sembra molto stimolante soprattutto in connessione con problemi di
campionamento pluridimensionale.
Per maggiori informazioni sulla programmazione
intera e problemi collegati, visitare il sito
“testsets”.
|
|
Applicazioni dell'algebra computazionale alla Biometria.
La biometria si occupa di metodi automatici per
il riconoscimento di una persona a partire dai suoi caratteri fisiologici
(impronte digitali,volto, voce, etc.) o comportamentali (firma). Si tratta di
metodi oggi molto richiesti al fine di combattere le violazioni della
sicurezza e le transazioni fraudolente. Il cuore di un metodo biometrico è il
confronto tra un'informazione codificata archiviata e una acquisita al
momento (ad es., durante un prelievo al bancomat). Si tratta d'un triplice
processo di raccolta-elaborazione-acquisizione, seguito da una fase
d’identificazione oppure di verifica della identità. La raccolta del
dato biometrico grezzo avviene mediante un apparecchio (ad es. un microfono).
L’elaborazione consiste nell’estrazione dal dato grezzo dell'informazione
rilevante e nella sua codifica. L'informazione codificata (da cui non è
possibile risalire all'integrità del dato grezzo) è quindi acquisita su un
opportuno supporto. Il confronto vero e proprio può essere di due tipi. Nel
caso della verifica d'identità, si confronta l'informazione nuova con quella
disponibile in archivio, per rispondere al quesito: Sei davvero la persona
che dici di essere? Nel caso dell’identificazione, si confronta
l'informazione nuova con un insieme di informazioni disponibili in archivio,
per rispondere al quesito: Chi sei? Alcuni dei più comuni metodi biometrici
d'identificazione riguardano l'analisi della retina, l'analisi del volto, il
controllo della firma, la geometria della mano, il riconoscimento della voce
e la verifica delle impronte digitali.
Si ritiene di potere realisticamente affrontare uno di questi metodi e
precisamente la verifica delle impronte digitali, che è anche uno dei più
semplici e meno costosi. Si spera poi di poter estendere lo stesso approccio
all'analisi della retina. L'approccio con cui si intende studiare la verifica
delle impronte digitali è quello del confronto dell'insieme delle minuzie. Le
minuzie di una impronta digitale sono quei punti che si trovano alla fine di
una cresta, oppure ad una biforcazione.E' comunemente ammesso che
l'uguaglianza dell'insieme delle minuzie sia sufficiente evidenza per
l'uguaglianza dell'impronta digitale. Ci si riduce pertanto a un problema di
confronto tra due insiemi di punti, ovvero (fissato un sistema di
riferimento) di insiemi di coppie di numeri. Se la posizione del polpastrello
fosse assolutamente identica in tutti i rilievi, i due insiemi risulterebbero
identici. Ma in pratica il polpastrello può essere traslato, ruotato, premuto
di più o di meno. Ci si domanda allora se esiste un cambiamento di
riferimento affine del piano che porti un insieme di minuzie nell'altro.
Strumenti di algebra computazionale più o meno ben noti paiono consentire di
dare una risposta al quesito (senza calcolare esplicitamente il cambiamento
di riferimento) e di implementare un algoritmo utile nella pratica. Un primo tentativo in tale direzione è
presentato nell'articolo “Computer Algebra for Fingerprint
Matching”, Lecture Notes in Computer Science, Vol. 2657, (2003), 811 –
820 (in collaborazione con S.Bistarelli e G.Boffi), nel quale illustriamo un
prototipo di algoritmo che, con metodologie algebrico-geometriche
computazionali, teoricamente risolve il precedente problema. Sfortunatamente
una prima implementazione (in un linguaggio di “alto livello”) di
detto algoritmo mostra, nei test eseguiti, una lentezza esecutiva tale da non
renderlo competitivo nella pratica. Stiamo ora studiando un sensibile
miglioramento dell’algoritmo (di complessità notevolmente più bassa e
parallelizzabile) che dovrebbe migliorarne sensibilmente le prestazioni.
Cenni bibliografici
- H. Cummins and C. Midlo, Finger Prints, Palms and
Soles,Dover 1961.
- A. K. Jain, R. Bolle and S. Pankanti (Eds.), Biometrics:Personal
Identification in Networked Society, Kluwer1999.
- H. C. Lee and R. E. Gaensslen, Advances in Fingerprint Technology, Elsevier
1991.
- N. Ratha and R. Bolle (Eds.), Advances in Fingerprint Recognition, Springer
2002.
|
