Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Lot production size problem and simulation of urban transport

OBJECTIVES AND STUDY METHOD: There are two subjects in this thesis: “Lot production size for a parallel machine scheduling problem with auxiliary equipment” and “Bus holding for a simulated traffic network”. Although these two themes seem unrelated, the main idea is the optimization of complex systems. The “Lot production size for a parallel machine scheduling problem with auxiliary equipment” deals with a manufacturing setting where sets of pieces form finished products. The aim is to maximize the profit of the finished products. Each piece may be processed in more than one mold. Molds must be mounted on machines with their corresponding installation setup times. The key point of our methodology is to solve the single period lot-sizing decisions for the finished products together with the piece-mold and the mold-machine assignments, relaxing the constraint that a single mold may not be used in two machines at the same time. For the “Bus holding for a simulated traffic network” we deal with One of the most annoying problems in urban bus operations is bus bunching, which happens when two or more buses arrive at a stop nose to tail. Bus bunching reflects an unreliable service that affects transit operations by increasing passenger-waiting times. This work proposes a linear mathematical programming model that establishes bus holding times at certain stops along a transit corridor to avoid bus bunching. Our approach needs real-time input, so we simulate a transit corridor and apply our mathematical model to the data generated. Thus, the inherent variability of a transit system is considered by the simulation, while the optimization model takes into account the key variables and constraints of the bus operation. CONTRIBUTIONS AND CONCLUSIONS: For the “Lot production size for a parallel machine scheduling problem with auxiliary equipment” the relaxation we propose able to find solutions more efficiently, moreover our experimental results show that most of the solutions verify that molds are non-overlapping even if they are installed on several machines. We propose an exact integer linear programming, a Relax&Fix heuristic, and a multistart greedy algorithm to solve this problem. Experimental results on instances based on real-world data show the efficiency of our approaches. The mathematical model and the algorithm for the lot production size problem, showed in this research, can be used for production planners to help in the scheduling of the manufacturing. For the “Bus holding for a simulated traffic network” most of the literature considers quadratic models that minimize passenger-waiting times, but they are harder to solve and therefore difficult to operate by real-time systems. On the other hand, our methodology reduces passenger-waiting times efficiently given our linear programming model, with the characteristic of applying control intervals just every 5 minutes.

A Review of the Arcuate Structures in the Iberian Variscides; Constraints and Genetical Models

In the Iberian Variscides several first order arcuate structures have been considered. In spite of being highly studied their characterization, formation mechanisms and even existence is still debatable. Themain Ibero-Armorican Arc (IAA) is essentially defined by a predominantNW–SE trend in the Iberian branch and an E–Wtrend in the Brittany one. However, in northern Spain it presents a 180° rotation, sometimes known as the Cantabrian Arc (CA). The relation between both arcs is controversial, being considered either as a single arc due to one tectonic event, or as the result of a polyphasic process. According to the last assumption, there is a later arcuate structure (CA), overlapping a previousmajor one (IAA). Whatever themodels, they must be able to explain the presence of a Variscan sinistral transpression in Iberia and a dextral one in Armorica, and a deformation spanning from the Devonian to the Upper Carboniferous. Another arcuate structure, in continuity with the CA, the Central-Iberian Arc (CIA) was recently proposed mainly based upon on magnetic anomalies, geometry of major folds and Ordovician paleocurrents. The critical review of the structural, stratigraphic and geophysical data supports both the IAA and the CA, but as independent structures. However, the presence of a CIA is highly questionable and could not be supported. The complex strain pattern of the IAA and the CA could be explained by a Devonian — Carboniferous polyphasic indentation of a Gondwana promontory. In thismodel the CA is essentially a thin-skinned arc,while the IAA has a more complex and longer evolution that has led to a thick-skinned first order structure. Nevertheless, both arcs are essentially the result of a lithospheric bending process during the Iberian Variscides.

Evaluation of the productive and vegetative aspects of the cultivar 'Imperial Gala' apple tree with EM-9 interstem in different lengths.

The obtaining of a compact plant, with less vigor and high productivity, equivalent to a conventional plant, constitutes a strong tendency in the current horticulture, aiming at a raising of the fruit production at the same planted area. One of the techniques that have had success nowadays is the interstem use. This study was developed in a commercial orchard of Randon Agro Silvo Pastoril S.A. (RASIP), located in the Rio Grande do Sul state, Brazil. The purpose of this work was to evaluate the vegetative and productive development of apple trees of 'Imperial Gala' with different lengths of EM-9 interstem. The treatments consisted of five interstem lengths: 10, 15, 20, 25, 30 cm. In the seventh year of implantation the following parameters were evaluated: the height of the plant, the diameter of the 'Imperial Gala' 5 cm above the second graft point, the volume of the tree-head (height, width and length), the number of bud per branch, and the number of fruits per lineal centimeter of branch. Through this study it could be concluded that the greater interstem (30 cm) presented better indices with relation of vigor control. However, the number of fruits per lineal centimeter of branch with the interstem of 10 cm offered only significant superiority, when compared with the interstem of 30 cm. Using interstem technique allows to gather the benefits of the rootstock 'Marubakaido' and to control excessive vigour with the interstem EM-9.

Methods for integrating machine learning and constrained optimization

In the framework of industrial problems, the application of Constrained Optimization is known to have overall very good modeling capability and performance and stands as one of the most powerful, explored, and exploited tool to address prescriptive tasks. The number of applications is huge, ranging from logistics to transportation, packing, production, telecommunication, scheduling, and much more. The main reason behind this success is to be found in the remarkable effort put in the last decades by the OR community to develop realistic models and devise exact or approximate methods to solve the largest variety of constrained or combinatorial optimization problems, together with the spread of computational power and easily accessible OR software and resources. On the other hand, the technological advancements lead to a data wealth never seen before and increasingly push towards methods able to extract useful knowledge from them; among the data-driven methods, Machine Learning techniques appear to be one of the most promising, thanks to its successes in domains like Image Recognition, Natural Language Processes and playing games, but also the amount of research involved. The purpose of the present research is to study how Machine Learning and Constrained Optimization can be used together to achieve systems able to leverage the strengths of both methods: this would open the way to exploiting decades of research on resolution techniques for COPs and constructing models able to adapt and learn from available data. In the first part of this work, we survey the existing techniques and classify them according to the type, method, or scope of the integration; subsequently, we introduce a novel and general algorithm devised to inject knowledge into learning models through constraints, Moving Target. In the last part of the thesis, two applications stemming from real-world projects and done in collaboration with Optit will be presented.

Modelling, simulation and control of rotary-wing aircraft in multi-agent scenario

The topic of this thesis is the design and the implementation of mathematical models and control system algorithms for rotary-wing unmanned aerial vehicles to be used in cooperative scenarios. The use of rotorcrafts has many attractive advantages, since these vehicles have the capability to take-off and land vertically, to hover and to move backward and laterally. Rotary-wing aircraft missions require precise control characteristics due to their unstable and heavy coupling aspects. As a matter of fact, flight test is the most accurate way to evaluate flying qualities and to test control systems. However, it may be very expensive and/or not feasible in case of early stage design and prototyping. A good compromise is made by a preliminary assessment performed by means of simulations and a reduced flight testing campaign. Consequently, having an analytical framework represents an important stage for simulations and control algorithm design. In this work mathematical models for various helicopter configurations are implemented. Different flight control techniques for helicopters are presented with theoretical background and tested via simulations and experimental flight tests on a small-scale unmanned helicopter. The same platform is used also in a cooperative scenario with a rover. Control strategies, algorithms and their implementation to perform missions are presented for two main scenarios. One of the main contributions of this thesis is to propose a suitable control system made by a classical PID baseline controller augmented with L1 adaptive contribution. In addition a complete analytical framework and the study of the dynamics and the stability of a synch-rotor are provided. At last, the implementation of cooperative control strategies for two main scenarios that include a small-scale unmanned helicopter and a rover.

Fleet Management System for Search and Rescue Operations

Over one million people lost their lives in the last twenty years from natural disasters like wildfires, earthquakes and man-made disasters. In such scenarios the usage of a fleet of robots aims at the parallelization of the workload and thus increasing speed and capabilities to complete time sensitive missions. This work focuses on the development of a dynamic fleet management system, which consists in the management of multiple agents cooperating in order to accomplish tasks. We presented a Mixed Integer Programming problem for the management and planning of mission’s tasks. The problem was solved using both an exact and a heuristic approach. The latter is based on the idea of solving iteratively smaller instances of the complete problem. Alongside, a fast and efficient algorithm for estimation of travel times between tasks is proposed. Experimental results demonstrate that the proposed heuristic approach is able to generate quality solutions, within specific time limits, compared to the exact one.

Marcas da religião evangelica na educação do corpo feminino : implicações para a educação fisica escolar

Universidade Estadual de Campinas . Faculdade de Educação Física

Veias do sistema porta-hepático em gansos domésticos

A distribuição intraparenquimal das veias porta-hepáticas foi estudada em 30 gansos domésticos. Latex Neoprene corado foi injetado pela veia isquiática e os animais forma fixados por imersão e injeção intramuscular com formol a 10% e dissecados. O fígado esteve composto por um grande lobo hepático direito e por um lobo hepático esquerdo menor, os quais estiveram conectados por uma ponte de parênquima. O lobo direito do fígado teve exclusivamente vasos do sistema porta-hepático formados pela distribuição intraparenquimal da veia porta-hepática direita, enquanto que no lobo esquerdo estes originaram-se da veia porta-hepática direita e de pequenas veias porta-hepáticas esquerdas. A veia porta-hepática direita emitiu o ramo caudal direito, que emitiu um pequeno ramo caudolateral direito e um grande ramo caudomedial direito. Cranialmente esta veia emitiu os ramos craniais direito e ramos lateral direito. A porção transversa da veia porta-hepática direita cruzou para o lobo hepático esquerdo, emitindo de 1 a 6 pequenos ramos craniais e caudais para a região média do fígado. No lobo esquerdo, o ramo esquerdo da veia porta-hepática direita emitiu o ramo cranial esquerdo, o ramo lateral esquerdo e o ramo medial. De 1 a 6 veias porta-hepáticas esquerdas foram identificadas desembocando ou no ramo esquerdo da veia porta-hepática direita ou em sua porção transversa, oriundos do ventrículo gástrico e do pró-ventrículo. Em 40% dos gansos uma veia porta-hepática própria oriunda da confluência de vasos venosos da face esquerda do ventrículo distribuiu-se na extremidade caudal do lobo esquerdo isoladamente.

PFLEIDERER 2: IDENTIFICATION OF A NEW GLOBULAR CLUSTER IN THE GALAXY

We provide evidence that indicates the star cluster Pfleiderer 2, which is projected in a rich field, as a newly identified Galactic globular cluster. Since it is located in a crowded field, core extraction and decontamination tools were applied to reveal the cluster sequences in B, V, and I color-magnitude diagrams (CMDs). The main CMD features of Pfleiderer 2 are a tilted red giant branch and a red horizontal branch, indicating a high metallicity around solar. The reddening is E(B - V) = 1.01. The globular cluster is located at a distance of d(circle dot) = 16 +/- 2 kpc from the Sun. The cluster is located 2.7 kpc above the Galactic plane and at a distance of R(GC) = 9.7 kpc from the Galactic center, which is unusual for a metal-rich globular cluster.

f t value of the 0(+)-> 0(+) beta(+) decay of (32)Ar: A measurement of isospin symmetry breaking in a superallowed decay

We determined the absolute branch of the T=2 superallowed decay of (32)Ar by detecting the beta(+)-delayed protons and gamma decays of the daughter state. We obtain b(SA)(beta)=(22.71 +/- 0.16)%, which represents the first determination of a proton branch to better than 1%. Using this branch along with the previously determined (32)Ar half-life and energy release, we determined ft=(1552 +/- 12) s for the superallowed decay. This ft value, together with the corrected Ft value extracted from previously known T=1 superallowed decays, yields a measurement of the isospin symmetry breaking correction in (32)Ar decay delta(exp)(C)=(2.1 +/- 0.8)%. This can be compared to a theoretical calculation delta(C)=(2.0 +/- 0.4)%. As by-products of this work, we determined the gamma and proton branches for the decay of the lowest T=2 state of (32)Cl, made a precise determination of the total proton branch and relative intensities of proton groups that leave (31)S in its first excited state and deduced an improved value for the (32)Cl mass.

The anti-MMP activity of benzalkonium chloride

Objective: This study evaluated the ability of benzalkonium chloride (BAC) to bind to dentine and to inhibit soluble recombinant MMPs and bound dentine matrix metalloproteinases (MMPs). Methods: Dentine powder was prepared from extracted human molars. Half was left mineralized; the other half was completely demineralized. The binding of BAG to dentine powder was followed by measuring changes in the supernatant concentration using UV spectrometry. The inhibitory effects of BAC on rhMMP-2, -8 and -9 were followed using a commercially available in vitro proteolytic assay. Matrix-bound endogenous MMP-activity was evaluated in completely demineralized beams. Each beam was either dipped into BAG and then dropped into 1 mL of a complete medium (CM) or they were placed in 1 mL of CM containing BAG for 30 days. After 30 days, changes in the dry mass of the beams or in the hydroxyproline (HYP) content of hydrolysates of the media were quantitated as indirect measures of matrix collagen hydrolysis by MMPs. Results: Demineralized dentine powder took up 10-times more BAG than did mineralized powder. Water rinsing removed about 50% of the bound BAC, whilst rinsing with 0.5 M NaCl removed more than 90% of the bound BAG. BAG concentrations 0.5 wt% produced 100% inhibition of soluble recombinant MMP-2, -8 or -9, and inhibited matrix-bound MMPs between 55 and 66% when measured as mass loss or 76-81% when measured as solubilization of collagen peptide fragments. Conclusions: BAC is effective at inhibiting both soluble recombinant MMPs and matrix-bound dentine MMPs in the absence of resins. (C) 2010 Elsevier Ltd. All rights reserved.

Knowledge-based system on optimum design of liquid retaining structures with genetic algorithms

This paper delineates the development of a prototype hybrid knowledge-based system for the optimum design of liquid retaining structures by coupling the blackboard architecture, an expert system shell VISUAL RULE STUDIO and genetic algorithm (GA). Through custom-built interactive graphical user interfaces under a user-friendly environment, the user is directed throughout the design process, which includes preliminary design, load specification, model generation, finite element analysis, code compliance checking, and member sizing optimization. For structural optimization, GA is applied to the minimum cost design of structural systems with discrete reinforced concrete sections. The design of a typical example of the liquid retaining structure is illustrated. The results demonstrate extraordinarily converging speed as near-optimal solutions are acquired after merely exploration of a small portion of the search space. This system can act as a consultant to assist novice designers in the design of liquid retaining structures.

Manutenção proactiva de sistemas AVAC com recurso aos sistemas inteligentes multiagente

Nos tempos actuais os equipamentos para Aquecimento Ventilação e Ar Condicionado (AVAC) ocupam um lugar de grande importância na concepção, desenvolvimento e manutenção de qualquer edifício por mais pequeno que este seja. Assim, surge a necessidade premente de racionalizar os consumos energéticos optimizando-os. A alta fiabilidade desejada nestes sistemas obriga-nos cada vez mais a descobrir formas de tornar a sua manutenção mais eficiente, pelo que é necessário prevenir de uma forma proactiva todas as falhas que possam prejudicar o bom desempenho destas instalações. Como tal, torna-se necessário detectar estas falhas/anomalias, sendo imprescíndivel que nos antecipemos a estes eventos prevendo o seu acontecimento num horizonte temporal pré-definido, permitindo actuar o mais cedo possível. É neste domínio que a presente dissertação tenta encontrar soluções para que a manutenção destes equipamentos aconteça de uma forma proactiva e o mais eficazmente possível. A ideia estruturante é a de tentar intervir ainda numa fase incipiente do problema, alterando o comportamento dos equipamentos monitorizados, de uma forma automática, com recursos a agentes inteligentes de diagnóstico de falhas. No caso em estudo tenta-se adaptar de forma automática o funcionamento de uma Unidade de Tratamento de Ar (UTA) aos desvios/anomalias detectadas, promovendo a paragem integral do sistema apenas como último recurso. A arquitectura aplicada baseia-se na utilização de técnicas de inteligência artificial, nomeadamente dos sistemas multiagente. O algoritmo utilizado e testado foi construído em Labview®, utilizando um kit de ferramentas de controlo inteligente para Labview®. O sistema proposto é validado através de um simulador com o qual se conseguem reproduzir as condições reais de funcionamento de uma UTA.

Contextual intelligent load management with ANN adaptive learning module

With the current increase of energy resources prices and environmental concerns intelligent load management systems are gaining more and more importance. This paper concerns a SCADA House Intelligent Management (SHIM) system that includes an optimization module using deterministic and genetic algorithm approaches. SHIM undertakes contextual load management based on the characterization of each situation. SHIM considers available generation resources, load demand, supplier/market electricity price, and consumers’ constraints and preferences. The paper focus on the recently developed learning module which is based on artificial neural networks (ANN). The learning module allows the adjustment of users’ profiles along SHIM lifetime. A case study considering a system with fourteen discrete and four variable loads managed by a SHIM system during five consecutive similar weekends is presented.