SU "ALGORITMO" IN GENERALE E SHORTCUT PER MILP


Vi scrivo una cosa, strana pure per i miei usi e costumi, ma con varie giustificazioni. Una di esse è il levarmi lo sfizio di raccontare quanto ero intelligentino, tanti anni fa. La seconda è smitizzare la difficoltà generalmente attribuita alla matematica anche nelle sue forme più semplici. Terza, fare un esempio della sua utilità. Quarta, cercare di spiegare che perfino uno negato per la matematica (come me) può perfino divertirsi a usarla, se motivato a accendere l'opportuno interruttore (chiedo scusa, in milanese, ma ormai anche in romano, switch) nel cervello. Quinta, trattandosi di cosa da me escogitata che tanti anni fa una sua certa importanza anche economica poteva averla, se i progressi non sono ancora stati tali da renderla assolutamente irrilevante, ricavarci qualcosa non mi dispiacerebbe: ma a tale fine devo prima comunque pubblicarla, anche se solo a un giro di amici. Meglio, di finora amici, finchè non mi mandano apertamente a cercare di rompere le scatole a Belzebub.

Si tratta di una mia modifica a un algoritmo commercialmente e costosamente (ai suoi tempi) usato: ho anche almeno un vero intero algoritmo originariamente tutto mio, e anche simpatico, oltre che bene funzionante, a suo tempo da me realizzato (chiedo scusa, implementato) e credo tuttora usato, ma la cui esposizione richiederebbe troppa fatica per spiegarne il contesto e la specialissima funzione: se poi qualcuno fosse preso da insana curiosità per una cosa in gergo detta power demand (control, ma l'ultimo pezzetto tra i massoni, gli aderenti a una particolare società segreta di addetti, si trascura) può mettersi in contatto e glielo spiego.



Comincio collo smitizzare il parolone di moda: “algoritmo”. Il vocabolo deriva dal nome di un matematico arabo chiamato al Kwharizmi, “il Corasmiano”, “quello della Corasmia”, l'antico nome della regione a sud del lago (o ex lago, ormai è quasi secco) Aral. Il quale, appartenendo a una cultura che, quando in contrade oggi leghiste ci si era ridotti a contare solo sulle dita delle mani (e quelli bravi anche dei piedi), ha salvato alquanto delle cognizioni classiche e anche parecchio incrementandole. Con l'enorme merito tra gli altri, di avere compreso l'utilità dei numeri indiani (o indocinesi, non si sa) adottandoli e rendendoli disponibili a noi come “numeri arabi”, quelli che continuamente usiamo. Incidentalmente, non è che nella cultura classica ci fosse una grande considerazione della Tecnica: nel 1900 nel relitto di una nave antico greca è stato trovato un coso, chiamato “meccanismo di Anticitera” dal nome del luogo del naufragio (e del ritrovamento quasi un paio di millenni dopo), che per capirne la finezza di concezione e realizzazione c'è voluto circa un secolo: sembra provato essere un calendario universale solare, lunare, eclissi, date delle Olimpiadi eccetera. Ma nella letteratura classica la pur avanzata assai capacità tecnica per realizzarlo è sostanzialmente ignorata: eppure questa capacità esisteva e veniva correntemente impiegata. Temo che dipenda anche da questa visione parziale della realtà classica, che già gli autori antichi avevano, la visione a torto definita “umanistica” di Scienza e Tecnica come roba volgare, cafona, da “vile meccanico”, visione che ancora oggi continua a fare danno.

Comunque, il Corasmiano ha redatto e lasciato usatissime e utilissime raccolte di metodi di calcolo, per cui il suo nome è diventato sinonimo di “metodo di calcolo” in generale, senza bisogno che sia qualcosa di terribilmente complicato. Esiste perfino un “algoritmo del mugico”, il sistema usato da poveracci russi in epoca zarista per fare le divisioni, ma non me lo ricordo. E poi è diventato semplicemente “metodo”, per cui abbiamo per esempio anche l'algoritmo per creare il codice fiscale. Quindi di per sé non indica chissà che terribile cosa che solo i versatissimi in matematica possano comprendere e utilizzare: allora è estremamente opportuno non farsi terrorizzare dal parolone, anche perchè la roba in qualche misura STEM (che sarebbe Science, Technology, Engineering and Mathematics, quindi in italiano sarebbe dovuto diventare STIM con la I per Ingegneria) diventa sempre più importante per tutti, per cui per partecipare alle discussioni, o ascoltare per poi decidere chi ha più o meno ragione, e quindi politicamente agire senza estraniarsi o affidarsi a caso e simpatie personali (e poi restare quasi inevitabilmente fregati) è necessario masticarne almeno un po'. E non è per niente vero che sia necessario averne il bernoccolo: in tutte le prove attitudinali fatte, io sono sempre risultato pochissimo naturalmente portato per la matematica, ma questo non mi ha impedito di usarla talvolta assai meglio di persone naturalmente portatissime, ma intimidite, male informate, non consapevoli della sua utilità, eccetera.

Allora, sia per smitizzare, sia perchè mi piace lasciare scritta un'idea che mi pare brillantina e forse forse pure ancora utile, tento di rifilarvi un esempio vissuto, spiegandolo (nelle mie intenzioni) chiarissimmente.

Dunque, esiste (e deve venire spessissimo affrontata) una classe di problemi analoghi matematicamente a quello della formulazione di una miscela per fare (per esempio !) un cibo da gatti. Occorre che i croccantini abbiano una percentuale di vitamina A compresa tra un certo minimo e un certo massimo, così per la vitamina B, per la C, per ogni vario tipo di grassi, di proteine, di fibre eccetera eccetera. Abbiamo a disposizione un certo numero di ingredienti di partenza da miscelare, e per ogni ingrediente di partenza sappiamo quanta vitamina A e quanto di ogni altra cosa necessaria c'è: per esempio, in un preparato commerciale di vitamina A c'è un 98% di quella vitamina e zero % di vitamina B, il 2% per la C, zero per i grassi eccetera. Invece, continuando l'esempio, sappiamo che nella farina di soia c'è un certo tenore (in percentuale) di vitamina A, un altro di B, un altro di C, un altro di grassi saturi, un altro di grassi insaturi eccetera eccetera. E poi sappiamo quanto costa ogni ingrediente di partenza: devo arrivare a sapere quale è la miscelazione degli ingredienti di partenza che rispettando gli obblighi (“vincoli”) del tipo “ tenore di vitamina C compreso tra un certo minimo e un certo massimo” viene a costare di meno. Si scrivono tutti i numeretti in un certo modo, facendo una specie di tabella, in cui ogni colonna corrisponde a un certo ingrediente di partenza, ogni riga corrisponde agli obblighi (vincoli) di minimo e di massimo di ogni tenore di ingrediente di arrivo (vitamine, grassi, zuccheri, fibre eccetera), mentre nella riga finale si scrivono i costi di ogni ingrediente di partenza. Si fa inghiottire questa “tabella” o “matrice” a un software apposito, comperato o noleggiato, caricato su un computer abbastanza potente (ma per moltissimi problemi non troppo complicati basterebbe quello che molti di noi hanno a casa), il quale lo mastica ben bene e ti sputa il risultato. Dentro c'è un “algoritmo”, chiamato “del simplesso”, che il suo lavoro lo fa benissimo e viene correntemente usato una caterva di volte. Occhio, ma tanto per dire, anche la benzina che mettete nel serbatoio dell'auto è stata, di solito, “formulata” con questo sistema, perchè in realtà le benzine in uscita dalle raffinerie non sono tutte perfettamente uguali per composizione e costo: quindi per ogni partita di benzina da mandare alla distribuzione si ricalcola la miscelazione migliore. O si faceva così, almeno ai tempi miei.

Ma se in questo caso normale non c'è insomma che da procurarsi il software e alimentarlo, insomma quasi scoprire l'acqua calda (come per l'antico problema del “LHCP,” o Left Handled Chamber Pot, ossia il Pitale col Manico a Sinistra, per i destrimani, se pesante, difficile da reggere con la sinistra, avente la soluzione “Rotate”, ossia “giralo”, avvertendo che per i mancini può esistere il problema speculare RHCP, la cui facile soluzione si lascia al lettore), per molti casi importanti e pure assai le cose possono non essere tanto lisce. Nel caso normale si ha sempre a che fare con le solite quantità espresse da numeri “reali” come 5,23 o 18,435 o 22,052 eccetera: ma esistono appunto problemi dove non si possono usare le frazioni. Per un esempio semplice semplice, la ditta A specializzata in cibo per gatti deve fare un quintale di croccantini, ma un costoso ingrediente di partenza viene venduto dalla fabbrica solo in confezioni da 5 chili. Senza tenerne conto, la miscela ideale prevederebbe 7,15 kg di quell'ingrediente: che fare ? Bah, si fa rigirare il software imponendo una volta che dell'ingrediente se ne mettano 5 chili e una seconda volta imponendone 10, quindi le possibili soluzioni, in questo caso semplice, si può ammettere siano solo due, si fanno calcolare tutt'e due e si sceglie la meno peggio. Ma in numerosi e importantissimi problemi la complicazione aumenta enormemente, e finiamo nel vero campo dei MILP, Mixed Integer Linear Programming, cioè problemi e algoritmi di ottimizzazione in cui ci sono mischiate grandezze esprimibili coi soliti numeri frazionari e altre invece che per natura loro devono essere espresse da numeri interi. Molto spesso si tratta di problemi in cui ci sono da fare delle scelte “discrete”: per esempio, in un laminatoio non è che sullo stesso spessore puoi fare contemporaneamente le larghezze di lamiera che ti pare: clienti e regole di unificazione prevedono certe larghezze e non altre, non puoi fare contemporaneamente larghezze che sommate superino la largezza del laminatoio, eccetera. In generale, la somma delle larghezze può anche essere inferiore a quella alla quale il laminatoio deve lavorare, e poi tagliare a misura, ma allora hai degli scarti che vanno a rottame, eccetera eccetera. Anche problemi (alle volte enormi) di programmazione politico-economico-industriale ricadono in questo genere di complicazioni. E se non ricordo male, ai tempi dell'URSS già assai languente ma ancora in mano agli apparatciki la propaganda loro ha lanciato la favola di un loro supercalcolatore lavorante non in logica binaria (come tutti fino ad ora) ma ternaria, con l'unità di base di informazione dai possibili valori 0, 1 e 2 anziché solo 0 e 1. Poi si è dimostrata una balla: ma la motivazione era politica, fare credere di potere essere all'avanguardia tecnica e potere avere uno strumento efficace per potere davvero calcolare tutta la programmazione industriale, fino al colore delle carte delle caramelle, per dire.

E la balla un senso politico ce l'aveva, perchè in molti problemi anche di programmazione industriale si tratta di complicazioni assai rapidamente crescenti: se hai una sola variabile incognita che deve avere solo valori interi compresi tra zero e 10, hai 11 soluzioni possibili. Ma ti basta averne due di questo genere perchè le possibili soluzioni diventino 11x11 ossia 121: e si tratta di pinzillacchere, rispetto a molti problemi reali e pure assai importanti.

Bene, quando lavoravo, negli alti gradi del baraccone, dove solo una sparutissima minoranza di teste pensanti cercava di salvare almeno qualcosa, salta fuori il desiderio, o la speranza, appunto, di affrontare un problema di questo genere.

Ma già per cominciare a formalizzare la faccenda cominciavano i guai: comunque, si esplora un po' l'ambiente tecnico più evoluto e tra le altre informazioni rilevanti si trova che la ditta nostra obbligata (e questo sarebbe poi tutto un altro grosso dramma, costato molti miliardoni di lirette e molti molti molti posti di lavoro) come fornitrice (USA ma non IBM) dei computer o “cervelli elettronici” su cui soli si poteva lavorare, il software ce lo fornivano, però senza sostanziale assistenza. O meglio, ci fornivano il collegamento in “Time Sharing” (suddivisione di tempo macchina) via linea telefonica e poi satellie, con dei sistemi di calcolo che per quei tempi erano “supercomputer” e che stavano non so dove negli USA, assieme alla documentazione necessaria minima per poterci lavorare. Il software, sempre per quei tempi, era all'avanguardia, e veniva correntemente usato anche da grossissime ditte italiane.

Va bene, mi studio il tutto, mi impratichisco un po', e poi costruisco un modellino assai semplice del problema da affrontare, nella speranza che le nostre difficoltà organizzative potessero essere almeno parzialmente superate. Il modellino funzionava, il software pure, e l'utilizzo era giusto: ci ho pure rimediato un viaggio a Vienna ottenendo la benedizione del guru europeo della faccenda.

Ma appena appena lo si ingrandiva per renderlo via via più realistico, il tempo di calcolo, anche se per il momento non ce lo fatturavano, aumentava spaventosamente. Per cercare di combinare qualcosa, mi è sembrato indispensabile entrare nel dettaglio della logica dell'algoritmo, e ci ho trovato qualcosa su cui intervenire.

In presenza di una variabile incognita, quindi da trovare come parte della soluzione assieme a tutte le altre, variabile, dicevo, solo intera, I1 di valore compreso tra 0 e, poniamo, 15, l'algoritmo la sostituiva con una somma di 15 variabili “binarie” I11 , I12 , I13 , I14 , ...... I113 , I114 , I115 intere, che potevano assumere, nel corso dell'algoritmo, soltanto i valori 0 oppure 1. Il motivo di questo giochetto era che di volta in volta attribuendo a queste variabili tutte le possibili scelte tra 0 e 1 e assumendole di volta in volta come obbligate si ottenevano tutti i possibili valori di soluzione (in concomitanza sempre con lo stesso giochetto sulle altre variabili incognite intere), semplificando le scelte di ricalcolo. Ossia, si generavano delle ipotetiche soluzioni, e muovendosi in questo insieme di possibili soluzioni per tentativi guidati dalle soluzioni fino a quel punto calcolate (il metodo si dice di “branch and bound”, ma è inutile qui scendere nei dettagli) si poteva beccare la meglio.

Ma se invece di usare la bellezza di quindici variabili intere binarie, per la nostra variabile I1 di valore compreso tra 0 e 15 ne uso solo 4, ma ciascuna moltiplicata per potenze crescenti di 2, che succede ?

Dunque, ricordiamo che 2 elevato a potenza zero, cioè 20 = 1, poi 21 = 2 22 = 4 23 = 8.

Allora, IC11 = I11 x 1 può assumere solo i valori 0 o 1, IC12 = I12 x 2 può assumere solo i valori 0 oppure 2, IC13 = I13 x 4 può essere solo 0 o 4,

IC14 = I14 x 8 può essere solo 0 oppure 8. Vediamo tutti i casi possibili.

Le colonne sono i possibili valori delle nostre 4 variabili binarie moltiplicate p2 2 alla “potenza” zero, poi per 2 alla potenza 1, cioè 2, eccetera.                                            

                      Somma = I1


0     0      0     0              0

1     0     0     0               1

0     2     0     0               2

1     2     0     0               3

0     0     4     0              4

1     0     4     0              5

0     2     4     0              6

1     2     4     0              7

0     0     0     8              8

1     0      0    8              9


eccetera fino a


1     2     4     8             15


Insomma, usando in opportuna combinazione le variabili binarie previste dall'algoritmo usato dal software fornitoci, sono riuscito ad avere una variabile intera (l'incognita originaria) di valore compreso tra zero e 15 usando però solo 4 variabili ausiliarie invece di 15.

Allora, forzando il programma a fare come dicevo io (come ho fatto sono cavoli miei, e poi è astruso da spiegare) nelle prove ho avuto gli stessi identici risultati, ma in pochissimo tempo, un quarto o un quinto rispetto alla versione originaria fornitaci dagli USA come il meglio del meglio universale.

Ma perchè tutto questo miglioramento da un'idea certo simpatica, ma poi mica tanto trascendentale ? Per un motivo certo e probabilmente anche per un altro di cui non sono sicuro. Non ne sono sicuro perchè ho agito sull'algoritmo dall'esterno, usando il linguaggio “utente”, quello di espressione dei problemi a disposizione dell'utilizzatore, senza entrare nel vero e proprio codice sorgente, cosa che poi il sistema mi avrebbe impedito. Il primo motivo, quello certo, è il grande risparmio sul numero di variabili che poi l'algoritmo deve usare per i suoi tentativi esplorativi alla ricerca della soluzione più conveniente.

Il secondo motivo, quello possibile ma che non ho potuto verificare, è questo: nella rappresentazione originaria, il valore, per esempio 3, da attribuire all'incognita per calcolare il risultato e valutare se si è su una strada promettente su cui proseguire coi tentativi, può essere rappresentato da molte diverse configurazioni dell'insieme delle quindici variabili ausiliarie: 0,0,0, 1, 0, 1, 1, e tutti zeri fanno somma 3, come anche 1,0,1,1,0,0 eccetera: ossia, col trucchetto mio ho tolto intrinsecamente subito di mezzo una gran quantità di configurazioni diverse ma perfettamente equivalenti al fine del risultato. Allora, l'algoritmo deve cercare la soluzione valida tra un numero di ipotesi assai minore, senza dovere valutare (calcolandole) moltissime soluzioni sostanzialmente identiche tra di loro e quindi inutili da perderci lavoro macchina sopra.

Poi la, diciamo, “azienda” in cui lavoravo di fronte a una caterva di guai e all'incapacità di prevederli, capirli e tanto meno potervi porre rimedio, aveva ben altre gatte da pelare, per cui non se n'è fatto nulla.

Ora, ormai povero vecchietto, mi scoccia che una mia idea forse potenzialmente utile vada persa, per cui ve la ho scritta, così rendendola pubblica (ammesso che a qualcuno possa interessare). Ho fatto qualche indagine sullo stato dell'arte attuale dei software pronti per i problemi MILP, ma se certamente ci sono stati dei miglioramenti, non è che posso (e sopratutto non ne ho voglia) di indagare più approfonditamente: quindi non sono in grado di escludere che quella mia idea oggi sia veramente diventata inutile o sia rimasta valida, almeno per quanto riguarda un genere di problemi particolarmente rognosi. Certamente i software attuali ricorrono sempre a una “tattica” di branch and bound, esplorando per scelte successive (comportanti anche frequenti salti all'indietro) l'insieme delle possibili soluzioni. Per quanto i costi di elaborazione siano oggi un millesimo di quanto erano decenni fa, comunque i problemi MILP sono tanti e potenzialmente tanto complessi da potere comunque rendere utile il rendere intrinsecamente veloce l'algoritmo, senza fare conto solo sulla bruta potenza dell'hardware.

Mi è ovviamente dispiaciuto non potere poi utilizzare meglio la mia ideuzza, ma le gatte da pelare urgentissime erano tante e i vincoli organizzativi, commerciali e politici erano tali da renderlo assolutamente impossibile. Però mi levo la soddisfazione di cercare di raccontarla in giro, anche se assai probabilmente non ci sarà nessuno disponibile a dirmi, per conoscenza e comprensione della cosa, che sono stato bravino... Non è poi che spero di ricavarci qualcosa di pratico: se arriva tanto meglio, ma non ci conto. Comunque un primissimo contattino con una casa produttrice e fornitrice di software per i MILP lo ho avuto, e non è che mi abbiano risposto “Lei non ha capito proprio niente”: mi hanno rilanciato a un'altra ditta, sempre USA, che gli ha costruito l'algoritmo. Intanto però mando in giro questa mia anche come un primissimo livello di comunicazione pubblica.

Alla vostra Somma Pazienza !


Claudio Fornasari


Roma, 3 Marzo 2020

(Diffusa tramite email)