Programele de optimizare

Programele de optimizare au marcat foarte interesant istoria informaticii românești pentru că:

- erau necesare produse software care să implementeze algoritmii de optimizare;

- se urmărea maximizarea dimensiunii problemei de rezolvat;

- dintr-o mulțime de algoritmi era selectat acela care permitea atingerea unui obiectiv;

- transpunerea de algoritmi de cercetări operaționale presupuneau artificii;

- din start programatorii și-au dorit să realizeze programe generale, pentru biblioteci;

- testarea programelor de optimizare presupune utilizarea de exemple din cărți;

- unele programe de optimizare au zone care nu sunt testate din lipsa exemplelor;

- restricțiile de memorie sunt extrem de dure, iar volumul de calcule este și el dur.

Problema de programare liniară are mai mulți algoritmi și au fost implementări interesante și spectaculoase, iar mie mi-a plăcut foarte mult prin anii '80 că realizatorii lor propuneau și niște inegalități care permiteau calculul dimensiunii maxime a problemei de rezolvat, știut fiind faptul că în acele vremuri capacitatea memoriei interne era o mare problemă, adică o teribilă restricție.

Voi lua acum un alt exemplu, nu o procedură de optimizare și un subprogram pentru calcului produsului a două matrice.

Procedura va avea necesita definirea următorilor operanzi:

- o matrice A[M][N];

- o matrice B[N][K];

- o matrice rezultat C[M][K];

- variabilele de control i, j, k;

- variabila de lucru Cij unde se calculează suma de produse.

Dacă procedura în format executabil ocupă L bytes, matricele A, B, C și variabila  Cij sunt de tip float, iar variabilele de control i, j, k, m, n sunt de tip int, iar disponibilul de memorie al calculatorului este de DISP bytes, restricția pe care o construim este:

(M * N + N * K + M * K + 1) * 4 + 12 < DISP

unde:

- M * N *4 dimeniunea matricei A exprimată în bytes; 

-  N * K * 4 dimeniunea matricei B exprimată în bytes; 

- M * K * 4 dimeniunea matricei A exprimată în bytes;  

-  1  * numărul de bytes ocupați de variabila Cij; 

- 6 * 2 = 10 bytes ocupați de variabilele i, j, k m, n, h.

După același raționament se calculează restricțiile pentru orice program de optimizare, lucru deosebit de important când se scriau astfel de programe. Acum când se lucrează la nivel de Gb astel de restricții ne permit să constatăm câte zeci de mii de linii și câte zeci de mii de coloane au matricele cu care dorim să lucră, ceea ce este extrem de confortabil în zilele noastre. Nu am spus nimic de lungimile de la segmente care în vremurile de demult aveau aportul lor în a crește sau din contră în a reduce performanțele programelor dacă definirea de variabile era multisegment.

Chestiunile dure apăreau și în ceea ce priveau volumul de operații de prelucrare  exprimat grosier ca număr de instrucțiuni executabile. Pentru secvența de calcula aprodusului de două matrice volumul de prelucrări V este dat de relația:

V = n * m * 2 *( 1 + h) instrucțiuni.

Am folosit termenul grosier pentru a arăta că nu țin seama cât de diferite sunt instrucțiunile for() de cele de calcul și de atribuire. Cel pai riguros ar fi dacă s-ar lucra ca număr de cicluri mașină.

Pachetele de programe de optimizare în care apar iterații trebuie să conțină multe elemente dintre care limitarea duratei maxime disponibile, preciziei și a numărului de iterații sunt esențiale. În plus, ele trebuie să permită afișarea:

- datelor inițiale;

- soluției optime;

- erorii de calcul;

- numărului de iterații;

- situațiilor speciale de întrerupere.Acum au intrat în zona banalului aceste programe de optimizare, lumea căutând să le folosescă mai ales în simularea de situații cu postoptimizări și parametrizări. De asemenea, am văzut niște aplicații de optimizare multicriterială cu implementări interesante în acele vremuri, prin agregări care reduceau tot la o banală optimizare. N-am insistat, căci de prea multe ori am văzut aplicat algoritmul simplex la probleme care se pretau la programare în numere întregi. Una este să se optimizeze producția de cutii de conserve unde rotunjirea este nesemnificativă și alta este să se optimizeze cu simplex producția de autorurisme care rotunjire devine catastrofală la o adică.
Programele de optimizare au reprezentat parte din mitologia istoriei programării pentru că implementările în care numărul de variabile și numărul de restricții dacă depășeau ordinul miilor deveneau ceva de domeniul fantasticului.

(23 noiembrie 2017)