Networks, Uncertainty, Applications and a Crusade for Optimality

In this thesis we address a collection of Network Design problems which are strongly motivated by applications from Telecommunications, Logistics and Bioinformatics. In most cases we justify the need of taking into account uncertainty in some of the problem parameters, and different Robust optimization models are used to hedge against it. Mixed integer linear programming formulations along with sophisticated algorithmic frameworks are designed, implemented and rigorously assessed for the majority of the studied problems. The obtained results yield the following observations: (i) relevant real problems can be effectively represented as (discrete) optimization problems within the framework of network design; (ii) uncertainty can be appropriately incorporated into the decision process if a suitable robust optimization model is considered; (iii) optimal, or nearly optimal, solutions can be obtained for large instances if a tailored algorithm, that exploits the structure of the problem, is designed; (iv) a systematic and rigorous experimental analysis allows to understand both, the characteristics of the obtained (robust) solutions and the behavior of the proposed algorithm.

Two-Dimensional Bin Packing Problem with Guillotine Restrictions

This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

Hierarchical Approach for Survivable Network Design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.

Quantification of relativistic perturbation forces on spacecraft trajectories

The intent of the work presented in this thesis is to show that relativistic perturbations should be considered in the same manner as well known perturbations currently taken into account in planet-satellite systems. It is also the aim of this research to show that relativistic perturbations are comparable to standard perturbations in speciffc force magnitude and effects. This work would have been regarded as little more then a curiosity to most engineers until recent advancements in space propulsion methods { e.g. the creation of a artiffcial neutron stars, light sails, and continuous propulsion techniques. These cutting-edge technologies have the potential to thrust the human race into interstellar, and hopefully intergalactic, travel in the not so distant future. The relativistic perturbations were simulated on two orbit cases: (1) a general orbit and (2) a Molniya type orbit. The simulations were completed using Matlab's ODE45 integration scheme. The methods used to organize, execute, and analyze these simulations are explained in detail. The results of the simulations are presented in graphical and statistical form. The simulation data reveals that the speciffc forces that arise from the relativistic perturbations do manifest as variations in the classical orbital elements. It is also apparent from the simulated data that the speciffc forces do exhibit similar magnitudes and effects that materialize from commonly considered perturbations that are used in trajectory design, optimization, and maintenance. Due to the similarities in behavior of relativistic versus non-relativistic perturbations, a case is made for the development of a fully relativistic formulation for the trajectory design and trajectory optimization problems. This new framework would afford the possibility of illuminating new more optimal solutions to the aforementioned problems that do not arise in current formulations. This type of reformulation has already showed promise when the previously unknown Space Superhighways arose as a optimal solution when classical astrodynamics was reformulated using geometric mechanics.

Egalitarianism under Earmark Constraints

Agents with single-peaked preferences share a resource coming from different suppliers; each agent is connected to only a subset of suppliers. Examples include workload balancing, sharing earmarked funds, and rationing utilities after a storm. Unlike in the one supplier model, in a Pareto optimal allocation agents who get more than their peak from underdemanded suppliers, coexist with agents who get less from overdemanded suppliers. Our Egalitarian solution is the Lorenz dominant Pareto optimal allocation. It treats agents with equal demands as equally as the connectivity constraints allow. Together, Strategyproofness, Pareto Optimality, and Equal Treatment of Equals, characterize our solution.

An MILP-based heuristic for staff scheduling problems with acceptance levels

We present a real-world staff-assignment problem that was reported to us by a provider of an online workforce scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of requirements related to work laws, work shift compatibility, workload balancing, and personal preferences of employees. A target value is given for each requirement, and all possible deviations from these values are associated with acceptance levels. The objective is to minimize the total number of deviations in ascending order of the acceptance levels. We present an exact lexicographic goal programming MILP formulation and an MILP-based heuristic. The heuristic consists of two phases: in the first phase a feasible schedule is built and in the second phase parts of the schedule are iteratively re-optimized by applying an exact MILP model. A major advantage of such MILP-based approaches is the flexibility to account for additional constraints or modified planning objectives, which is important as the requirements may vary depending on the company or planning period. The applicability of the heuristic is demonstrated for a test set derived from real-world data. Our computational results indicate that the heuristic is able to devise optimal solutions to non-trivial problem instances, and outperforms the exact lexicographic goal programming formulation on medium- and large-sized problem instances.

A heuristic approach for scheduling assessment centers

Human resources managers often use assessment centers to evaluate candidates for a job position. During an assessment center, the candidates perform a series of exercises. The exercises require one or two assessors (e.g., managers or psychologists) that observe and evaluate the candidate. If an exercise is designed as a role-play, an actor is required as well which plays, e.g., an unhappy customer with whom the candidate has to deal with. Besides performing the exercises, the candidates have a lunch break within a prescribed time window. Each candidate should be observed by approximately half the number of the assessors. Moreover, an assessor cannot be assigned to a candidate if they personally know each other. The planning problem consists of determining (1) resource-feasible start times of all exercises and lunch breaks and (2) a feasible assignment of assessors to candidates, such that the assessment center duration is minimized. We propose a list-scheduling heuristic that generates feasible schedules for such assessment centers. We develop novel procedures for devising an appropriate scheduling list and for incorporating the problem-specific constraints. Our computational results indicate that our approach is capable of devising optimal or near-optimal solutions to real-world instances within short CPU time.

Fiscal Federalism and Tax Equalization: The potential for progressive local taxes

We construct an empirically informed computational model of fiscal federalism, testing whether horizontal or vertical equalization can solve the fiscal externality problem in an environment in which heterogeneous agents can move and vote. The model expands on the literature by considering the case of progressive local taxation. Although the consequences of progressive taxation under fiscal federalism are well understood, they have not been studied in a context with tax equalization, despite widespread implementation. The model also expands on the literature by comparing the standard median voter model with a realistic alternative voting mechanism. We find that fiscal federalism with progressive taxation naturally leads to segregation as well as inefficient and inequitable public goods provision while the alternative voting mechanism generates more efficient, though less equitable, public goods provision. Equalization policy, under both types of voting, is largely undermined by micro-actors' choices. For this reason, the model also does not find the anticipated effects of vertical equalization discouraging public goods spending among wealthy jurisdictions and horizontal encouraging it among poor jurisdictions. Finally, we identify two optimal scenarios, superior to both complete centralization and complete devolution. These scenarios are not only Pareto optimal, but also conform to a Rawlsian view of justice, offering the best possible outcome for the worst-off. Despite offering the best possible outcomes, both scenarios still entail significant economic segregation and inequitable public goods provision. Under the optimal scenarios agents shift the bulk of revenue collection to the federal government, with few jurisdictions maintaining a small local tax.

Estrategias para el control microclimático del espacio entre edificaciones en clima cálido – húmedo

La presente investigación parte del problema en las zonas de clima cálido - húmedo en las cuales se producen impactos asociados a la incomodidad térmica producto de la intensa radiación solar, altas temperaturas y elevada humedad. Estos factores reducen la calidad de los espacios abiertos y desarrollan en la población una actitud de rechazo hacia el uso del microespacio urbano entre edificaciones en los desarrollos urbanos - conjuntos urbanos - , los mismos frecuentemente admiten soluciones que al parecer no contribuyen a la realización de las actividades comunes de esparcimiento de la población residente. Por lo tanto, el objetivo de la investigación es profundizar en la temática urbano - ambiental - social y el diseño urbano vinculada a la particularidad morfológica local, las condiciones microclimáticas, el uso del microespacio y los requerimientos de los usuarios. La finalidad de desarrollar estrategias de control microclimático del microespacio entre edificios en clima cálido - húmedo en búsqueda de soluciones óptimas que satisfagan las necesidades de los usuarios de los espacios exteriores en estas áreas residenciales. La investigación se centra en el estudio de las particularidades contextuales relacionadas con el microclima y las características urbanas - morfotipológicas, básicamente los factores microclimáticos (soleamiento y ventilación), los morfológicos y edificatorios y las características de las superficies (pavimentos). En coherencia con el objetivo propuesto el trabajo se desarrolla en cuatro fases: la primera aborda la revisión documental, literatura relevante e investigaciones relativas a la calidad ambiental, medio social, medio físico, el microespacio urbano, control y diseño sostenible, modelización proyectual y estrategias sostenibles; la segunda fase se refiere al marco contextual, características urbanas, datos climáticos locales, planes y procesos urbanos, tipologías y conformación urbana. En esta fase se describe el proceso de selección, análisis y evaluación urbano - ambiental de los casos de estudio (conjuntos residenciales). En la tercera fase se aborda el marco evaluativo y estudio de casos, consideraciones físicas, climáticas y valoración térmico - ambiental de los conjuntos residenciales seleccionados. En esta fase se aplican Técnicas Estadísticas y de Simulación Computacional y se analizan los resultados obtenidos. Finalmente, la cuarta fase propositiva incluye el establecimiento de Estrategias, Principios y Lineamientos de optimación térmica y se exponen las Conclusiones parciales de la tesis, alcances y perspectivas futuras. Finalmente, los resultados obtenidos en la investigación demuestran que el análisis en las experiencias de la realidad permiten comprobar que las situaciones y alteraciones ambientales sustanciales, los niveles de afectación térmica y las condiciones de confortabilidad e impacto derivan de las características urbanas, los componentes del microespacio y de las condiciones climáticas las cuales afectan el desarrollo de las actividades y el uso efectivo del microespacio entre edificios. El análisis de los factores morfo - climáticos incidentes y el estudio de los efectos de interacción contribuyen al establecimiento de Principios y Lineamientos para la evaluación y diseño sostenible del microespacio entre edificios y el uso correcto de los elementos del clima en estas áreas urbanas destinadas a la actividad social y al esparcimiento de la población residente. ABSTRACT This research starts from the problem of hot - humid climate zones where impacts related to thermal discomfort are produced as a result from the intense solar radiation and high temperatures and humidity. These factors reduce the quality of open spaces and people develop an attitude of rejection towards the use of urban microspace among buildings within urban developments - urban complexes - . Usually, these complexes admit solutions that apparently do not contribute to the achievement of common leisure activities in the resident dwellers. Therefore, the main purpose of this research is to deepen in the urban - environmental - social issue and urban design linked to the local morphological particularity, microclimate conditions, use of microspace and users’ requirements. In order to develop microclimate control strategies of microspace among buildings in hot - humid climate to look for optimal solutions that satisfy users’ needs of outdoors spaces in these residential areas. The research focuses in the study of contextual particularities related to microclimate and urban - morphotypological characteristics. Basically, microclimate (sunlight and ventilation), morphological and building factors as well as road surface characteristics. According to the proposed objective, this research is developed in four phases: the first one considers documentary review, relevant literature and researches related to environmental quality, social environment, physical environment, urban microspace, control and sustainable design, project modelling and sustainable strategies; while the second phase refers to contextual framework, urban characteristics, local climate data, plans and urban processes, typologies and urban structure. In this phase, the process of selection, analysis and urban - environmental evaluation of case studies (residential complexes) is described. The third phase approaches the assessment framework and case studies, physical and climate considerations as well as environmental - thermal evaluation of selected residential complexes. In this phase, statistical techniques and computational simulations are applied. Likewise, results obtained are analysed. Similarly, fourth and proposing phase includes the establishment of strategies, principles and guidelines of thermal optimization and partial conclusions of the thesis, scopes and future perspectives are exposed. Finally, from the results obtained, it is demonstrated that the analysis on reality experiences allow proving that situations and substantial environmental changes, levels of thermal affectations, comfort conditions and impact derive from urban characteristics, microspace components and from climate conditions which affect the development of activities and the effective use of microspace among buildings. The analysis of incidental morpho - climate factors and the study of interaction effects contribute to the establishment of principles and guidelines for the assessment and sustainable design of microspace among buildings as well as the correct use of climate elements in these urban areas oriented to social and leisure activities of resident population.

Aerodynamic Optimization of High-Speed Trains Nose using a Genetic Algorithm and Artificial Neural Network

An aerodynamic optimization of the train aerodynamic characteristics in term of front wind action sensitivity is carried out in this paper. In particular, a genetic algorithm (GA) is used to perform a shape optimization study of a high-speed train nose. The nose is parametrically defined via Bézier Curves, including a wider range of geometries in the design space as possible optimal solutions. Using a GA, the main disadvantage to deal with is the large number of evaluations need before finding such optimal. Here it is proposed the use of metamodels to replace Navier-Stokes solver. Among all the posibilities, Rsponse Surface Models and Artificial Neural Networks (ANN) are considered. Best results of prediction and generalization are obtained with ANN and those are applied in GA code. The paper shows the feasibility of using GA in combination with ANN for this problem, and solutions achieved are included.

Multiobjective optimization applied to structural sizing of low cost university-class microsatellite projects

In recent years, there has been continuing interest in the participation of university research groups in space technology studies by means of their own microsatellites. The involvement in such projects has some inherent challenges, such as limited budget and facilities. Also, due to the fact that the main objective of these projects is for educational purposes, usually there are uncertainties regarding their in orbit mission and scientific payloads at the early phases of the project. On the other hand, there are predetermined limitations for their mass and volume budgets owing to the fact that most of them are launched as an auxiliary payload in which the launch cost is reduced considerably. The satellite structure subsystem is the one which is most affected by the launcher constraints. This can affect different aspects, including dimensions, strength and frequency requirements. In this paper, the main focus is on developing a structural design sizing tool containing not only the primary structures properties as variables but also the system level variables such as payload mass budget and satellite total mass and dimensions. This approach enables the design team to obtain better insight into the design in an extended design envelope. The structural design sizing tool is based on analytical structural design formulas and appropriate assumptions including both static and dynamic models of the satellite. Finally, a Genetic Algorithm (GA) multiobjective optimization is applied to the design space. The result is a Pareto-optimal based on two objectives, minimum satellite total mass and maximum payload mass budget, which gives a useful insight to the design team at the early phases of the design.

A review on probabilistic graphical models in evolutionary computation

Thanks to their inherent properties, probabilistic graphical models are one of the prime candidates for machine learning and decision making tasks especially in uncertain domains. Their capabilities, like representation, inference and learning, if used effectively, can greatly help to build intelligent systems that are able to act accordingly in different problem domains. Evolutionary algorithms is one such discipline that has employed probabilistic graphical models to improve the search for optimal solutions in complex problems. This paper shows how probabilistic graphical models have been used in evolutionary algorithms to improve their performance in solving complex problems. Specifically, we give a survey of probabilistic model building-based evolutionary algorithms, called estimation of distribution algorithms, and compare different methods for probabilistic modeling in these algorithms.

New laser-based approaches to improve the passivation and rear contact quality in high effiency crystalline silicon solar cells

Laser processing has been the tool of choice last years to develop improved concepts in contact formation for high efficiency crystalline silicon (c-Si) solar cells. New concepts based on standard laser fired contacts (LFC) or advanced laser doping (LD) techniques are optimal solutions for both the front and back contacts of a number of structures with growing interest in the c-Si PV industry. Nowadays, substantial efforts are underway to optimize these processes in order to be applied industrially in high efficiency concepts. However a critical issue in these devices is that, most of them, demand a very low thermal input during the fabrication sequence and a minimal damage of the structure during the laser irradiation process. Keeping these two objectives in mind, in this work we discuss the possibility of using laser-based processes to contact the rear side of silicon heterojunction (SHJ) solar cells in an approach fully compatible with the low temperature processing associated to these devices. First we discuss the possibility of using standard LFC techniques in the fabrication of SHJ cells on p-type substrates, studying in detail the effect of the laser wavelength on the contact quality. Secondly, we present an alternative strategy bearing in mind that a real challenge in the rear contact formation is to reduce the damage induced by the laser irradiation. This new approach is based on local laser doping techniques previously developed by our groups, to contact the rear side of p-type c-Si solar cells by means of laser processing before rear metallization of dielectric stacks containing Al2O3. In this work we demonstrate the possibility of using this new approach in SHJ cells with a distinct advantage over other standard LFC techniques.

Laser Processes for Contact Optimization in c-Si Solar Cells

Solid State Lasers (SSL) have been used in microelectronic and photovoltaic (PV) industry for decades but, currently, laser technology appears as a key enabling technology to improve efficiency and to reduce production costs in high efficiency solar cells fabrication. Moreover, the fact that the interaction between the laser radiation and the device is normally localized and restricted to a controlled volume makes SSL a tool of choice for the implementation of low temperature concepts in PV industry. Specifically, SSL are ideally suited to improve the electrical performance of the contacts further improving the efficiency of these devices. Advanced concepts based on standard laser firing or advanced laser doping techniques are optimal solutions for the back contact of a significant number of structures of growing interest in the c-Si PV industry, and a number of solutions has been proposed as well for emitter formation, to reduce the metallization optical losses or even to remove completely the contacts from the front part of the cell. In this work we present our more recent results of SSL applications for contact optimization in c-Si solar cell technology, including applications on low temperature processes demanding devices, like heterojunction solar cells.