6.8.
La recerca en investigació operativa / optimització a Catalunya
DOI 10.2436/15.2000.07.8
Francisco Javier Heredia Cervera
Possiblement, trobaríem tants petits matisos en la definició del que s’entén per investigació operativa (IO) com experts diferents consultéssim. Tractant-se aquest d’un llibre sobre la recerca matemàtica a Catalunya, pot ser interessant fer menció de la definició d’investigació operativa que apareix al Diccionari de matemàtiques i estadística , editat a Catalunya, en què diu:
Investigació operativa: branca de les matemàtiques molt lligada a l’estadística i a l’anàlisi dels processos d’optimització, consistent a aplicar tècniques matemàtiques i estadístiques a la solució de problemes governamentals, empresarials, industrials, educatius, etc.
De fet, aquesta definició té un caire força reduccionista, ja que sembla que limiti la IO a l’aplicació d’un conjunt de tècniques preestablertes a uns problemes ben definits, sense cap referència a la seva metodologia. Segons la definició que podem trobar al web de l’Intitute for Operations Research and the Management Science (INFORMS), la Federació Internacional d’Associacions d’Investigació Operativa proporciona una visió més àmplia d’aquesta disciplina:
In a nutshell, operations research (O.R.) is the discipline of applying advanced analytical methods to help make better decisions. By using techniques such as mathematical modeling to analyze complex situations, operations research gives executives the power to make more effective decisions and build more productive systems (...). To achieve these results, O.R. professionals draw upon the latest analytical technologies, including simulation, optimization probability and statistics.
Si haguéssim de fer un resum de totes dues definicions, potser hauríem de dir que la investigació operativa és una disciplina que, mitjançant la modelització matemàtica i amb eines provinents de les matemàtiques, l’estadística i ―cal afegir― la computació, com ara, l’optimització, la teoria de probabilitats i la simulació, intenta donar solució a problemes de presa de decisió en camps diversos. Com veiem, la investigació operativa cavalca entre diferents disciplines (bàsicament matemàtiques, estadística i computació). La teoria i el conjunt de procediments matemàtics usats per la IO en la resolució de problemes de presa de decisió és el que es coneix com a optimització o programació matemàtica. En la vessant més teòrica, aquesta disciplina s’ocupa de l’estudi de les propietats dels problemes d’optimització i del desenvolupament d’algorismes d’optimització, la seva convergència i el cost computacional. Aquests algorismes poden ser deterministes (tots els paràmetres que defineixen el problema a resoldre es consideren coneguts) o estocàstics (alguns dels paràmetres que defineixen el problema a resoldre són variables aleatòries amb lleis de probabilitat conegudes o estimades). En la vessant més aplicada, l’optimització es dedica a la modelització matemàtica i la resolució de problemes d’optimització reals de grans dimensions mitjançant la implementació eficient dels algorismes d’optimització més adients. Tots aquests aspectes, tant teòrics com aplicats, de la recerca en IO queden reflectits en l’activitat d’algun dels grups de recerca en IO i optimització a les diverses universitats de Catalunya.
La Universitat Politècnica de Catalunya (UPC) és, possiblement, la institució amb una tradició més llarga de recerca en IO a Catalunya i la que compta amb el col·lectiu més nombrós d’investigadors i grups de recerca dedicats a aquesta disciplina, principalment ubicats als departaments d’Estadística i Investigació Operativa, d’Organització d’Empreses i de Matemàtica Aplicada I. A la Universitat Autònoma de Barcelona (UAB) també es desenvolupa recerca destacada en aquest àmbit als departaments de Matemàtiques, d’Economia i Història Econòmica i d’Economia i Empresa. Pel que fa a la Universitat Pompeu Fabra (UPF), en el Departament d’Economia i Empresa també hi ha una intensa activitat de recerca en IO, amb un enfocament cap a les decisions empresarials. Farem una descripció conjunta de l’activitat de totes aquestes universitats, i mencionarem, quan calgui, el lloc on es du a terme principalment.
En l’àrea de l’estudi i el desenvolupament d’algorismes d’optimització, el Departament d’Estadística i Investigació Operativa de la UPC té una llarga tradició en la millora de mètodes d'optimització, tant contínua com mixta (presència de variables enteres i contínues), amb funció objectiu lineal i quadràtica. Per a problemes continus i de gran dimensió, es consideren mètodes de punt interior. Tot i ser algorismes polinòmics, aquests s’han d’especialitzar per a problemes reals, sovint de gran escala (gran dimensió), i amb una estructura particular que cal ser explotada. Això es pot aconseguir aplicant mètodes iteratius basats en gradients conjugats precondicionats a cada iteració dels mètodes de punt interior. Aquesta estratègia és vàlida tant per a problemes lineals com per a problemes convexos, en general. L’obtenció d’un bon precondicionat per al problema particular és clau en l’eficiència del mètode resultant. Per a problemes mixtos lineals, es treballa tant en heurístiques com en mètodes òptims. Les heurístiques usades es basen en fluxos en xarxes i càlculs de punts inicials (usant tècniques tipus feasibility pump). Entre els mètodes òptims, es treballa principalment en descomposicions i reformulacions de Benders, plans de talls i talls perspectius per a problemes mixtos enters quadràtics. També s’ha abordat la resolució de problemes mixtos quadràtics per mitjà de tècniques de descomposició dual basades en algorismes de relaxació Lagrangiana i Lagrangiana augmentada. Dins d’aquest context de relaxació Lagrangiana, s’han proposat nous mètodes d’actualització de les variables duals, anomenats mètodes radar, i algorismes híbrids que combinen les propietats dels mètodes subgradients amb els de les Lagrangianes augmentades. Dins, encara, del camp de l’optimització contínua, el fluxos en xarxes han estat i continuen essent, en l’actualitat, un altre dels camps tradicionals de recerca a la UPC. S’han desenvolupat nous algorismes de fluxos no lineals que permeten resoldre problemes de fluxos en xarxes amb constriccions a banda, és a dir, amb un conjunt de constriccions diferents de les de balanç als nodes de la xarxa, basats en tècniques de particionament primal. Aquests algorismes també s’han adaptat a l’optimització de fluxos multiarticle, és a dir, aquells problemes de fluxos en xarxes en les quals circulen fluxos de diferent naturalesa que no es poden mesclar.
L’optimització estructurada (Tame optimization) és una especialitat del Departament de Matemàtiques de la UAB. Aquest és un camp de recerca prometedor i molt nou: un dels principals objectius és donar més profunditat a la teoria asimptòtica de sistemes dinàmics de tipus gradient, combinant i relacionant idees que provenen de dues branques diferents: l’anàlisi variacional i la geometria moderada. Això pot propiciar avenços significatius per a l’anàlisi de la convergència d’algorismes d’optimització. L’optimització numèrica és la motivació principal que hi ha al darrere d’aquesta part dels objectius, però no és l’única: cal esperar importants aplicacions a altres camps, incloent-hi la teoria del control òptim. Des d’un punt de vista algorítmic, la recerca se centra en el problema general de minimització de funcions no diferenciables, en què la recerca d’algorismes ràpids i eficients per a computar els mínims locals és un problema obert molt important, i que té a veure, essencialment, amb la dificultat de definir objectes matemàtics de segon ordre adequats que capturin el comportament de la funció objectiu al voltant del punt mínim.
L’optimització global és un camp de col·laboració d’investigadors del Departament de Matemàtica Aplicada I de la UPC i del Departament d’Economia i Història Econòmica de la UAB. Aquesta activitat de recerca té per objectiu el desenvolupament d’algorismes d’optimització global i el disseny d’estratègies que permetin aplicar-los a problemes de dimensió gran. La idea és utilitzar estratègies en les quals la cerca lineal (dimensió 1) és reemplaçada per un cerca multidimensional (dimensions 2, 3, 4...) utilitzant algorismes d’optimització global. Aquests mètodes centren l’atenció, bàsicament, en la millora de les solucions obtingudes pels mètodes locals a partir de mètodes globals, més que assegurar-nos que la solució final sigui exactament la global. Aquest fet fa que problemes que en un primer moment són extremadament complicats de resoldre per mètodes globals, i en els quals els mètodes locals donen solucions molt allunyades de l’òptim global, siguin molt més tractables i eficients des d’un punt de vista computacional i obtinguin solucions molt properes a una de global, i sovint a una solució global. Es poden utilitzar diferents estratègies. En primer lloc, s’han dissenyat algorismes en què els mètodes de cerca global s’apliquen per a millorar les propietats de cerca global dels mètodes de cerca local. En segon lloc, s’han desenvolupat algorismes en què els mètodes de cerca globals s’utilitzen per a escapar del punt estacionari que s’ha obtingut mitjançant el mètode de cerca local i generar un nou punt de partida del mètode de cerca local. Finalment, s’ha treballat amb algorismes en què el mètode de cerca global s’utilitza per a generar un conjunt de punts inicials i, tot seguit, s’aplica un mètode de cerca local. Aquests procediments s’han aplicat a problemes de coordinació hidroelèctrica, fiabilitat estructural, problemes de localització, programació fraccional i per a resoldre problemes d’economia i cluster analysis.
Els mètodes heurístics i metaheurístics permeten l’obtenció de solucions factibles habitualment per a problemes d’optimització combinatòria, però sense cap garantia sobre l’optimalitat de la solució trobada. Representen una opció vàlida, si no l’única possible, quan la complexitat del problema a tractar supera les possibilitats dels mètodes exactes de programació lineal entera. Diversos grups, tant de la UPC com de la UPF, han desenvolupat i apliquen tècniques heurístiques (GRASP, Tabu Search, programació evolutiva, etc.) per a la resolució de diversos problemes, com ara l’obtenció de rutes òptimes de vehicles, els problemes de localització, la cadena d’aprovisionament i logística, la gestió de la producció tant uniobjectiu com multiobjectiu, la planificació i la programació d’horaris de treball, i molts altres.
Tots els algorismes mencionats anteriorment consideren que les dades que defineixen els problemes a resoldre són valors coneguts (optimització determinista). De vegades, aquesta hipòtesi és certa, però sovint no és més que una aproximació a la realitat. La disciplina coneguda com a programació estocàstica es planteja mètodes per a resoldre problemes d’optimització en què alguns dels paràmetres es consideren com a variables aleatòries conegudes. La manera habitual d’abordar aquests problemes consisteix en la representació de les variables aleatòries contínues implicades mitjançant l’anomenat arbre d’escenaris, una forma de discretització de la variable aleatòria, i la resolució del problema original a través del seu «equivalent determinista», un problema d’optimització determinista que és equivalent al problema d’optimització estocàstica original. Diversos grups de recerca de la UPC han desenvolupat, ja des de fa anys, models de programació estocàstica per a la resolució de diferents problemes, especialment en el camp de l’optimització de mercats energètics i de la planificació de rutes.
Si ens fixem ara en l’àrea de les aplicacions de les tècniques d’optimització a la resolució de problemes reals de presa de decisió, l’activitat desenvolupada a les universitats catalanes s’ha orientat fonamentalment al camp de la logística i el transport (trànsit, planificació de rutes), a problemes d’organització a la indústria (cadena de subministrament, problemes de localització, planificació de la producció, confecció de plantilles, horaris), a l’administració (problemes de confidencialitat de dades), a empreses de serveis (màrqueting, estratègies d’oferta) i al sector energètic (planificació òptima de la generació d’energia elèctrica, optimització en mercats elèctrics).
En el camp dels problemes de trànsit i transport, els mètodes i les tècniques de la IO han trobat un terreny fèrtil per al desenvolupament d’aplicacions a la UPC, modelant els plantejaments de planificació estratègica, des de la perspectiva de l’equilibri espacial, com a models de desigualtats variacionals que, sota determinades hipòtesis, es poden reduir a casos especials de problemes d’optimització convexa de la classe dels fluxos en xarxes no lineals. Un aspecte crític dels models de transport és l’estimació de la demanda, el nombre de viatges entre diferents punts d’una àrea geogràfica amb motius específics en un interval de temps donat. Aquests models han estat l’origen d’una contribució significativa a les tècniques d’optimització binivell per a problemes no sempre diferenciables ni convexos. D’altra banda, el trànsit és un fenomen típic de sistema dinàmic altament estocàstic, un terreny en el qual la simulació esdevé una eina d’utilització obligada. És aquí on s’han fet algunes de les contribucions més significatives, modelant el comportament dels fluxos de trànsit en xarxes viàries de grans dimensions i desenvolupant un programari (software) de simulació altament especialitzat i evolucionat que ha estat un exemple reeixit de transferència de tecnologia de la recerca universitària al món industrial.
A la UPC també s’ha treballat en els problemes de rutes de vehicles: aquests es modelen com a problemes d’optimització en grafs. Llurs solucions són camins o circuits que compleixen condicions addicionals, com ara subconjunts de nodes a visitar i/o subconjunts d’arestes a travessar, segons el cas. A més de l’interès teòric, aquests problemes tenen nombroses aplicacions en l’àmbit de la logística (repartiment de mercaderies, correu, etc.) i el manteniment de xarxes (de comunicacions, elèctriques, etc.), entre d’altres. Aquests problemes es poden estendre combinant-los amb decisions sobre la millor ubicació per als centres de serveis. S’ha treballat en formulacions de programació lineal entera per a modelar els problemes i també s’han estudiat els poliedres associats. Per a resoldre aquests problemes, s’han fet servir tant tècniques heurístiques com mètodes de branch-and-cut i de caracterització de desigualtats vàlides i facetes dels poliedres. Relacionats amb els problemes anteriors, els problemes de localització busquen la millor ubicació per a centres de serveis i el patró d’assignació de clients potencials a aquests centres. En localització discreta, el conjunt d’ubicacions potencials per als centres de serveis és finit, i conegut a priori. Aquests problemes tenen nombroses aplicacions a l’àmbit de l’administració pública (hospitals, escoles, abocadors, etc.) i a l’àmbit logístic (fàbriques, magatzems, etc.). Els problemes que s’estudien n’inclouen alguns amb incerteses, d’altres amb un horitzó temporal multiperíode i problemes relacionats amb el disseny de territoris (amb aplicacions a la recuperació de residus electrònics, entre d’altres). Dins d’aquest àmbit, també s’han estudiat problemes de localització de concentradors (hubs) que contenen simultàniament elements de problemes de localització i de disseny de xarxes.
Es coneix com a Revenue Management la disciplina que aplica mètodes quantitatius per maximitzar els ingressos davant d’una demanda heterogènia, és a dir, d’uns consumidors amb diverses valoracions i utilitats del producte o servei ofert. Es tracta de vendre el producte adequat, al client adequat, al preu adequat i en el moment adequat. Les indústries hotelera o del transport aeri han estat capdavanteres en l’ús d’aquestes tècniques. Els grups de recerca de la UPF han estat pioners a Catalunya en el plantejament i la resolució d’aquesta mena de problemes.
La publicació de dades per part dels instituts nacionals d’estadística (i, en general, tot organisme que dissemini dades) ha de garantir que no es revela informació privada i confidencial dels individus. El camp del control de la revelació estadística inclou tots els mètodes de protecció de dades. A la UPC hi ha línies de recerca actives en optimització que treballen en mètodes de protecció de dades tabulars (no de microdades). Aquests mètodes formulen problemes d’optimització, continus i mixtos lineals-enters, de gran dimensió. S’ha treballat en el mètode de supressió de cel·les (mètode no pertorbatiu), mètode d’ajustament o pertorbació controlada de taules (mètode pertorbatiu) i protecció per intervals (mètode no pertorbatiu).
Finalment, parlarem de l’aplicació de models de programació estocàstica a problemes d’optimització de mercats elèctrics, una altra de les àrees en què s’ha produït una gran activitat de recerca a la UPC. La liberalització del sector elèctric durant la dècada dels noranta va representar el pas a una situació de lliure competència en què les companyies generadores d’electricitat havien d’elaborar, per a cada hora del dia, ofertes de la seva generació i sotmetre-les a un mercat diari, en què un agent independent, un cop rebudes totes les ofertes de compra i venda, realitzava la cassació i fixava el preu únic de l’energia per a cada hora del dia. Les empreses del sector elèctric es troben en aquesta nova situació davant d’un problema de presa de decisió amb incertesa, ja que cal decidir l’oferta (quantitat d’energia i preu) per a cadascun dels generadors (centrals tèrmiques, hidroelèctriques, nuclears, etc.) sense conèixer el preu de l’energia, perquè aquest és un resultat del procés de cassació del mercat. S’han desenvolupat models de programació estocàstica bietapa i multietapa per a resoldre problemes d’oferta òptima tant a llarg termini, que inclouen en la seva formulació models d’equilibri Nash-Cournot, com de curt termini, en què es determina quines unitats de generació han de participar en cadascun dels vint-i-quatre mercats diaris i la seva oferta òptima. La resolució d’aquests problemes d’optimització provinents del sector elèctric han estat l’origen d’aportacions originals en el desenvolupament de nous algorismes, que van des dels fluxos en xarxes no lineals amb constriccions a banda, uniarticle i multiarticle, fins als mètodes de punt interior, els mètodes de descomposició dual i heurístiques i, més recentment, la recerca en tècniques de programació estocàstica.
.
Diccionari de matemàtiques i estadística. Barcelona: Enciclopèdia Catalana: Universitat Politècnica de Catalunya, 2002. (Col·lecció «Ciència i Tecnologia»)
