Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Análise de risco em sequenciamento de actividades com restrições de recursos

Mestrado em Engenharia Electrotécnica e de Computadores. Área de Especialização em Sistemas e Planeamento Industrial.

Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma

Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms

Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

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.

Algebraic Bethe ansatz method for the exact calculation of energy spectra and form factors: applications to models of Bose-Einstein condensates and metallic nanograins

In this review we demonstrate how the algebraic Bethe ansatz is used for the calculation of the-energy spectra and form factors (operator matrix elements in the basis of Hamiltonian eigenstates) in exactly solvable quantum systems. As examples we apply the theory to several models of current interest in the study of Bose-Einstein condensates, which have been successfully created using ultracold dilute atomic gases. The first model we introduce describes Josephson tunnelling between two coupled Bose-Einstein condensates. It can be used not only for the study of tunnelling between condensates of atomic gases, but for solid state Josephson junctions and coupled Cooper pair boxes. The theory is also applicable to models of atomic-molecular Bose-Einstein condensates, with two examples given and analysed. Additionally, these same two models are relevant to studies in quantum optics; Finally, we discuss the model of Bardeen, Cooper and Schrieffer in this framework, which is appropriate for systems of ultracold fermionic atomic gases, as well as being applicable for the description of superconducting correlations in metallic grains with nanoscale dimensions.; In applying all the above models to. physical situations, the need for an exact analysis of small-scale systems is established due to large quantum fluctuations which render mean-field approaches inaccurate.

New approaches in W gravities

We devote effort to studying some nonlinear actions, characteristic of W theories, in the framework of the soldering formalism. We disclose interesting new results concerning the embedding of the original chiral W particles in different metrical spaces in the final soldered action; i.e., the metric is modified by the soldering interference process. The results are presented in a weak field approximation for the W-N case when Ngreater than or equal to3 and also in an exact way for W-2. We promote a generalization of the interference phenomenon to W-N theories of different chiralities and show that the geometrical features introduced can yield a new understanding of the interference formalism in quantum field theories.

Numerical and analytical approaches to strongly correlated electron systems

In this thesis we consider three different models for strongly correlated electrons, namely a multi-band Hubbard model as well as the spinless Falicov-Kimball model, both with a semi-elliptical density of states in the limit of infinite dimensions d, and the attractive Hubbard model on a square lattice in d=2. In the first part, we study a two-band Hubbard model with unequal bandwidths and anisotropic Hund's rule coupling (J_z-model) in the limit of infinite dimensions within the dynamical mean-field theory (DMFT). Here, the DMFT impurity problem is solved with the use of quantum Monte Carlo (QMC) simulations. Our main result is that the J_z-model describes the occurrence of an orbital-selective Mott transition (OSMT), in contrast to earlier findings. We investigate the model with a high-precision DMFT algorithm, which was developed as part of this thesis and which supplements QMC with a high-frequency expansion of the self-energy. The main advantage of this scheme is the extraordinary accuracy of the numerical solutions, which can be obtained already with moderate computational effort, so that studies of multi-orbital systems within the DMFT+QMC are strongly improved. We also found that a suitably defined Falicov-Kimball (FK) model exhibits an OSMT, revealing the close connection of the Falicov-Kimball physics to the J_z-model in the OSM phase. In the second part of this thesis we study the attractive Hubbard model in two spatial dimensions within second-order self-consistent perturbation theory. This model is considered on a square lattice at finite doping and at low temperatures. Our main result is that the predictions of first-order perturbation theory (Hartree-Fock approximation) are renormalized by a factor of the order of unity even at arbitrarily weak interaction (U->0). The renormalization factor q can be evaluated as a function of the filling n for 00, the q-factor vanishes, signaling the divergence of self-consistent perturbation theory in this limit. Thus we present the first asymptotically exact results at weak-coupling for the negative-U Hubbard model in d=2 at finite doping.

Filling in gaps of Drosophila melanogaster urate degradation metabolic pathway using metabolomics approaches: towards the core metabolome of the fruit fly

The primary goal of systems biology is to integrate complex omics data, and data obtained from traditional experimental studies in order to provide a holistic understanding of organismal function. One way of achieving this aim is to generate genome-scale metabolic models (GEMs), which contain information on all metabolites, enzyme-coding genes, and biochemical reactions in a biological system. Drosophila melanogaster GEM has not been reconstructed to date. Constraint-free genome-wide metabolic model of the fruit fly has been reconstructed in our lab, identifying gaps, where no enzyme was identified and metabolites were either only produced or consume. The main focus of the work presented in this thesis was to develop a pipeline for efficient gap filling using metabolomics approaches combined with standard reverse genetics methods, using 5-hydroxyisourate hydrolase (5-HIUH) as an example. 5-HIUH plays a role in urate degradation pathway. Inability to degrade urate can lead to inborn errors of metabolism (IEMs) in humans, including hyperuricemia. Based on sequence analysis Drosophila CG30016 gene was hypothesised to encode 5- HIUH. CG30016 knockout flies were examined to identify Malpighian tubules phenotype, and shortened lifespan might reflect kidney disorders in hyperuricemia in humans. Moreover, LC-MS analysis of mutant tubules revealed that CG30016 is involved in purine metabolism, and specifically urate degradation pathway. However, the exact role of the gene has not been identified, and the complete method for gap filling has not been developed. Nevertheless, thanks to the work presented here, we are a step closer towards the development of a gap-filling pipeline in Drosophila melanogaster GEM. Importantly, the areas that require further optimisation were identified and are the focus of future research. Moreover, LC-MS analysis confirmed that tubules rather than the whole fly were more suitable for metabolomics analysis of purine metabolism. Previously, Dow/Davies lab has generated the most complete tissue-specific transcriptomic atlas for Drosophila – FlyAtlas.org, which provides data on gene expression across multiple tissues of adult fly and larva. FlyAtlas revealed that transcripts of many genes are enriched in specific Drosophila tissues, and that it is possible to deduce the functions of individual tissues within the fly. Based on FlyAtlas data, it has become clear that the fly (like other metazoan species) must be considered as a set of tissues, each 2 with its own distinct transcriptional and functional profile. Moreover, it revealed that for about 30% of the genome, reverse genetic methods (i.e. mutation in an unknown gene followed by observation of phenotype) are only useful if specific tissues are investigated. Based on the FlyAtlas findings, we aimed to build a primary tissue-specific metabolome of the fruit fly, in order to establish whether different Drosophila tissues have different metabolomes and if they correspond to tissue-specific transcriptome of the fruit fly (FlyAtlas.org). Different fly tissues have been dissected and their metabolome elucidated using LC-MS. The results confirmed that tissue metabolomes differ significantly from each other and from the whole fly, and that some of these differences can be correlated to the tissue function. The results illustrate the need to study individual tissues as well as the whole organism. It is clear that some metabolites that play an important role in a given tissue might not be detected in the whole fly sample because their abundance is much lower in comparison to other metabolites present in all tissues, which prevent the detection of the tissue-specific compound.

Exact solutions for the agricultural and the two-dimensional packing problems

Objectives and study method: The objective of this study is to develop exact algorithms that can be used as management tools for the agricultural production planning and to obtain exact solutions for two of the most well known twodimensional packing problems: the strip packing problem and the bin packing problem. For the agricultural production planning problem we propose a new hierarchical scheme of three stages to improve the current agricultural practices. The objective of the first stage is to delineate rectangular and homogeneous management zones into the farmer’s plots considering the physical and chemical soil properties. This is an important task because the soil properties directly affect the agricultural production planning. The methodology for this stage is based on a new method called “Positions and Covering” that first generates all the possible positions in which the plot can be delineated. Then, we use a mathematical model of linear programming to obtain the optimal physical and chemical management zone delineation of the plot. In the second stage the objective is to determine the optimal crop pattern that maximizes the farmer’s profit taken into account the previous management zones delineation. In this case, the crop pattern is affected by both management zones delineation, physical and chemical. A mixed integer linear programming is used to solve this stage. The objective of the last stage is to determine in real-time the amount of water to irrigate in each crop. This stage takes as input the solution of the crop planning stage, the atmospheric conditions (temperature, radiation, etc.), the humidity level in plots, and the physical management zones of plots, just to name a few. This procedure is made in real-time during each irrigation period. A linear programming is used to solve this problem. A breakthrough happen when we realize that we could propose some adaptations of the P&C methodology to obtain optimal solutions for the two-dimensional packing problem and the strip packing. We empirically show that our methodologies are efficient on instances based on real data for both problems: agricultural and two-dimensional packing problems. Contributions and conclusions: The exact algorithms showed in this study can be used in the making-decision support for agricultural planning and twodimensional packing problems. For the agricultural planning problem, we show that the implementation of the new hierarchical approach can improve the farmer profit between 5.27% until 8.21% through the optimization of the natural resources. An important characteristic of this problem is that the soil properties (physical and chemical) and the real-time factors (climate, humidity level, evapotranspiration, etc.) are incorporated. With respect to the two-dimensional packing problems, one of the main contributions of this study is the fact that we have demonstrate that many of the best solutions founded in literature by others approaches (heuristics approaches) are the optimal solutions. This is very important because some of these solutions were up to now not guarantee to be the optimal solutions.

Cytogenetic And Morphologic Approaches Of Hybrids From Experimental Crosses Between Triatoma Lenti Sherlock & Serafim, 1967 And T. Sherlocki Papa Et Al., 2002 (hemiptera: Reduviidae).

The reproductive capacity between Triatoma lenti and Triatoma sherlocki was observed in order to verify the fertility and viability of the offspring. Cytogenetic, morphological and morphometric approaches were used to analyze the differences that were inherited. Experimental crosses were performed in both directions. The fertility rate of the eggs in crosses involving T. sherlocki females was 65% and 90% in F1 and F2 offspring, respectively. In reciprocal crosses, it was 7% and 25% in F1 and F2 offspring, respectively. The cytogenetic analyses of the male meiotic process of the hybrids were performed using lacto-acetic orcein, C-banding and Feulgen techniques. The male F1 offspring presented normal chromosome behavior, a finding that was similar to those reported in parental species. However, cytogenetic analysis of F2 offspring showed errors in chromosome pairing. This post-zygotic isolation, which prevents hybrids in nature, may represent the collapse of the hybrid. This phenomenon is due to a genetic dysregulation that occurs in the chromosomes of F1. The results were similar in the hybrids from both crosses. Morphological features, such as color and size of connexive and the presence of red-orange rings on the femora, were similar to T. sherlocki, while wins size was similar to T. lenti in F1 offspring. The eggshells showed characteristics that were similar to species of origin, whereas the median process of the pygophore resulted in intermediate characteristics in the F1 and a segregating pattern in F2 offspring. Geometric morphometric techniques used on the wings showed that both F1 and F2 offspring were similar to T. lenti. These studies on the reproductive capacity between T. lenti and T. sherlocki confirm that both species are evolutionarily closed; hence, they are included in the brasiliensis subcomplex. The extremely reduced fertility observed in the F2 hybrids confirmed the specific status of the species that were analyzed.

Comparasion of two minimally invasive methods on the longevity of glass ionomer cement restorations: short-term results of a pilot study

The purpose of this study was to evaluate the clinical performance of glass ionomer cement (GIC) restorations comparing two minimally invasive methods in permanent teeth after 12 months. Fifty pregnant women (second trimester of pregnancy), mean age 22 ± 5.30 years, were treated by two previously trained operators. The treatment approaches tested were: chemomechanical method (CarisolvTM; MediTeam) and atraumatic restorative treatment (ART). A split-mouth study design was used in which the two treatments were randomly placed in 50 matched pairs of permanent teeth. The chemomechanical method (CM) was the test group and the ART was the control group. The treatments were performed in Public Health Centers. The tested restorative material was a high-strength GIC (Ketac Molar; 3M/ESPE). The restorations were placed according to the ART guidelines. Two calibrated independent examiners evaluated the restorations in accordance with ART criteria. The inter-examiner kappa was 0.97. Data were analyzed using 95% confidence interval on the binomial distribution and Fisher's exact test at 5% significance level. In a 12-month follow-up, 86% of the restorations were evaluated. In the test group (CM), 100% (CI=93.3-100%) of the restorations were considered successful. In the control group (ART) 97.6% (CI=87.4-99.9%) of the restorations were considered successful and 2.4% unsuccessful (marginal defect >0.5 mm). There was no statistically significant difference between the 12-mounth success rate for both groups (Fisher's exact test: P=0.49) and between the two operators (Fisher's exact test: P=1.00). Both minimally invasive methods, chemomechanical method and ART, showed a similar clinical performance after 12 months of follow up.

Inteligência artificial aplicada à Zootecnia

Os sistemas biológicos são surpreendentemente flexíveis pra processar informação proveniente do mundo real. Alguns organismos biológicos possuem uma unidade central de processamento denominada de cérebro. O cérebro humano consiste de 10(11) neurônios e realiza processamento inteligente de forma exata e subjetiva. A Inteligência Artificial (IA) tenta trazer para o mundo da computação digital a heurística dos sistemas biológicos de várias maneiras, mas, ainda resta muito para que isso seja concretizado. No entanto, algumas técnicas como Redes neurais artificiais e lógica fuzzy tem mostrado efetivas para resolver problemas complexos usando a heurística dos sistemas biológicos. Recentemente o numero de aplicação dos métodos da IA em sistemas zootécnicos tem aumentado significativamente. O objetivo deste artigo é explicar os princípios básicos da resolução de problemas usando heurística e demonstrar como a IA pode ser aplicada para construir um sistema especialista para resolver problemas na área de zootecnia.

Neuromodulation approaches for the treatment of major depression: challenges and recommendations from a working group meeting

The use of neuromodulation as a treatment for major depressive disorder (MDD) has recently attracted renewed interest due to development of other non-pharmacological therapies besides electroconvulsive therapy (ECT) such as transcranial magnetic stimulation (TMS), transcranial direct current stimulation (tDCS), deep brain stimulation (DBS), and vagus nerve stimulation (VNS). METHOD: We convened a working group of researchers to discuss the updates and key challenges of neuromodulation use for the treatment of MDD. RESULTS: The state-of-art of neuromodulation techniques was reviewed and discussed in four sections: [1] epidemiology and pathophysiology of MDD; [2] a comprehensive overview of the neuromodulation techniques; [3] using neuromodulation techniques in MDD associated with non-psychiatric conditions; [4] the main challenges of neuromodulation research and alternatives to overcome them. DISCUSSION: ECT is the first-line treatment for severe depression. TMS and tDCS are strategies with a relative benign profile of side effects; however, while TMS effects are comparable to antidepressant drugs for treating MDD; further research is needed to establish the role of tDCS. DBS and VNS are invasive strategies with a possible role in treatment-resistant depression. In summary, MDD is a chronic and incapacitating condition with a high prevalence; therefore clinicians should consider all the treatment options including invasive and non-invasive neuromodulation approaches.