Search

Este Trabajo Final de Grado explora la determinación de la dimensión métrica de varios grafos para los que ciertos investigadores han proporcionado cotas o no han investigado a fondo. La dimensión métrica de un grafo es un concepto bien conocido en teoría de grafos, representando el número mínimo de vértices necesarios para identificar de manera única todos los demás vértices en el grafo usando distancias. Este estudio tiene como objetivo ampliar el conocimiento actual y potencialmente descubrir cotas más estrictas para la dimensión métrica. Para lograr esto, utilizaremos "solvers", que son herramientas computacionales poderosas para resolver problemas NP-Completos. A través de un análisis exhaustivo de diferentes grafos y sus métricas asociadas, esta investigación contribuye a la comprensión de la dimensión métrica y proporciona valiosos conocimientos para futuras investigaciones en teoría de grafos., This undergraduate thesis explores the determination of the metric dimension of various graphs for which certain researchers have provided bounds or have not thoroughly investigated. The metric dimension of a graph is a well-known concept in graph theory, representing the smallest number of vertices required to uniquely identify all other vertices in the graph using distances. This study aims to extend the current knowledge and potentially discover tighter bounds for the metric dimension. To achieve this, we will make use of solvers, which are powerful computational tools for solving NP-Complete problems. Through a comprehensive analysis of different graphs and their associated metrics, this research contributes to the understanding of the metric dimension and provides valuable insights for future investigations in graph theory.

En aquests últims anys, la manera de realitzar estudis de mercat ha canviat radicalment. La informació que s'aconseguia abans en una setmana, demanant l'opinió de la gent pel carrer o a través de trucades telefòniques, ara es pot fer en qüestió d'hores a través d'aplicacions de mòbil. A més, permet aconseguir molta més informació valuosa que abans era impossible sense fer una inversió molt gran, com aconseguir opinions de persones d'un altre país. Ara bé, aquest canvi comporta també nous reptes que s'han de superar per mantenir la qualitat dels estudis. Un d'aquests reptes és assegurar que els demogràfics de la mostra utilitzada en l'estudi estan distribuïts correctament. En aquest treball, s'estudia aquest problema en concret, buscant tant la solució òptima fent un seguit d'assumpcions, com una solució per al cas real que pugui ser utilitzada sense alentir el procés ni haver de malgastar molts recursos. Per aconseguir-ho, s'han utilitzat les dades d'una empresa espanyola del sector, Zinklar, qui està interessada a utilitzar els resultats obtinguts per millorar la gestió del servei que ofereixen., In recent years, the way market research is conducted has changed dramatically. The information that used to be obtained in a week, by asking people on the street or through phone calls, can now be gathered in a matter of hours via mobile applications. Furthermore, it allows for the collection of much more valuable information that was previously impossible without making a significant investment, such as obtaining opinions from people in another country. However, this change also brings new challenges that must be overcome to maintain the quality of the studies. One of these challenges is ensuring that the demographics of the sample used in the study are correctly distributed. This TFG is focused on this problem, seeking both the optimal solution making a series of assumptions, and a solution for the real case that can be used without slowing down the process or wasting many resources to achieve it. To achieve this, Zinklar, a Spanish company in the sector who is interested in using the obtained results to improve the management of the service they offer, has provided the needed data.

Dins el domini dels mercats financers, les operacions se solen categoritzar en llarg i en curt, segons les expectatives sobre les tendències futures dels preus. Una característica distintiva de certs actius és la reversió a la mitjana, on els preus tendeixen a retornar a una mitjana amb el temps. Encara que aquesta característica no és comuna, pot induir-se en actius "sintètics" mitjançant combinacions lineals d'actius individuals que no exhibeixen aquesta propietat, en un fenomen conegut com a cointegració. Aquest projecte aspira a desenvolupar eines basades en programació lineal entera mixta, utilitzant Gurobi, per identificar combinacions lineals d'actius, representats com a sèries temporals, que exhibeixen reversió a la mitjana de manera estadísticament significativa. A través de l'organització de transaccions en llarg i en curt d'aquests actius sintètics, es proposen estratègies d'inversió que capitalitzen la dinàmica de la reversió a la mitjana i minimitzen riscos., Within the domain of financial markets, operations are usually categorized as long and short, based on expectations regarding future price trends. A distinctive characteristic of certain assets is the mean reversion, where prices tend to return to a mean over time. Although this characteristic is not common, it can be induced in "synthetic" assets through linear combinations of individual assets that do not exhibit this property, in a phenomenon known as cointegration. This project aims to develop tools based on mixed integer linear programming, using Gurobi, to identify linear combinations of assets, represented as time sèries, that exhibit mean reversion in a statistically significant manner. Through the organization of long and short transactions of these synthetic assets, investment strategies are proposed that capitalize on the dynamics of mean reversion and minimize risks.

El sector de edificios representa alrededor de un tercio de la energía relacionada con las emisiones de gases de efecto invernadero (GEI) de la UE, convirtiéndolo en un sector crucial para alcanzar los objetivos energéticos y medioambientales de la UE. Por ende, la UE ha establecido un marco legislativo para fomentar la integración de tecnologías verdes y mejorar el rendimiento energético en los edificios. En este sentido, considerando las necesidades de rehabilitación de los edificios públicos en España, y en particular en Catalunya, este trabajo propone la optimización de un sistema de poligeneración para el edificio TR5 de la UPC ubicado en Terrassa. Esta se lleva a cabo usando un modelo de Programación Lineal Entera Mixta para optimizar económicamente el sistema bajo distintos escenarios. Los resultados muestran la viabilidad del uso de fotovoltaica en todos los escenarios, mientras que otras tecnologías como los colectores solares térmicos, almacenamientos energéticos, entre otros, no lo son. Por otro lado, la configuración óptima cambia según los precios de la energía, pero también el impacto ambiental. En particular, los precios más altos del gas natural conducen a reducir las emisiones de GEI, mientras que precios más altos de electricidad no conllevan a ello necesariamente., Los autores agradecen la financiación por parte de la Universidad Politécnica de Catalunya y su apoyo durante la ejecución de este trabajo. El autor Edwin S. Pinto agradece la financiación de las ayudas Margarita Salas proveniente de los fondos Europeos UnionNext Generation y del Ministerio de Universidades de España., Peer Reviewed, Postprint (author's final draft)

Many real-life problems can be expressed as a set of restrictions. If those restrictions can be satisfied, then there's a solution to the problem, otherwise, the problem can be classified as not solvable. The set of those problems that can be codified using boolean formulas, that is to say, where the variables of the problems can take the values 0 and 1, are wildly known as SATISFIABILITY (SAT) problems. Therefore, if a program is capable of assigning values to the variables such that all the restrictions of a given problem are satisfied, then the solution to the problem is found. Although many problems can be easily represented this way, deciding whether there's a solution to the problem or giving a solution if it exists is not easy to compute. SAT is the first family of problems proven to be NP-Complete by Stephen Cook and Leonid Levin. Therefore, there's no known algorithm that runs in polynomial time capable of solving this kind of problem. This project tries to transform the SAT problem into an LP problem, as well as applying preprocessing techniques to express the information in a more optimized way for the LP solver.

Los Sistemas Inteligentes de Transporte están cambiando la forma en que concebimos el futuro de la movilidad. En particular, los ferrocarriles están experimentando un proceso de transformación para modernizar el transporte público y las operaciones ferroviarias. Tecnologías como el 5G, la fibra óptica y la nube han surgido como catalizadores para digitalizar el ferrocarril proporcionando comunicaciones de alta velocidad y baja latencia. Este TFG se centra en la exploración de redes que permitan el control del tren y la transmisión de datos a bordo. El objetivo es planificar la infraestructura de red (dimensionamiento y asignación de recursos) necesaria para las futuras comunicaciones del sistema ferroviario de larga distancia de la Deutsche Bahn en Alemania. En este trabajo, proponemos una arquitectura de red que puede satisfacer los requisitos de rendimiento de las aplicaciones para trenes y pasajeros. Presentamos un método para la colocación de estaciones base 5G a lo largo de las vías del tren para garantizar el rendimiento necesario en el borde de la celda. Por último, presentamos el problema de colocación y asignación de centros de datos. El objetivo es encontrar el número necesario de centros de datos y su ubicación en la red, y asignarlos a cada estación de tren. Realizamos simulaciones en cuatro escenarios diferentes, en los que modificamos parámetros de entrada como la latencia máxima tolerada y el número máximo de centros de datos. Los resultados obtenidos muestran el compromiso entre la latencia alcanzada y el coste de la infraestructura., Els Sistemes Intel·ligents de Transport estan canviant la manera en què concebem el futur de la mobilitat. En particular, els ferrocarrils estan experimentant un procés de transformació per modernitzar el transport públic i les operacions ferroviàries. Tecnologies com el 5G, la fibra òptica i el núvol han sorgit com a catalitzadors per digitalitzar el ferrocarril proporcionant comunicacions d'alta velocitat i baixa latència. Aquest TFG se centra en l'exploració de xarxes que permetin el control dels trens i la transmissió de dades a bord. L'objectiu és planificar la infraestructura de xarxa (dimensionament i assignació de recursos) necessària per a les futures comunicacions del sistema ferroviari de llarga distància de la Deutsche Bahn a Alemanya. En aquest treball, proposem una arquitectura de xarxa que pot satisfer els requisits de rendiment de les aplicacions per a trens i passatgers. Presentem un mètode per a la col·locació d'estacions base 5G al llarg de les vies del tren per garantir el rendiment necessari a la vora de la cel·la. Per últim, presentem el problema de col·locació i assignació de centres de dades. L'objectiu és trobar el nombre necessari de centres de dades i la seva ubicació a la xarxa, i assignar-los a cada estació de tren. Realitzem simulacions en quatre escenaris diferents, on modifiquem paràmetres d'entrada com la latència màxima tolerada i el nombre màxim de centres de dades. Els resultats obtinguts mostren el compromís entre la latència assolida i el cost de la infraestructura., Smart Transportation Systems are changing the way we conceive the future of mobility. In particular, railways are undergoing a transformation process to modernize public transportation and rail operation. Technologies like 5G, optical fiber and the cloud have emerged as catalysts to digitalize the railway by providing high-speed and low-latency communications. This bachelor's thesis focuses on the exploration of networks enabling train control and on-board data communications. The goal is to plan the network infrastructure (dimensioning and resource allocation) needed for the future communications in the train mobility scenario for Deutsche Bahn's long-distance railway system in Germany. In this work, we propose a network architecture that can meet the performance requirements of train and passenger applications. We present an approach for 5G base station placement along the rail tracks to guarantee the necessary throughput at the cell edge. Finally, we introduce the data center placement and assignment problem. The objective is to find the required number of data centers and their location in the network, and to assign them to each train station. We perform simulations in four different scenarios, in which we modify input parameters such as the maximum tolerated latency and the maximum number of data centers. The obtained results show the trade-off between the achieved latency and the infrastructure cost.

[ES] Chile actualmente cuenta con alto déficit de edificación habitacional, especialmente en sectores socio económicos vulnerables de la sociedad. Ante esta situación el estado ha aplicado una política subsidiaria que permita a las personas acceder a una vivienda en propiedad. Paralelamente a esta situación, el país ha ido adquiriendo compromisos cuyo objetivo es la reducción del impacto ambiental de las actividades económicas desarrolladas en el país. Los esfuerzos en la reducción del impacto ambiental se han centrado en disminuir las emisiones de gases de efecto invernadero, lo cual puede implicar transformaciones en los procesos productivos de los países asociados a nuevas inversiones. Esto puede originar una pérdida de competitividad en las economías emergentes en caso de no verse capaces de adaptar su matriz productiva. Una forma de reducir el impacto ambiental de los productos es la reducción de su huella energética, a través de una selección adecuada de materiales que lleven un menor impacto ambiental incorporado. El objetivo de este TFM es buscar una combinación óptima de materiales que permita reducir la huella energética de las viviendas objeto de la política subsidiaria del país y que, a la vez, permita mejorar las condiciones de confort térmico que estas entregan, centrándose en la parte opaca de la envolvente de la vivienda estudiada. La solución propuesta se determinará mediante el empleo de técnicas de optimización matemática que busquen la mejor combinación entre los materiales disponibles en el mercado chileno., [EN] Currently in Chile there is a high lack of residentials buildings, especially on society’s vulnerable socioeconomic people. To deal with this problem, the estate of Chile has applied a subsidiary policy which has made possible getting a home. Concurrently to this situation, Chile has been getting commitments whose purpose is to minimize the environmental impact of economic activities of the country. The efforts of reducing environmental impact have been focused on reducing greenhouse gases emissions. This may need transformations on countries’ productive process which may imply investments. This could cause a lack of competitiveness on emerging economies who could not be able of adapting its productive matrix. Reducing energy footprint of products is a way of minimizing its environmental impact, through a better selection of their materials which imply a lower environmental impact associated. The aim of this work is finding an optimal combination of materials that allows a reduction of social interest homes’ energy footprint and permits to improve the thermal comfort that they give. This study will be focused on the opaque part of the building’s envelope. The proposal will be determined by using mathematical optimization techniques which look for the best combination among materials available on Chilean market., [CA] Xile actualment compta amb un alt dèficit d'edificació residencial, especialment en sectors socioeconòmics vulnerables de la societat. Davant d’aquesta situació l'estat ha aplicat una política subsidiària que permeta a les persones accedir a un habitatge en propietat. Paral·lelament a aquesta situació, el país ha anat adquirint compromisos amb l'objectiu de reduir l'impacte ambiental de les activitats econòmiques desenvolupades al país. Els esforços en la reducció de l'impacte ambiental s'han centrat a en disminuir les emissions de gasos d'efecte d'hivernacle, la qual cosa pot implicar transformacions en els processos productius dels països associats a noves inversions. Això pot originar una pèrdua de competitivitat en les economies emergents en cas de no veure's capaces d'adaptar la seua matriu productiva. Una manera de reduir l'impacte ambiental dels productes és la reducció de la seua petjada energètica, a través d'una selecció adequada de materials que comporten un menor impacte ambiental incorporat. L'objectiu d'aquest TFM és buscar una combinació òptima de materials que permeta reduir la petjada energètica dels habitatges objecte de la política subsidiària del país i que, alhora, permeta millorar les condicions de confort tèrmic que aquests oferixen, centrant-se en la part opaca de l'envolupant de l'habitatge estudiat. La solució proposada es determinarà mitjançant l'ús de tècniques d'optimització matemàtica que busquen la millor combinació entre els materials disponibles en el mercat xilé.

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., First author partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936., Peer Reviewed, Postprint (author's final draft)

We use real-time time-dependent density functional theory simulations to numerically demonstrate that resonantly enhanced differencefrequency generation (re-DFG) involving intense ultrashort coherent X-ray pulses can selectively excite core states of atoms in molecules. As a model case, we evaluate the spectral selectivity of re-DFG excitation of the oxygen K-edge by illumination of a single gas-phase water molecule with two-color X-ray pulses of different photon energies and durations. The re-DFG excitation is further probed by a small delayed pulse with central photon energy resonant with the oxygen K-edge peak absorption line. Based on these results, we anticipate that highly selective excitation by re-DFG X-ray nonlinear processes might be achieved in more complex molecular systems and bulk materials by using highly penetrating two-color hard X-ray pulses, with extensive applications, Postprint (published version)

Parallel Assembly Lines with multi-line stations (PALBs) have been widely studied in recent years because PALBs can help improve the efficiency of a production system. However, the need of buffers has not been considered in the PALBP literature. In this study, for the first time in the literature, it is shown and demonstrated the need to consider the use of buffers in this type of line when their cycle times are different. Moreover, the buffer sizing problem in a multi-line workstation is presented and formalized. It is shown that the sequencing and scheduling of the task influences the buffer size. Finally, the designed resolution method is shown: solve a mixed integer linear programming model with a commercial software, with the objective of minimizing the size of the buffers., Peer Reviewed, Postprint (published version)

Purpose: The actual market characteristic oriented toward customers’ requirements compels decision-makers to foresee customization abilities. Mass customization represents a valuable approach to combinecustomizable offers with mass production processes. From a supply chain standpoint, this paper attemptsto develop an integrated procurement, production and distribution modeling to describe the generatedframework structure formulation within tactical decision planning level.Design/methodology/approach: The paper provides a mixed integer linear programming model of athree echelon supply chain illustrated from the automotive industry with (a) customers: OriginalEquipment Manufacturers (OEMs) identified as leaders and (b) first-tier supplier: wiring harnessesmanufacturer (c) second-tier suppliers: raw material suppliers, identified as followers. The modelformulation is depicted through dyadic relationships between stakeholders considering the specificoperation enablers of the environment such as make to order, modular approach in addition to thecorresponding inventory management policy.Findings: The integrated model is solved by an exact method which illustrates the feasibility of theformulation in addition to the observance of the applied constraints. A sensitivity analysis is performed tohighlight the interdependency across some key parameters to provide managerial insights within thestudied framework while keeping the optimal solvability of the model.Research limitations/implications: The limitation of this study is the computational experiment study.An extensive experiment with a real-word case will outline the optimal solvability status of the exactmethod and the necessity for a performance benchmark through the approximate solving approaches.Originality/value: The present research aims to contribute as first studies toward mathematical modelingfor supply chain decision planning endeavor operating within mass customization business model, Peer Reviewed

Disaggregated DCs offer multiple benefits. However, transmission capacity limitations at blade level can severely degrade their performance. We analyze several strategies to enhance their service acceptance., The presented work has been supported by the Spanish Government through project ALLIANCE-B (TEC2017-90034-C2-2-R) with FEDER contribution., Peer Reviewed, Postprint (published version)

Assembly lines are mass production systems which are significant in the industrial production of both standard and customised products. Currently, industrial companies offer several products and it is common for an assembly system to have multiple assembly lines. Parallel assembly lines are multiple lines located in such a way as to allow improvements in the system’s efficiency through the use of common resources. In recent years several research studies have been made on parallel assembly lines. In this paper, we survey the parallel assembly lines balancing problem (PALBP) studies. Moreover, a classification scheme is provided to ease understanding. Finally, the main gaps in the literature are described and future research directions are presented., Peer Reviewed, Postprint (author's final draft)

Aquest treball de final de màster vol desenvolupar per a diferents escenaris proposats una solució efectiva per a la producció i transport entre fàbriques i delegacions comercials d’una empresa productora de pa congelat i altres productes alimentaris. També es descriu breument el procés de fabricació del pa per tal de contextualitzar el treball en la formació prèvia en el Grau d’ Enginyeria Química que vaig cursar a l’ETSEIB. L’objectiu principal del treball és establir un model de programació lineal que optimitzi el cost de producció i transport de diferents productes en funció d’una demanda i unes restriccions de capacitat dels centres productius i les delegacions comercials. Es tracta d’establir un model matemàtic a nivell estratègic que permeti respondre les principals preguntes de “què, quant i on” fabricar i transportar. En una segona fase, mitjançant la transcripció del model en llenguatge OPL del programari IBM © ILOG © CPLEX es fan diferents simulacions de diversos escenaris de demanda per veure si es té prou capacitat i pels casos sense solució factible, s’han proposat diferents solucions per a no diferir la demanda. Finalment s’ha proposat un model matemàtic més complet que incorpora nous elements com els magatzems pulmó i la possibilitat de transportar producte entre fàbriques per a una futura ampliació del treball actual.

Se presenta un modelo de PLEM para minimizar el coste de almacenamiento de elementos combustibles nucleares gastados en contenedores tipo MPC-32 procedentes de la piscina de una central nuclear. La carga de contenedores se realiza en una sola etapa y en una fecha concreta., En la gestión de residuos de combustible de las centrales nucleares españolas, está previsto activar los almacenes temporales individualizados (ATI) cuando se alcanza la saturación de la piscina destinada a albergar elementos de combustible nuclear gastado durante el periodo de explotación de la instalación; al finalizar dicho periodo, un ATI puede utilizarse como almacén transitorio a corto o largo plazo hasta que el almacén temporal central (ATC) esté disponible. Los elementos combustibles (EC), gastados y ubicados en la piscina de la central nuclear (CN), se seleccionan para su almacenado en seco en contenedores (cápsulas) atendiendo a una serie de restricciones impuestas a cada ATI por el órgano regulador competente en función de los requerimientos que afectan específicamente a los contenedores utilizados (v.gr. la limitación de la carga térmica o el número de posiciones para elementos combustibles). Las características de estas cápsulas condicionan el tiempo mínimo de enfriamiento del combustible en la piscina de la central nuclear y, por consiguiente, el tiempo necesario para completar el vaciado completo de dicha piscina. En este contexto, presentamos un modelo de programación lineal entera mixta (Mixed Integer Linear Programming) con el objetivo de minimizar, en una sola carga de elementos con fecha preestablecida, el coste de utilización de las cápsulas MPC (Multi Purpose Canister) necesarias para reubicar en un almacén ATI el número máximo de elementos de combustible gastado que están disponibles en la piscina de la central en tal fecha. El modelo propuesto se ha explotado mediante el solucionador CPLEX utilizando un caso de estudio inspirado en la realidad de la CN Ascó ubicada a unos 160 km de Barcelona. El método de resolución que proponemos es capaz de resolver instancias con 1500 elementos de combustible, 7 tipos de regiones y 4 tipos de contenedores en un tiempo de CPU inferior a 2 segundos., Preprint

Aquesta tesi es desenvolupa en el marc d'una associació de projectes del consorci entre ALBA Synchrotron Light Source (ALBA), el Conseil Européen pour la Recherche Nucléaire (CERN), l'Institut de Ciència de Materials de Barcelona (ICMAB), lInstitut de Física d'Altes Energies (IFAE) i Universitat Politècnica de Catalunya (UPC). L'objectiu principal de la col·laboració és obtenir la impedància superficial dels conductors recoberts de superconductors d'alta temperatura (HTS-CCs) a les freqüències de microones que s'utilitzaran com a recobriment alternatiu a la pantalla de feixos del Future Circular Collider hadron-hadron (FCC-hh). L'ALBA i UPC han desenvolupat ressonadors de microones capaços de mesurar les propietats clau del HTS-CC amb diverses mesures de mostres de materials subministrats per diversos fabricants. El principal objectiu d'aquest treball es concentra en el desenvolupament d'un codi de Python per processar dades experimentals buscant paràmeters com factor de qualitat i impedància de superfície mitjançant algoritmes adaptats a la literatura tècnica.

P vs NP ha sido (y sigue siendo) uno de los problemas más importantes (si no el más importante) en el campo de las ciencias de la computación. Los problemas NP-Completos son infames por lo difíciles que son de solucionar, y además son muy prevalentes en casi todo campo dentro de la investigación en ciencias de la computación. Por este motivo, encontrar métodos eficientes para solucionar problemas NP-Completos es muy importante. En este proyecto nos centramos en un par de métodos para mejorar la eficiencia de Programación Lineal Entera (particularmente, el subconjunto de problemas en Programación Lineal Entera donde las variables son binarias, llamado Programación Lineal Binaria o Pseudobooleana) y comparamos su eficiencia usando el solver de "Intsat" desarrollado por Barcelogic, un spinoff de la UPC. El objetivo de este proyecto es implementar y estudiar la eficiencia de estos métodos, e integrarlos en Intsat si parece que mejoran el tiempo y/o la calidad de las soluciones., P vs NP has been (and still is) one of the most, if not the most important problem in computer science. NP-Complete problems are infamously difficult to solve, and not only that, but they are also very prevalent in almost every field inside computer science research. Because of that, finding efficient methods for solving NP-Complete problems is very important. In this project, we focus on a couple methods for improving the efficiency of Integer Linear Programing (particularly, the subset of problems in ILP where variables are binary, called Binary or Pseudoboolean Linear Programming) and compare their performance using the solver "Intsat" developed by Barcelogic, a spinoff of UPC. The final goal for this project is to implement and study the efficiency of these methods, and to integrate them into Intsat if they appear to make an improvement on the running time and/or the quality of the solutions.

Se presentan 7 soluciones con programación lineal entera mixta para el almacenamiento monoetápico del combustible nuclear gastado en cápsulas MPC-32 en una central nuclear. Se emplea la instancia de datos Ascó#01_06 y el solver CPLEX para la asignación de elementos combustibles a regiones térmicas., Se presenta en detalle siete soluciones óptimas para la instancia de datos Ascó#01_06 relacionada con la central nuclear Ascó-1 ubicada a 160 km de Barcelona. El procedimiento utilizado para hallar tales soluciones se despliega en dos fases. En la primera fase, se utiliza el modelo MILP-1 descrito en [2], cuyo objetivo es minimizar el coste de los contenedores requeridos para reubicar el máximo número de elementos combustibles disponibles en la piscina de una central nuclear; el modelo MILP-1, implementado en IBM ILOG CPLEX, sirve para concretar la tipología óptima de los contenedores para el vaciado de la piscina, siendo capaz de resolver instancias con 1200 elementos de combustible nuclear, 6 tipos de regiones térmicas y 4 tipos de contenedores en tiempos de CPU inferiores a 0.5 segundos. En la segunda fase, se emplea un procedimiento exacto (Algoritmo A1) que, partiendo de una solución de MILP-1, ofrece asignaciones óptimas de elementos combustibles a contenedores con 32 posiciones agrupadas en dos regiones con limitaciones máximas del calor residual soportable en cada locus (cápsulas MPC-32); el Algoritmo A1 es capaz de ofrecer una asignación óptima en un tiempo de CPU inferior a 0.25 segundos., Preprint

[ES] Actualmente en la República Dominicana, a diferencia de otros países, no existe una ley que regule la eficiencia energética en el sector construcción, aún siendo éste el segundo del mundo de un ranking de 124 países, en pagar una de las tarifas eléctricas mas caras. Uno de los mayores consumos eléctricos tiene lugar como consecuencia de establecer una temperatura agradable dentro de cualquier edificación. Los muros exteriores de las edificaciones están compuestos por capas de distintos materiales que tienen propiedades específicas dependiendo de su naturaleza y de su grosor. Una de estas propiedades guarda relación con la transmitancia térmica, que básicamente mide la cantidad de calor que atraviesa dicha capa. A menor transmitancia del muro exterior, mayor aislamiento térmico del interior de la edificación respecto del exterior. Una forma de contribuir a la eficiencia energética de un edificio es pues diseñar muros exteriores con capas y materiales adecuados a las características climáticas de la zona mediante el control de la transmitancia de los mismos, de manera que se pueda mantener una temperatura confortable en los espacios habitados, con el menor uso posible de calefacción o aire acondicionado, todo ello respetando condicionantes como el espesor del muro o el presupuesto establecido para su construcción. En el mercado existe una gran cantidad de materiales que se utilizan para las diversas capas de los muros exteriores, así como pueden ser varios los espesores de estos materiales. Ello puede dar lugar a incluso millones de combinaciones posibles, por lo que elegir la combinación óptima puede ser un trabajo humanamente imposible en un tiempo razonable. El objetivo de este Trabajo Final de Máster es hacer un estudio específico de los materiales usados en la República Dominicana para las diferentes capas que componen los muros exteriores de grandes edificios (particularmente hoteles), y mediante el uso de la Programación Lineal Entera y del programa Mathem, [CA] Actualment a la República Dominicana, a diferència d'altres països, no existeix una llei que regule l'eficiència energètica en el sector construcció, encara sent aquest el segon del món d'un rànquing de 124 països, a pagar una de les tarifes elèctriques més cares. Un dels majors consums elèctrics té lloc com a conseqüència d'establir una temperatura agradable dins de qualsevol edificació. Els murs exteriors de les edificacions estan compostos per capes de diferents materials que tenen propietats específiques depenent de la seua naturalesa i del seu gruix. Una d'aquestes propietats guarda relació amb la transmitància tèrmica, que bàsicament mesura la quantitat de calor que travessa aquesta capa. A menor transmitància del mur exterior, major aïllament tèrmic de l'interior de l'edificació respecte de l'exterior. Una forma de contribuir a l'eficiència energètica d'un edifici és doncs dissenyar murs exteriors amb capes i materials adequats a les característiques climàtiques de la zona mitjançant el control de la transmitància d'aquests, de manera que es puga mantenir una temperatura confortable en els espais habitats, amb el menor ús possible de calefacció o aire condicionat, tot això respectant condicionants com la grossària del mur o el pressupost establert per a la seua construcció. En el mercat existeix una gran quantitat de materials que s'utilitzen per a les diverses capes dels murs exteriors, així com poden ser diverses les grossàries d'aquests materials. Això pot donar lloc a fins i tot milions de combinacions possibles, per la qual cosa triar la combinació òptima pot ser un treball humanament impossible en un temps raonable. L'objectiu d'aquest Treball Final de Màster és fer un estudi específic dels materials usats a la República Dominicana per a les diferents capes que componen els murs exteriors de grans edificis (particularment hotels), i mitjançant l'ús de la Programació Lineal Entera i del programa Mathematica, trobar la combinació òptima de materials, [EN] Currently in the Dominican Republic, unlike other countries, there is no law that regulates energy efficiency in the construction sector, even though this is the second in the world of a ranking of 124 countries, to pay one of the most expensive electricity bill. One of the biggest electrical consumptions takes place as a result of establishing a pleasant temperature inside any building. The exterior walls of buildings are composed of layers of different materials that have specific properties depending on their nature and thickness. One of these properties is related to thermal transmittance, which basically measures the amount of heat that passes through said layer. The lower the transmittance of the outer wall, the greater thermal insulation of the interior of the building respect to the exterior. One way to contribute to the energy efficiency of a building is to design exterior walls with layers and materials appropriate to the climatic characteristics of the area by controlling the transmittance of them, so that a comfortable temperature can be maintained in the spaces inhabited, with the least possible use of heating or air conditioning, all respecting restrictions such as the thickness of the wall or the budget established for its construction. In the market there is a large amount of materials that are used for the layers of the outer walls, as well as there may be several thicknesses of these materials. If the number of layers is considerable, this can result in even millions of possible combinations, so choosing the optimal combination can be a humanly impossible job in a reasonable time. The objective of this Master's Final Project is to make a specific study of the materials used in the Dominican Republic for the different layers that make up the exterior walls of large buildings (particularly hotels), and through the use of Integer Linear Programming and the program Mathematica, find the optimal combination of materials and thicknesses for the diff

[ES] El DouGong es una estructura de la arquitectura tradicional china consistente en un conjunto de piezas de madera que se encajan entre sí sin adhesivos ni clavos y con doble misión, la de soportar el peso por parte de las columnas y la decorativa. En la antigua China este tipo de estructura estaba reservada para edificios imperiales y templos, pero en la actualidad se usa también para imitar edificios antiguos. En este Trabajo Final de Máster, tras hacer un estudio exhaustivo de los diversos tipos de DouGong existentes, de sus características técnicas, las dimensiones y funciones de las distintas piezas que los componen y los pasos de su fabricación artesanal, se modeliza matemáticamente mediante Programación Lineal Entera las características de una fábrica de DouGong, con todos sus condicionantes (cartera de pedidos de diferentes tipos de DouGong, mano de obra, materiales y su coste, tiempo de fabricación de cada tipo de DouGong, precios de venta, etc.), con el objeto de maximizar los beneficios obtenidos por la fábrica en un cierto periodo de tiempo. Tras plantear una formulación teórica de este problema, se aplica esta formulación a un caso de estudio de una fábrica de 100 trabajadores en un periodo de 6 meses con encargos de 12 tipos diferentes de DouGong. La obtención de la solución óptima para este caso de estudio con diversas herramientas informáticas permitirá mostrar la complejidad del problema planteado., [EN] The DouGong is a structure of the traditional Chinese architecture consisting of a set of pieces of wood that fit together without adhesives or nails and with a double mission, to support the weight by the columns and the decorative one. In the ancient China this type of structure was reserved for imperial buildings and temples, but nowadays it is also used to imitate ancient buildings. In this Final Master's Project, after making an exhaustive study of the various types of existing DouGong, their technical characteristics, the dimensions and functions of the different pieces that compose them, and the steps of their handmade manufacture, the characteristics of a DouGong factory is modeled mathematically by using Integer Linear Programming, with all its constraints (order book of different types of DouGong, labor force, materials and their cost, time of manufacture of each type of DouGong, sale prices, etc.), with the object of maximizing the profits obtained by the factory in a certain period of time. After proposing a theoretical formulation of this problem, this formulation is applied to a case study of a factory with 100 workers in a period of 6 months and with orders of 12 different types of DouGong. Obtaining the optimal solution to this case study with various computer tools will show the complexity of the problem., [CA] El DouGong és una estructura de l'arquitectura tradicional xinesa consistent en un conjunt de peces de fusta que s'encaixen entre si sense adhesius ni claus i amb doble missió, la de suportar el pes per part de les columnes i la decorativa. En l'antiga Xina aquest tipus d'estructura estava reservada per a edificis imperials i temples, però en l'actualitat s'usa també per a imitar edificis antics. En aquest Treball Final de Màster, després de fer un estudi exhaustiu dels diversos tipus de DouGong existents, de les seues característiques tècniques, les dimensions i funcions de les diferents peces que els componen i els passos de la seua fabricació artesanal, es modelitza matemàticament mitjançant Programació Lineal Entera les característiques d'una fàbrica de DouGong, amb tots els seus condicionants (cartera de comandes de diferents tipus de DouGong, mà d'obra, materials i el seu cost, temps de fabricació de cada tipus de DouGong, preus de venda, etc.), a fi de maximitzar els beneficis obtinguts per la fàbrica en un cert període de temps. Després de plantejar una formulació teòrica d'aquest problema, s'aplica aquesta formulació a un cas d'estudi d'una fàbrica de 100 treballadors en un període de 6 mesos amb encàrrecs de 12 tipus diferents de DouGong. L'obtenció de la solució òptima per a aquest cas d'estudi amb diverses eines informàtiques permetrà mostrar la complexitat del problema plantejat.

En aquest treball de fi de grau es resolen dos casos concrets de producció de productes aplicant el mètode d’optimització matemàtica anomenat programació lineal utilitzant dos eines de desenvolupament diferents anomenades RStudio i LINGO. En el primer cas, l’objectiu que es pretén és el de maximitzar la quantitat de productes que es volen produir en un fàbrica, però on la seva producció està limitada i condicionada per un seguit de restriccions. En el segon cas, l’objectiu que és pretén és el de maximitzar el benefici de la venda de productes que es volen produir en una explotació agrícola, però on la seva producció està limitada i condicionada per un seguit de restriccions. Un dels casos, concretament el cas 1, també es resol usant dos mètodes, basats en la programació lineal, que no impliquen l’ús d’una eina de desenvolupament, per tal de mostrar quines diferències hi ha entre usar una eina de desenvolupament o no usar-la. Aquests dos mètodes són el mètode geomètric i el mètode símplex.

© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991) showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., Peer Reviewed, Postprint (author's final draft)

Purpose: Once a set of suppliers has been determined, according to criteria of quality, price and reliability, among others, there remains the problem of assigning orders to the selected suppliers, in order to cover the needs at the lowest cost. We consider the case in which the needs of a component for a set of plants should be covered by suppliers with linear piecewise concave cost functions, a lower bound on the order size for the non-zero deliveries and a capacity constraint. The purpose is to design procedures for solving this problem. Design/methodology/approach: With the aim of providing practical tools to solve the problem of assigning orders to suppliers with linear piecewise concave costs, two mixed integer linear programs are proposed. Findings: The two MILP models are compared through an extensive computational experiment. This shows that both models, with a slight advantage for one of them, can be solved within a very short time, even when the dimensions of the instance largely exceed those that can occur in real cases. Originality/value: The paper proposes novel models that can be used to solve the problem to optimality in reasonable times and with standard optimization software., Peer Reviewed

En este trabajo aplicamos dos modelos de Programación lineal entera mixta, sobre problemas de taller de flujo regular con demanda generalizada de tipos de trabajos, con el propósito de transformar una línea de modelos mixtos en un taller de flujo regular. Para ilustrar dicha aplicación, presentamos un caso de estudio basado en una línea de motores mixtos de la factoría de Nissan en Barcelona. En el estudio se comparan los costes de producción de los dos sistemas productivos enfrentados, llegando a la conclusión de que el sistema taller de flujo regular sin bloqueos entre estaciones es el más competitivo. Como herramienta de resolución hemos empleado el solucionador CPLEX con resultados satisfactorios. Para llevar a la práctica la transformación de la línea de producción en un taller de flujo regular, proponemos un conjunto de requisitos, así como la asistencia al sistema productivo con un sistema de información basado en tecnologías IoT en el marco de la Industria 4.0., Postprint (author's final draft)

We introduce a new way of composing proofs in rule-based proof systems that generalizes tree-like and dag-like proofs. In the new definition, proofs are directed graphs of derived formulas, in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs circular. We show that, for all sets of standard inference rules, circular proofs are sound. We first focus on the circular version of Resolution, and see that it is stronger than Resolution since, as we show, the pigeonhole principle has circular Resolution proofs of polynomial size. Surprisingly, as proof systems for deriving clauses from clauses, Circular Resolution turns out to be equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: (1) polynomial-time (LP-based) algorithms that find circular Resolution proofs of constant width, (2) examples that separate circular from dag-like Resolution, such as the pigeonhole principle and its variants, and (3) exponentially hard cases for circular Resolution. Contrary to the case of circular resolution, for Frege we show that circular proofs can be converted into tree-like ones with at most polynomial overhead., Peer Reviewed, Postprint (author's final draft)