This dissertation revolves around the idea of linear interference alignment (IA) for a network consisting of several mutually interfering transmitter-receiver pairs, which is commonly known as interference channel. In particular, we consider the case where nodes are equipped with multiple antennas and exploit the spatial dimension to perform interference alignment. This work explores the problem of linear spatial domain interference alignment in three different facets. Our first contribution is to analyze the conditions, i.e., number of antennas, users and streams, under which IA is feasible. For this task, we distinguish between systems in which each user transmits a single stream of information (single-beam systems) and those in which multiple streams per user are transmitted (multi-beam systems). For single-beam systems, we show that the problem admits a closed-form solution with a time-complexity that is linear in the number of users. For multi-beam systems, we propose a numerical feasibility test that completely settles the question of IA feasibility for arbitrary networks and is shown to belong to the bounded-error probabilistic polynomial time (BPP) complexity class. The second contribution consists in generalizing the aforementioned feasibility results to characterize the number of existing IA solutions. We show that different IA solutions can exhibit dramatically different performances and, consequently, the number of solutions turns out to be an important metric to evaluate the ability of a system to improve its performance in terms of sum-rate or robustness while maintaining perfect IA. Finally, our contributions conclude with the design of two algorithms for the computation of IA solutions. / Esta tesis gira en torno a la idea de alineado de interferencias (interference alignment, IA) lineal en redes donde varios pares transmisor-receptor se comunican simultáneamente; escenario conocido como canal de interferencia. En particular, se considera el caso en el que cada nodo (ya sea transmisor o receptor) está equipado con varias antenas y hace uso de la dimensión espacial para llevar a cabo el citado alineado de interferencias. En esta tesis se explora el problema del alineado de interferencias en el dominio espacial desde tres puntos de vista diferentes. En primer lugar, se analizan las condiciones (número de antenas, usuarios y flujos de información) bajo las cuales el alineado de interferencias es posible. Para esta tarea, se distingue entre sistemas en los que cada usuario envía uno o múltiples flujos de información. En el primer caso, se demuestra que el problema admite una solución cerrada que puede ser evaluada con complejidad lineal en el número de usuarios. En el segundo caso, se propone un test numérico que da una respuesta concluyente al problema y muestra que el problema pertenece a la clase de complejidad BPP. En segundo lugar, los resultados anteriores son generalizados para calcular el número de soluciones existentes. En ocasiones, no sólo interesa determinar si el problema de alineado de interferencias tiene solución o no, sino que es interesante conocer cuántas soluciones existen. En esta tesis se muestra que diferentes soluciones pueden exhibir resultados dramáticamente diferentes. Por consiguiente, el número de soluciones actúa como una métrica de diversidad que refleja la capacidad de una red para mejorar su rendimiento en términos de tasa suma, robustez o cualquier otra métrica. Por último, se proponen dos algoritmos para la obtención de soluciones de alineado de interferencias.

La implementació dels sistemes de transport intel·ligent (ITS) ha possibilitat disposar de gran quantitat de dades de trànsit en temps real, utilitzant les actuals infrastructures en la xarxa viària que ens permeten recollir informació on-line. Mesures de flux de trànsit, velocitats o ocupació proporcionats pels detectors son un exemple. Com utilitzar les dades de trànsit en temps real, així com les dades històriques, per realitzar una predicció a curt termini és encara un problema obert als investigadors. El problema de la predicció del trànsit a curt termini és determinar l'evolució del flux del trànsit o, de forma equivalent, l'estat de la xarxa. La possibilitat de realitzar una predicció dinàmica de l'estat de la xarxa és essencial per la gestió del trànsit i centres d'informació de trànsit, permetent l'aplicació de polítiques de control o gestió per prevenir les congestions, i evitar el problemes que es deriven quan aquesta congestió ja és present.Els sistemes avançats de gestió de trànsit (ATMS) i sistemes avançats d'informació de trànsit (ATIS) han de considerar en temps real períodes de temps on ni la demanda ni el flux de trànsit son constants ni homogenis. La demanda i el flux tenen un comportament dinàmic, és a dir, son dependents del temps. El concepte de gestió de trànsit, com es defineix en Barceló (1991), té un sentit més ampli que el clàssic concepte de control de trànsit, ja que realitza accions sobre el temps, incloent el control sobre l'espai, com per exemple la redistribució dels fluxos amb accions de "rerouting" proposant rutes alternatives. Com a conseqüència la gestió de trànsit requereix una modelització dinàmica que representi la variació del flux a través del temps. Totes les propostes de sistemes avançats de trànsit i sistemes de control basats en les tecnologies telemàtiques estan d'acord amb la importància de la predicció a curt termini de l'evolució del flux de trànsit, que és equivalent a tenir una predicció a curt termini de l'estat de la xarxa viària per gestionar correctament el trànsit, disseminació de la informació als usuaris, etc. Algunes arquitectures de sistemes han estat proposades i avaluades en projectes Europeus en els darrers anys. Malauradament els resultats obtinguts en aquests projectes no es poden extrapolar o aplicar a estructures urbanes complexes. Altres propostes més adequades a estructures més complexes han estat desenvolupades, com per exemple les referenciades en Cascetta (1993) i Barceló (1997), però aquests models no son massa apropiats en aplicacions totalment dinàmiques i això ens ha portat a explorar altres direccions per cercar un model de predicció adequat. Davant les prometedores capacitats de les xarxes neuronals com a eines útils en la predicció, (Baldi i Hornik, 1995), vàrem decidir explorar aquesta alternativa. Aquest plantejament, basat en l'obtenció de dades de detecció reals combinat amb les matrius OD històriques, determina la predicció a curt termini de la matriu OD, definida per períodes. Aquesta matriu obtinguda com a resultat, pot ser utilitzada com a dada d'entrada en el simulador microscòpic de trànsit i obtenir l'evolució dels fluxos de trànsit, i com a conseqüència, la predicció de l'estat de la xarxa.Considerant aquesta visió dinàmica de la demanda, podem considerar cada element de la matriu O/D com una sèrie temporal, i per tant la predicció d'una matriu OD consisteix en realitzar la predicció de cada component de la matriu, és a dir, la predicció simultània de diverses sèries temporals multivariants. Solucions a aquest problema basades en mètodes de predicció clàssics, com per exemple Box-Jenkins o filtres de Kalman, han estat proposat per diversos autors (Davis, 1993; Davis et al., 1994; Van der Ziipp i Hamerslag, 1996), i aquestes propostes donen bons resultats en infrastructures lineals, com podria ser el cas d'autopistes, però en el cas de xarxes amb una estructura més complexa, com podria ser un xarxa urbana, no està clar si proporcionen resultats acceptables, encara que en alguns del més prometedors casos, (Davis,1994), la càrrega computacional necessària posa en dubte el seu ús en aplicacions en temps real de xarxes d'una mida considerable, fent necessari la cerca d'altres mètodes.Les xarxes neuronals apareixen com a candidates naturals per un model de predicció, amb el valor afegit de la seva estructura fàcilment paral·lelitzable que en el cas d'un sistema en temps real és una característica a tenir en compte. Una altra raó per pensar en la utilització de les xarxes neuronals son els resultats reportats per en Chakraborty (1992) en l'anàlisi de sèries temporals multivariant utilitzant xarxes neuronals, o d'en Weigend (1992) en l'avaluació de les capacitats predictives comparades amb altres models clàssics.La predicció dinàmica de l'estat de la xarxa en termes de predicció de la matriu OD utilitzant Xarxes Neuronals té un inconvenient: la quantitat de dades necessàries per un correcte aprenentatge. El treball de recerca realitzat en aquesta tesis proposa solventar aquest desavantatge particionant la xarxa neuronal amb grups de parells OD "independents" segons la identificació de camins més utilitzats.La predicció a curt termini desemboca d'aquesta forma cap al crític problema de l'Assignació Dinàmica de Trànsit (DTA), que en aquesta tesis és resolta amb una heurística basada en la microsimulació. El treball de recerca planteja un dels aspectes més crítics de la simulació dinàmica de xarxes viàries, anomenat heurística d'assignació dinàmica, amb la consideració dels models de selecció de rutes, i la metodologia de la validació, un aspecte important per determinar el grau de validació i significació dels resultats de simulació. Aquest treball està estructurat en dues parts, la primera ens dóna una visió global de com les principals funcionalitats han estat implementades en el simulador microscòpic AIMSUN, (AIMSUN 2002), i una segona part dedicada a parlar en detall de la heurística dissenyada i determinar una guia en la calibració/validació dels seus paràmetres. Un cop el model de simulació està validat i calibrat, llavors és utilitzat per realitzar el DTA on els seus resultats ens permeten identificar els camins més utilitzats per llavors determinar la partició dels parells OD i així la definició de les xarxes neuronals per la realitzar la predicció. / The implementation of Intelligent Transport Systems (ITS) has made vast quantities of real-time traffic data available, by making use of current road network infrastructure that enables information to be gathered on-line. Detectors that measure traffic flow, speed and occupancy are an example. How to use real-time traffic data, as well as historical data, to provide short-term traffic prediction, remains an open problem for researchers. The problem of short-term traffic prediction involves determining the evolution of traffic flows or, equivalently, of the network state. The ability to predict the network state dynamically is essential in traffic management and for traffic information centres particularly, since it enables them to apply traffic control and traffic management policies to prevent traffic congestion rather than dealing with traffic problems after congestion has already occurred. Advanced traffic management systems (ATMS) and advanced traffic information systems (ATIS) must consider, in real time, short time intervals in which neither demand nor flows are constant and homogenous. Demand and flow behave dynamically, that is, they are both time-dependent. The concept of traffic management, as defined by Barceló (1991), is broader than the classic concept of traffic control, because it takes action over time, including control over space, such as, for instance, redistributing flows by rerouting, that is, by proposing alternatives routes. Therefore, traffic management applications require dynamic modelling that shows flow variation over time.All proposals for advanced traffic management and control systems that are based on telematic technologies agree on the importance of short-term prediction of traffic flow evolution, which is equivalent to the short-term prediction of the network state, for correct decision-making in traffic management, information dissemination to users, etc. Several system architectures have been proposed and evaluated in European projects in recent years. Although the achievements of these projects cannot be applied or extrapolated to complex urban structures, other models that are more suited to complex networks have been developed, by Cascetta (1993) and Barceló (1997), for example. Unfortunately, these models do not appear to be appropriate for full dynamic applications, and so we had to look elsewhere in our search for a suitable prediction model. The promising features of neural networks, which make them suitable for use as predictive tools (Baldi and Hornik, 1995), encouraged us to explore this approach. The approach, which is based on real-time detector measurements combined with historical OD matrices, involves determining a short-term forecast of a sliced OD matrix. The forecast OD matrix could be used as input for a microscopic traffic simulator such as AIMSUN; thus the evolution of traffic flows and, as a consequence, the forecast network state could be obtained.According to this dynamic vision of demand, we can consider each of the OD matrix's components as a time series. Therefore, forecasting an OD matrix consists in performing the forecast for each component in the matrix, that is, in simultaneously forecasting many multivariate time series. Solutions to this problem that are based on classic forecasting methods, such as Box-Jenkins or Kalman filtering, have been proposed by several authors (Davis, 1993; Davis et al., 1994; Van der Ziipp and Hamerslag, 1996). The approaches proposed provide relatively good results for linear infrastructures, such as motorways, although it remains unclear whether they would provide reliable results in the case of more complex networks, such as urban networks. In some of the most promising cases (Davis, 1994), however, the computational task required practically invalidates their use in real-time applications in large-scale networks and makes it advisable to look for other methods. Neural networks appear to be natural candidates for forecasting models, particularly if their easily parallelisable structure is taken into account, and high computational speed is required to achieve a system's objectives. Further reasons to consider a neural network approach are the results reported by Chakraborty (1992) for multivariate time series analysis using neural networks and by Weigend (1992) in his evaluation of their predictive capabilities compared to other classic models.The dynamic prediction of the network state in terms of the OD matrix by means of neural networks has one main drawback: the amount of data required for the proper training of the neural network. This thesis proposes solving this handicap by partitioning the neural network in terms of clusters of independent or almost independent OD pairs. This technique allows an original neural network of a large size to be split into a set of smaller neural networks that are easier to train. Before the clustering problem can be solved, however, the paths that are most likely to be used between each OD pair must be identified.Short-term forecasting leads, in this way, to the critical problem of dynamic traffic assignment, which is solved in this thesis by a microsimulation-based heuristic. In the thesis, some of the most critical aspects of the dynamic simulation of road networks are discussed, namely heuristic dynamic assignment, implied route choice models and the validation methodology, a key issue in determining the degree of validity and significance of the simulation results. The work is divided into two parts: the first provides an overview of how the main features of microscopic simulation were implemented in the microscopic simulator AIMSUN (AIMSUN 2002) and the second is a detailed discussion of heuristic dynamic assignment and sets guidelines for calibrating and validating dynamic traffic assignment parameters. The calibrated and validated simulation model is then used to conduct a dynamic traffic assignment, whose output identifies the paths that are most likely to be used, which will be clustered in subsets that connect the OD pairs and will define the neural networks for the forecast.

The topic of this thesis is the development of SAT-based techniques and tools for solving industrial combinatorial problems. First, it describes the architecture of state-of-the-art SAT and SMT Solvers based on the classical DPLL procedure. These systems can be used as black boxes for solving combinatorial problems. However, sometimes we can increase their efficiency with slight modifications of the basic algorithm. Therefore, the study and development of techniques for adjusting SAT Solvers to specific combinatorial problems is the first goal of this thesis. Namely, SAT Solvers can only deal with propositional logic. For solving general combinatorial problems, two different approaches are possible: - Reducing the complex constraints into propositional clauses. - Enriching the SAT Solver language. The first approach corresponds to encoding the constraint into SAT. The second one corresponds to using propagators, the basis for SMT Solvers. Regarding the first approach, in this document we improve the encoding of two of the most important combinatorial constraints: cardinality constraints and pseudo-Boolean constraints. After that, we present a new mixed approach, called lazy decomposition, which combines the advantages of encodings and propagators. The other part of the thesis uses these theoretical improvements in industrial combinatorial problems. We give a method for efficiently scheduling some professional sport leagues with SAT. The results are promising and show that a SAT approach is valid for these problems. However, the chaotical behavior of CDCL-based SAT Solvers due to VSIDS heuristics makes it difficult to obtain a similar solution for two similar problems. This may be inconvenient in real-world problems, since a user expects similar solutions when it makes slight modifications to the problem specification. In order to overcome this limitation, we have studied and solved the close solution problem, i.e., the problem of quickly finding a close solution when a similar problem is considered.

The frequency of occurrence of an accident is a key aspect in the risk assessment field. Variables such as the human factor, which is a major cause of undesired events in process industries, are usually not considered explicitly, mainly due to the uncertainty related to the lack of knowledge and the complexity associated to it. In this thesis, a frequency modifier has been developed in order to introduce the human factor in the failure frequency estimation. This modifier takes into account variables such as: the organizational factor, the job characteristic factor and the personal characteristic factor. The inclusion of the human factor was done through the application of two methodologies: the fuzzy logic and the Monte Carlo simulation. The first one is based on the operation of the human reason, because of that, the contribution of international experts on the subject area was taken into account through a questionnaire. In the second one, Monte Carlo, the variables are represented by probability functions through a probabilitic treatment. The modifiers were applied to four case studies of real chemical plants: two related to the storage of flammable products and another two dedicated to the toxic and flammable products storage. The new frequency values are considered more realistic and accurate since the human factor is now reflected. In addition, the models were validated with the comparison of the obtained results with a widely international recognized method: the Quantitative Risk Analysis (QRA). Consequently, the final evaluation of the risk is more conservative but in the same line as the results obtained through a QRA. / La frecuencia de los accidentes es un aspecto muy importante en el campo del análisis del riesgo. Variables cómo el factor humano en general no se consideran explícitamente en su evaluación. Esto se debe a la incertidumbre que se genera debido a la falta de información y la complejidad para calcular este factor. No obstante, el factor humano es una de las mayores causas de eventos no deseados en las industrias de proceso. En esta tesis, se desarrolló un modificador de la frecuencia de accidentes con el objetivo de introducir el factor humano en la estimación de riesgo. Este modificador tiene en cuenta variables como: el factor organizacional, el factor de las características del trabajo y el factor de las características personales. La inclusión del factor humano se hizo mediante la aplicación de dos metodologías: La lógica difusa y la simulación de Monte Carlo. La primera de ellas se basa en el funcionamiento del razón humana, por ello fue necesaria la contribución de expertos internacionales en el área de estudio a través de su contribución en un cuestionario. En la segunda, Montecarlo, las variables son representades por funciones de probabilidad a través de un tratamiento probabilístico. Los modificadores fueron aplicados a cuatro casos de estudio de industrias químicas reales: dos relacionados con empresas que almacenan productos inflamables y dos que almancenan productos tóxicos e inflamables. Los nuevos valores de frecuencia, después de aplicar el modificador obtenido, son considerados más realistas debido a que ya incluyen el factor humano. Además, los modelos fueron validados con la comparación de los resultados obtenidos con el método internacionalmente aceptado para la evaluación de riesgo: el Análisis Cuantitativo de Riesgo (ACR). Consecuentemente, la evaluación final de riesgo es más conservadora aunque en la línia de los resultados obtenidos a partir de un ACR.

Aquesta tesi ha estat destacada amb la menció de PREMI EXTRAORDINARI DE DOCTORAT en l'àmbit de MATEMÀTIQUESCurs 1997 - 98 / A la present tesi ens hem ocupat fonamentalment de l'estudi matemàtic dels esquemes per a compartir secrets en les seves vessants de l'estudi de la taxa d'informació i de l'estudi dels esquemes segurs enfront l'acció de mentiders. Com a tema complementari hem estudiat la qüestió de l'arrel cúbica a l'anell dels enters mòdul m. Tots dos temes s'enquadren dins de la Criptologia.Pel que fa l'estudi dels esquemes per a compartir secrets, els nostres objectius han estat la caracterització de les estructures ideals i la fitació de la taxa d'informació òptima per a certes famílies d'estructures d'accés. La primera família estudiada ha estat la de les estructures definides per pesos i llindar. Hem trobat que totes es poden expressar mitjançant pesos i llindar naturals. Hem obtingut una caracterització completa de les de rang 2, és a dir, les que estan determinades per un graf que hem anomenat k-graf. Hem dissenyat un algorisme que les identifica a partir dels graus de cadascun dels vèrtexs i determina els pesos i llindar mínims. A partir de l'estructura d'aquests grafs hem determinat una fita inferior de la taxa d'informació òptima que és de l'ordre de 1/log n (amb n el número de participants), millorant la fita 1/2^{n/2} trobada amb l'únic esquema proposat fins ara per a aquestes estructures, degut a Shamir. A partir d'aquests resultats i mitjançant l'ús del dual d'una estructura hem extés els resultats anteriors a una nova família d'estructures. L'estudi general de les estructures definides per pesos i llindar de rang superior s'ha concentrat en trobar fites superiors i inferiors, especialment per les estructures definides per dos pesos. La segona família que hem estudiat és la de les estructures bipartites. Per les estructures bipartites, hem aconseguit caracteritzar totalment les que són ideals. Aquestes són la família d'estructures de quasi-llindar. Aquesta caracterització de les estructures ideals fa que les estructures de quasi-llindar juguin un paper dins de les estructures bipartites anàleg al paper que juguen els grafs multipartits complets dins de les estructures definides per grafs. Així és equivalent dir que una estructura bipartita és ideal a dir que és de quasi-llindar o a dir que és pot definir amb un esquema d'espai vectorial o a dir que la seva taxa d'informació òptima és més gran que 2/3. Per les estructures bipartites descrivim tècniques típiques de recobriment per tal de trobar fites inferiors de la taxa d'informació. Determinem un algorisme que permet trobar una fita superior de la taxa d'informació. Justifiquem que aquestes fites són ajustades.La següent família d'estructures que hem estudiat ha estat la de les estructures homogènies, obtenint resultats en la fitació inferior de la taxa d'informació. Hem proposat dues construccions d'esquemes per a compartir secrets per estructures homogènies basats en les tècniques de recobriments. Per avaluar les taxes d'informació hem definit el concepte de k-grau d'un participant en una estructura homogènia. Aquest paràmetre és la clau de tot l'estudi de les fites, de les comparacions entre elles i amb les conegudes fins ara. El resultat de la comparació indica que la segona d'elles ens dóna un esquema amb una taxa d'informació millor que la primera, però a canvi la primera utilitza un conjunt de secrets de mesura més realista. La comparació amb les proposades anteriorment mostra que les nostres són millors en la majoria dels casos. L'estudi de les fites superiors per les estructures homogènies l'hem encetat amb les de rang 3, trobant una primera fita superior per una subfamília d'estructures que és del mateix ordre que la fita inferior obtinguda per les nostres construccions. Pels esquemes segurs enfront l'acció de mentiders hem generalitzat els conceptes de seguretat per estructures de llindar al cas d'una estructura qualsevol, tant pel cas en el qual els mentiders no coneixen el secret, com pel cas que sí el coneixen. Hem trobat una fita superior de la taxa d'informació òptima per un esquema en el que una coalició de mentiders és detectada amb una certa probabilitat. Després d'aquest estudi general, hem proposat un esquema per a compartir secrets per a una estructura d'accés de tipus vectorial que detecta l'acció de coalicions de mentiders, que no coneixen el secret, amb una certa probabilitat. La taxa d'informació d'aquest esquema és 1/2, la qual és asímptòticament òptima. Per una estructura de llindar hem proposat un esquema que detecta l'acció de coalicions de mentiders (que sí que coneixen el secret) amb una certa probabilitat. Finalment hem trobat el primer esquema per a una estructura qualsevol que detecta l'acció de coalicions de mentiders (que no coneixen el secret) amb una certa probabilitat.Pel que fa a l'arrel cúbica en el conjunt dels enters mòdul m, hem estudiat l'existència i número d'arrels. Hem generalitzat dos mètodes, dels més potents, pel càlcul de l'arrel quadrada per arrel cúbiques. Aquests són el mètode de Peralta basat en l'ús d'un anell auxiliar i el mètode de Tonelli-Shanks basat en l'ús de subgrups de Sylow. S'ha adjuntat algun comentari per les aplicacions criptogràfiques de les arrels cúbiques. / This thesis is mainly devoted to the study of information rate of secret sharing schemes as well as secret sharing schemes secures against the action of cheaters. As a complement we have studied the problem of cube roots in Z_m.In the first part of our work we study some access structures in a combinatorial way and the boundness of the optimal information rate. We begin with weighted threshold access structures. We state that any of them can be defined with positive integer weights and threshold. We characterize all the rank 2 weighted threshold access structures as a k-graphs, finding minimum integer weights and threshold. We bound the optimal information rate using the complete multipartite covering technique. We extend the above results on characterization and computation of minimum weights and threshold to dual structures after proving the fact that the dual of a weighted threshold structure is a weighted threshold structure. The second family of structures that we studied is the bipartite access structures. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. We prove that in a bipartite access structure it is equivalent ideal structure, vector space structure and optimal information rate of the structure less than 2/3. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. We also start the general study of multipartite access structure.Using results on bipartite structures we study the information rate of secret sharing schemes whose access structure is defined by two weights and a threshold of arbitrary rank. Some upper and lower bounds are found. Case on more than two weights is considered too.The last family of access structure that we have studied is the homogeneous access structure. We describe two constructions of secret sharing schemes for a such a general class of structures. The first one has a worst information rate than the second one, but on the other hand the size of the secret set is more moderate than the first one. We describe the comparison between our lower bounds on the optimal information rate and on the optimal average information rate as well as comparison with known upper bounds. The results are that our second one are better than the first one and that our bounds are better than the known bound almost for every structure.We have started a study of the upper bounds on the optimal information rate for rank 3 homogenous access structures. We describe a structure that its upper bound is not so far than the lower bound obtained with our second construction.Concerning to the extended capabilities we have studied the schemes secures against the action of cheaters. We have generalized the concepts of secure scheme and robust scheme to any access structure, that several authors have already defined only for threshold structures. We found that for a secure scheme the optimal information rate is upper bounded and we find the bound. We construct a 1/q-secure scheme (for q secrets) asymptotically optimal for a vector space access structure. We compare this scheme with the scheme of Ogata and Kurosawa. Our second scheme is robust realizing a (r,n) threshold structure with probability <= (2r-3)/(q-r). The information rate is 1/3. Finally we propose the first 1/q-secure scheme for any access structure.We have generalized two of the fastest algorithms to take square roots to cube roots in Z_p. The first one is Peralta's algorithm, a probabilistic algorithm based on some properties of a ring. The non probabilistic part of the algorithm runs in log^3 p. The second one is Tonelli-Shanks' algorithm, a probabilistic method based on group theory which runs in log^4 p.

Un aspecte fonamental quan cal resoldre un problema vibroacústic en un sistema mecànic és el de determinar com flueix l’energia des d’una font donada, cap a qualsevol part del sistema. Això permet decidir quines són les accions a prendre per disminuir, per exemple, els nivells de soroll i vibracions en una determinada àrea del sistema. El comportament dinàmic d’un sistema mecànic es pot estimar utilitzant diversos mètodes numèrics, cadascun dels quals enfocat a un marge de freqüència determinat. Mentre a baixes freqüències es poden aplicar mètodes deterministes com el Mètode d’Elements Finits (FEM) o el Mètode d’Elements de Contorn (BEM), a altes freqüències, els mètodes estadístics com l’Anàlisi Estadística Energètica (SEA), esdevenen inevitables. A més a més, diverses tècniques com el FE-SEA híbrid, els models de Distribució Energètica (ED) o l’Anàlisi Estadística de distribució d’Energia modal (SmEdA), entre d’altres, han estat recentment plantejades per tal de tractar amb l’anomenat problema de les mitges freqüències. Tanmateix, encara que alguns mètodes numèrics poden predir la resposta vibroacústica puntual o amitjanada d’un sistema, aquests no proporcionen de forma directa informació sobre com flueix l’energia per tot el sistema. Per tant, cal algun tipus de post-processament per a determinar quines són les vies de transmissió d’energia. L’energia transmesa a través d’un determinat camí que connecti un subsistema font, on l’energia és introduïda, i un subsistema receptor, es pot calcular numèricament. Tot i això, la identificació dels camins que dominen la transmissió d’energia des d’una font fins a un receptor normalment acostuma a basar-se en l’experiència i el parer de l’enginyer. Així doncs, un mètode que permeti obtenir aquests camins de forma automàtica resultaria molt útil. La teoria de grafs proporciona una sortida a aquest problema, ja que existeixen diversos algorismes de càlcul de camins en grafs. En aquesta tesi, es proposa un enllaç entre els models vibroacústics i la teoria de grafs, que permet adreçar els problemes de vies de transmissió de forma directa. La dissertació comença centrant-se en els models SEA. Primerament, es mostra que té sentit realitzar una anàlisi de vies de transmissió (TPA) en SEA. Seguidament, es defineix un graf que representa de forma acurada els models SEA. Tenint en compte que la transmissió d’energia entre fonts i receptors es pot justificar mitjançant la contribució d’un grup finit de vies dominants en varis casos d’interès, es presenta un algorisme per calcular-les. A continuació, s’implementa un algorisme que inclou en el càlcul de camins la naturalesa estocàstica dels factors de pèrdues SEA. Tot seguit, es tracta com es pot estendre l’anàlisi de vies de transmissió al marge de la mitja freqüència. L’aplicació de la teoria de grafs a les mitges freqüències s’adapta per alguns models ED, així com també SmEdA. Finalment, es presenta una altra possible aplicació de la teoria de grafs en vibroacústica. S’implementa una estratègia basada en algorismes de talls en grafs per tal de reduir l’energia en un subsistema receptor amb la modificació d’un grup reduït de factors de pèrdues. Aquest grup de variacions, es troba calculant talls en el graf que separin els subsistemes fonts dels receptors. / A fundamental aspect when solving a vibroacoustic problem in a mechanical system is that of finding out how energy flows from a given source to any part of the system. This would help making decisions to undertake actions for diminishing, for example, the noise or vibration levels at a given system area. The dynamic behavior of a mechanical system can be estimated using different numerical methods, each of them targeting a certain frequency range. Whereas at low frequencies deterministic methods such as the Finite Element Method (FEM) or the Boundary Element Method (BEM) can be applied, statistical methods like Statistical Energy Analysis (SEA) become unavoidable at high frequencies. In addition, a large variety of approaches such as the hybrid FE-SEA, the Energy Distribution (ED) models or the Statistical modal Energy distribution Analysis (SmEdA), among many others, have been recently proposed to tackle with the so-called mid-frequency problem. However, although numerical methods can predict the pointwise or averaged vibroacoustic response of a system, they do not directly provide information on how energy flows throughout the system. Therefore, some kind of post-processing is required to determine energy transmission paths. The energy transmitted through a particular path linking a source subsystem, where external energy is being input, and a target subsystem, can be computed numerically. Yet, identifying which paths dominate the whole energy transmission from source to target usually relies on the engineer's expertise and judgement. Thus, an approach for the automatic identification of those paths would prove very useful. Graph theory provides a way out to this problem, since powerful path algorithms for graphs are available. In this thesis, a link between vibroacoustic models and graph theory is proposed, which allows one to address energy transmission path problems in a straightforward manner. The dissertation starts focusing on SEA models. It is first shown that performing a transmission path analysis (TPA) in SEA makes sense. Then a graph that accurately represents the SEA model is defined. Given that the energy transmission between sources and targets is justified by the contribution of a limited group of dominant paths in many cases of practical interest, an algorithm to find them is presented. Thereafter, an enhanced algorithm is devised to include the stochastic nature of SEA loss factors in the ranking of paths. Next, it is discussed how transmission path analysis can be extended to the mid frequency range. The graph approach for path computation becomes adapted for some ED models, as well as for SmEdA. Finally, we outline another possible application of graph theory to vibroacoustics. A graph cut algorithm strategy is implemented to achieve energy reduction at a target subsystem with the sole modification of a reduced set of loss factors. The set is found by computing cuts in the graph separating source and receiver subsystems. / Un aspecto fundamental a la hora de resolver un problema vibroacústico en un sistema mecánico es el de determinar cómo fluye la energía desde una determinada fuente hasta cualquier parte del sistema. Ello ayudaría a tomar decisiones para emprender acciones destinadas a disminuir, por ejemplo, los niveles de ruido y vibraciones en un área del sistema dada. El comportamiento dinámico de un sistema mecánico se puede estimar utilizando varios métodos numéricos, cada uno de ellos enfocado a un determinado rango de frecuencia. Mientras en las bajas frecuencias se pueden aplicar métodos deterministas como el Método de los Elementos Finitos (FEM) o el método de Elementos de Contorno (BEM), los métodos estadísticos como el Análisis Estadístico Energético son inevitables en las altas frecuencias. Además, se han desarrollado gran variedad de técnicas como el FE-SEA híbrido, los modelos de Distribución de Energía (ED) o el Análisis Estadístico de distribución de Energía modal (SmEdA), entre otras, para tratar el llamado problema de las medias frecuencias. Sin embargo, aunque los métodos numéricos pueden predecir la respuesta vibroacústica puntual o promediada de un sistema mecánico, ellos no proporcionan información sobre como fluye la energía en el sistema. Por lo tanto, hace falta algún tipo de post-procesado para determinar las vías de transmisión de energía. La energía transmitida a través de un determinado camino que conecta un subsistema fuente, donde se introduce la energía, y un subsistema receptor, se puede calcular numéricamente. A pesar de ello, identificar qué caminos dominan la transmisión de energía desde la fuente al receptor normalmente suele recaer en la experiencia o el juicio del ingeniero. Así pues, un método automático para identificar estos caminos resultaría muy útil. La teoría de grafos proporciona una solución a este problema, ya que existen potentes algoritmos de cálculos de caminos en grafos. En esta tesis, se propone un enlace entre los modelos vibroacústicos y la teoría de grafos, que permite abordar los problemas de vías de transmisión de forma directa. La disertación empieza centrándose en los modelos SEA. Primeramente, se muestra que tiene sentido realizar un análisis de vías de transmisión (TPA) en un modelo SEA. Seguidamente, se define un grafo que representa fielmente un modelo SEA. Teniendo en cuenta que en muchos casos de interés práctico, la transmisión de energía entre fuentes y receptores se puede justificar mediante la contribución de un grupo finito de vías de transmisión, se define un algoritmo para encontrarlas. A continuación, se implementa un algoritmo que incluye en el cómputo de caminos la naturaleza estocástica de los factores de pérdidas SEA. Luego, se trata la extensión del análisis de vías de transmisión al rango de media frecuencia. La técnica de teoría de grafos aplicada a cálculo de caminos se adapta para algunos modelos ED y también SmEdA. Finalmente, se presenta otra posible aplicación de la teoría de grafos a la vibroacústica. Se implementa una estrategia basada en algoritmos de cortes en grafos destinada a reducir la energía en un subsistema receptor mediante la simple modificación de un grupo reducido de factores de pérdidas. El grupo se encuentra calculando cortes que separen en el grafo los subsistemas fuentes de los subsistemas receptores.

En la presente tesis se analiza el problema del coloreado de grafos tanto desde el punto de vista teórico como en relación a la resolución del problema mediante técnicas algorítmicas, algunas de las cuales se describen por vez primera. Se estudian asimismo distintas variaciones del problema simple del coloreado incluyendo el coloreado de vértices etiquetados, en que se asigna un número variable de colores a cada vértice, y el coloreado con aristas etiquetadas, en el que los colores asignados a vértices adyacentes deben guardar una distancia mayor o igual a la etiqueta de la arista que los une, así como combinaciones de ambos.Las técnicas descritas para el coloreado de grafos han sido posteriormente adaptadas a un problema de asignación de frecuencias en telefonía móvil habiéndose aplicado los algoritmos sobre distintos tipos de redes celulares. Las distintas redes analizadas pueden incorporar o no conmutación en frecuencia, variando la naturaleza del problema en cada caso. Para el caso de coloreado múltiple asociado al problema de asignación de frecuencias se ha descrito un conjunto de matrices asociadas a un grafo G(V,E) y un coloreado simple C que permiten reasignar colores a distintos vértices de G(V,E) aprovechando colores de C. Este reciclaje, en combinación con las métodos algorítmicos aplicados en coloreados simples, ha permitido resolver con eficiencia el problema del multicoloreado de grafos y en consecuencia el problema de asignación de frecuencias en redes celulares.En la segunda parte de la tesis se estudian las redes pequeño-mundo y se describen pautas deterministas para su obtención. De este modo se describe en primer lugar el modelo probabilista definido por Watts y Strogatz y se analiza la aparición de autoorganización crítica en las redes pequeño-mundo (caracterizadas por un apiñamiento elevado y un diámetro o distancia máxima entre vértices reducido) para a continuación ampliar el concepto sobre modelos deterministas. Se ha demostrado de este modo la posibilidad de obtener redes pequeño-mundo sobre grafos circulantes, mallas toroidales e hipercubos.Finalmente se ha probado la universalidad del efecto pequeño-mundo, es decir, la posibilidad de recortar arbitrariamente el diámetro de un grafo genérico G(V,E) sin que se produzcan variaciones significativas en su topología local (medida a partir del factor de clustering o apiñamiento del grafo), explicando así la ubicuidad de las redes pequeño-mundo y su descripción en entornos de todo tipo: social, biológico, industrial, matemático, etcétera.

El Problema de Enrutamiento de Vehículos (VRP) y sus diferentes variantes básicas son un dominio ampliamente estudiado en la comunidad científica de optimización. Algunos estudios han utilizado combinaciones específicas de restricciones encontradas en la vida real para definir los emergentes VRP Enriquecidos. Este trabajo aborda la integración de heurísticas, probabilidad sesgada, simulación, técnicas de computación distribuida & paralelas, y programación con restricciones. Los enfoques propuestos han solucionado algunas variantes del VRP: en primer lugar, las familias deterministas: VRP con flotas Heterogéneas (HVRP), VRP con flotas Heterogéneas y costo variable (HVRP-V), VRP con flota Heterogénea y Múltiples viajes (HVRPM), VRP con matriz de costo Asimétrica (AVRP), VRP con flota Heterogénea y matriz de costo Asimétrica (HAVRP), VRP con ventanas de Tiempo (VRPTW), y VRP Distancia limitada (DCVRP); en segundo lugar, las familias de naturaleza estocástica: VRP con Demandas estocásticas (VRPSD), y Problemas de Inventario y Enrutamiento de Vehículos con Demandas estocásticas (IRPSD). Una extensa revisión bibliográfica se ha realizado para cada una de estas variantes. Un primer enfoque propone la combinación de una aleatorización sesgada con heurísticas clásicas para la solución de problemas deterministas. Un segundo enfoque se centra en la combinación de heurísticas aleatorias con simulación (Simheuristics) para ser aplicados sobre los problemas estocásticos comentados. Por último, se propone un tercer enfoque basado en el trabajo conjunto de heurísticas aleatorias con programación de restricciones para resolver varios tipos de problemas de enrutamiento. Los algoritmos heurísticos desarrollados han sido aplicados en varios casos de referencia --entre ellos, dos estudios de casos reales de distribución en España-- y los resultados obtenidos son, en general, prometedores y útiles para los decisores. / The Vehicle Routing Problem (VRP) is a well known domain in optimization research community. Its different basic variants have been widely explored in the literature. Some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work deals with the integration of heuristics, biased probability, simulation, parallel & distributed computing techniques, and constraint programming. The proposed approaches are tested for solving some variants of VRPs, namely, first, the deterministic families: Heterogeneous VRP (HVRP), Heterogeneous VRP with Variable cost (HVRP-V), Heterogeneous fleet VRP with Multi-trips (HVRPM), Asymmetric cost matrix VRP (AVRP), Heterogeneous fleet with Asymmetric cost matrix VRP (HAVRP), VRP with Time Windows (VRPTW), and Distance-Constrained VRP (DCVRP); second, the stochastic nature families: VRP with Stochastic Demands (VRPSD), and Inventory Routing Problem with Stochastic Demands (IRPSD). An extensive literature review is performed for all these variants, focusing on the main contributions of each work. A first approach proposes a biased-randomization of classical heuristics for solving the deterministic problems addressed here. A second approach is centered on the combination of randomized heuristics with simulation (Simheuristics) to be applied on the commented stochastic problems. Finally, a third approach based on the joined work of randomized heuristics with constraint programming is proposed to solve several types of routing problems. The developed heuristic algorithms are tested in several benchmark instances --between these, two real-life case studies in Spain are considered-- and the results obtained are, on average, highly promising and useful for decision makers.