Els mètodes de punt interior per a programació lineal proporcionen algorismes de complexitat polinòmica, que els fa ser molt eficients en l’optimització a gran escala. Aquests algorismes utilitzen el mètode de Newton per a convertir les equacions d’òptim del problema, que són no lineals, en un sistema d’equacions lineals, que solen resoldre’s aplicant factorizacions de matrius esparses. En aquells casos particulars en els quals el problema té una estructura especial, com ara en els problemes d’optimització en xarxes multiarticle, es pot aprofitar per millorar l’eficiència de l’algorisme. Aquests problemes de xarxes pertanyen a la família més general de problemes primals bloc-angulars. El punt de partida d’aquesta tesi va ser un fet empíric: l’observació del millor comportament computacional d’un algorisme especialitzat de punt inferior per a problemes bloc-angulars quan en la funció objectiu figurem termes quadràtics. Aquest algorisme utilitza factoritzacions de matrius per resoldre la part de les equacions associades a la zarza i el mètode del gradient conjugat precondicional per resoldre les equacions asociadse a les restriccions d’acoblament. Llavors l’objectiu original va ser buscar alguna forma d’aproximar un problema lineal per un quadràtic de manera que s’explotés el fet experimental observat sense perjudicar la convergència del problema. Posteriorment el plantejament inicial es va amplificar amb el nou objectiu de demostrar la convergència del mètode, entre altres resultats teòrics. El marc teòric usat per poder formular matemàticament aquesta idea ha estat la regularització de la funció de barrera logarítmica associada al problema d’optimització, entenent com a tal la transformació de la funció de barrera original per una altra que inclou un terme quadràtic variable de pertorbació, que disminueix progressivament conforme l’algorisme s’atansa a l’òptim. Aqueste terme quadràtic converteix el problema lineal original en un de quadràtic, de forma que en les primeres iteracions aprofitem el comportament empíric abans esmentat i, a mesura que progressa l’algorisme, el terme quadràtic esdevé negligible, i el problema amb regularització quadràtica s’atansa al problema lineal original. La barrera regularitzada resulta ser auto-concordant, assegurant així la convergència del mètode de punt interior.

Tal i com indica el seu títol, la present memòria de tesi té com objecte d'estudi el desenvolupament d'algorismes i implementacions eficients per resoldre el problema conegut dins del món de l'Optimització i Investigació Operativa com a problema de fluxos multiarticle en xarxa. Com es desprèn del seu nom, és un problema d'optimització en xarxa on, a diferència del problema clàssic uniarticle, diversos productes (els articles) comparteixen el mateix canal físic (la xarxa) sense poder ser combinats entre ells. Això provoca que sigui necessària una replicació de les variables -fluxos en cada arc- de la xarxa original, tantes vegades com articles hi ha, el qual incrementa considerablement el nombre de variables i constriccions a ser tractades.L'optimització de fluxos en xarxes multiarticle és un problema ben conegut, i durant anys diverses aplicacions reals han estat modelitzades mitjançant aquesta tècnica. Alhora, és un problema molt costós des d'un punt de vista computacional, donat el gran nombre de variables i equacions que intervenen com abans s'ha esmentat. Aquest doble fet (el seu interès per solucionar problemes reals i el seu elevat cost) ha motivat l'estudi i desenvolupament de tècniques per tractar-lo de forma específica. Sovint, però, aquest esforç ha conduït a la formulació de diversos algorismes però rarament ha donat lloc a implementacions de caràcter pràctic. Amb això que acabem de dir queda clar que suposarem que hi ha una clara distinció entre el que és algorisme i el que és implementació, tot i que sovint és difícil decidir on hi ha la frontera entre un i altre concepte. En general, per algorisme entendrem la seqüència de processos que s'han de seguir per tal d'aconseguir un cert objectiu, mentre que la implementació fa referència a com, en última instància, s'han dut a la pràctica. Des d'aquest punt de vista es podria dir que un algorisme té moltes implementacions, però que una implementació només respon a un únic algorisme. S'ha cregut convenient fer una breu discussió sobre els conceptes d'algorisme i implementació, donat que al treball aquí presentat ambdós tenen un pes específic. Al treball desenvolupat no s'ha pretès només detallar com modificar, ampliar o obtenir algorismes per solucionar el problema de fluxos multiarticle, sinó que a més s'ha plantejat com objectiu prioritari l'obtenció d'implementacions el més eficients i robustes possibles. Vista així, la tasca desenvolupada es troba a cavall entre dos camps com ara la Investigació Operativa i la Informàtica. També cal tenir present que en aquesta memòria es presentarà detalladament tot el que faci referència a la part algorísmica però no tant a nivell d'implementació. Això implicaria haver de descriure una gran quantitat d'estructures de dades i una gran quantitat de rutines desenvolupades i altres usades de llibreries numèriques estàndard. Tanmateix, això no ha de fer oblidar que la major part de l'esforç necessari ha estat dedicat a l'obtenció i disseny d'aquestes rutines i estructures de dades. I el fet de que tot aquest treball quedi plasmat en només l'obtenció d'una sèrie de taules amb valors numèrics no ha de fer oblidar la gran quantitat de feina no descrita que hi ha darrera d'aquests resultats.Un cop s'ha definit el marc on es troba el treball realitzat, procedirem a definir amb més detall els objectius que s'han perseguit i les aportacions que representa respecte el que fins ara s'havia fet. Finalitzarem la introducció amb una breu descripció sobre com ha estat estructurada aquesta memòria.