Strategic Optimization Techniques For FRTU Deployment and Chip Physical Design

Combinatorial optimization is a complex engineering subject. Although formulation often depends on the nature of problems that differs from their setup, design, constraints, and implications, establishing a unifying framework is essential. This dissertation investigates the unique features of three important optimization problems that can span from small-scale design automation to large-scale power system planning: (1) Feeder remote terminal unit (FRTU) planning strategy by considering the cybersecurity of secondary distribution network in electrical distribution grid, (2) physical-level synthesis for microfluidic lab-on-a-chip, and (3) discrete gate sizing in very-large-scale integration (VLSI) circuit. First, an optimization technique by cross entropy is proposed to handle FRTU deployment in primary network considering cybersecurity of secondary distribution network. While it is constrained by monetary budget on the number of deployed FRTUs, the proposed algorithm identi?es pivotal locations of a distribution feeder to install the FRTUs in different time horizons. Then, multi-scale optimization techniques are proposed for digital micro?uidic lab-on-a-chip physical level synthesis. The proposed techniques handle the variation-aware lab-on-a-chip placement and routing co-design while satisfying all constraints, and considering contamination and defect. Last, the first fully polynomial time approximation scheme (FPTAS) is proposed for the delay driven discrete gate sizing problem, which explores the theoretical view since the existing works are heuristics with no performance guarantee. The intellectual contribution of the proposed methods establishes a novel paradigm bridging the gaps between professional communities.

Almost Disjoint Families of Representing Sets

The thesis is concerned with a number of problems in Combinatorial Set Theory. The Generalized Continuum Hypothesis is assumed. Suppose X and K are non-zero cardinals. By successively identifying K with airwise disjoint sets of power K, a function/: X-*•K can be viewed as a transversal of a pairwise disjoint (X, K)family A . Questions about families of functions in K can thus bethought of as referring to families of transversals of A. We wish to consider generalizations of such questions to almost disjoint families; in particular we are interested in extensions of the following two problems: (i) What is the 'maximum' cardinality of an almost disjoint family of functions each mapping X into K? (ii) Describe the cardinalities of maximal almost disjoint families of functions each mapping X into K. Article in Bulletin of the Australian Mathematical Society 27(03):477 - 479 · June 1983  

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Generation and screening of natural product-like compounds for antibiotic discovery

Avec l’apparition de plus en plus de souches de bactérie résistante aux antibiotiques, le développement de nouveaux antibiotiques est devenu une important problématique pour les agences de santé. C’est pour cela que la création de nouvelles plateformes pour accélérer la découverte de médicaments est devenu un besoin urgent. Dans les dernières décennies, la recherche était principalement orientée sur la modification de molécules préexistantes, la méta-analyse d’organismes produisant des molécules activent et l’analyse de librairies moléculaires pour trouver des molécules synthétiques activent, ce qui s’est avéré relativement inefficace. Notre but était donc de développer de nouvelles molécules avec des effets thérapeutiques de façon plus efficace à une fraction du prix et du temps comparé à ce qui se fait actuellement. Comme structure de base, nous avons utilisé des métabolites secondaires qui pouvaient altérer le fonctionnement des protéines ou l’interaction entre deux protéines. Pour générer ces molécules, j’ai concentré mes efforts sur les terpènes, une classe de métabolites secondaires qui possède un large éventail d’activités biologiques incluant des activités antibactériennes. Nous avons développé un système de chromosome artificiel de levure (YAC) qui permet à la fois l’assemblage directionnel et combinatoire de gènes qui permet la création de voies de biosynthèse artificielles. Comme preuve de concept, j’ai développé des YACs qui contiennent les gènes pour l’expression des enzymes impliquées dans la biosynthèse de la -carotène et de l’albaflavenone et produit ces molécules avec un haut rendement. Finalement, Des YACs produits à partir de librairies de gènes ont permis de créer une grande diversité de molécules.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

La régulation de la transcription dans les cellules cancéreuses

La chromatine eucaryote, contenant l’ADN et de nombreuses protéines de liaison, subit une compaction dynamique et fonctionnelle à de multiples échelles, nécessaire pour la régulation de nombreux processus biologiques comme l’expression génique. Afin de définir et maintenir les fonctions cellulaires, les protéines de la régulation transcriptionnelle et de la régulation de la structure chromatinienne agissent de concert pour orchestrer les programmes d’expression génique des cellules. Les facteurs de transcription opèrent de manière combinée et hiérarchique au niveau de nombreux éléments régulateurs, dont le fonctionnement est complexe et intégré, capables de générer de larges boucles topologiques pour réguler spécifiquement un promoteur cible à un moment précis. Le co-activateur transcriptionnel Mediator sert de centre d’interprétation, en connectant physiquement les régulateurs de la transcription à la machinerie transcriptionnelle, pour générer une réponse calibrée. Le complexe de maintenance de la structure des chromosomes, Cohesin, est impliqué dans la formation et la stabilisation des connexions génomiques à l’échelle de nombreuses structures chromatiniennes tri-dimensionnelles dont la caractérisation fonctionnelle commence à être explorée. Ensemble, les facteurs de transcription, Mediator et Cohesin contrôlent l’expression des programmes responsables du maintien de l’identité cellulaire. Les cellules cancéreuses présentent de nombreuses dérégulations au niveau transcriptionnel, et donc un programme d’expression aberrant. Nous avons démontré que les mécanismes de régulation qui contrôlent les cellules cancéreuses sont conservés, et proposons une stratégie qui permette de révéler les facteurs clefs dans la progression tumorale. Nous avons appliqué cette stratégie à la problématique de la résistance endocrinienne dans la progression du cancer du sein hormono-dépendant. Les résultats obtenus suggèrent que le complexe transcriptionnel AP-1 pourrait être impliqué dans l’acquisition et/ou le maintien de la résistance, en réponse aux pressions de sélection induites par les traitements hormonaux. Nous proposons une adaptation progressive et agressive des cellules cancéreuses par re-hiérarchisation des facteurs clefs qui contrôlent sa croissance.

Physicochemical complexity in complex chemical systems

Self-replication and compartmentalization are two central properties thought to be essential for minimal life, and understanding how such processes interact in the emergence of complex reaction networks is crucial to exploring the development of complexity in chemistry and biology. Autocatalysis can emerge from multiple different mechanisms such as formation of an initiator, template self-replication and physical autocatalysis (where micelles formed from the reaction product solubilize the reactants, leading to higher local concentrations and therefore higher rates). Amphiphiles are also used in artificial life studies to create protocell models such as micelles, vesicles and oil-in-water droplets, and can increase reaction rates by encapsulation of reactants. So far, no template self-replicator exists which is capable of compartmentalization, or transferring this molecular scale phenomenon to micro or macro-scale assemblies. Here a system is demonstrated where an amphiphilic imine catalyses its own formation by joining a non-polar alkyl tail group with a polar carboxylic acid head group to form a template, which was shown to form reverse micelles by Dynamic Light Scattering (DLS). The kinetics of this system were investigated by 1H NMR spectroscopy, showing clearly that a template self-replication mechanism operates, though there was no evidence that the reverse micelles participated in physical autocatalysis. Active oil droplets, composed from a mixture of insoluble organic compounds in an aqueous sub-phase, can undergo processes such as division, self-propulsion and chemotaxis, and are studied as models for minimal cells, or protocells. Although in most cases the Marangoni effect is responsible for the forces on the droplet, the behaviour of the droplet depends heavily on the exact composition. Though theoretical models are able to calculate the forces on a droplet, to model a mixture of oils on an aqueous surface where compounds from the oil phase are dissolving and diffusing through the aqueous phase is beyond current computational capability. The behaviour of a droplet in an aqueous phase can only be discovered through experiment, though it is determined by the droplet's composition. By using an evolutionary algorithm and a liquid handling robot to conduct droplet experiments and decide which compositions to test next, entirely autonomously, the composition of the droplet becomes a chemical genome capable of evolution. The selection is carried out according to a fitness function, which ranks the formulation based on how well it conforms to the chosen fitness criteria (e.g. movement or division). Over successive generations, significant increases in fitness are achieved, and this increase is higher with more components (i.e. greater complexity). Other chemical processes such as chemiluminescence and gelation were investigated in active oil droplets, demonstrating the possibility of controlling chemical reactions by selective droplet fusion. Potential future applications for this might include combinatorial chemistry, or additional fitness goals for the genetic algorithm. Combining the self-replication and the droplet protocells research, it was demonstrated that the presence of the amphiphilic replicator lowers the interfacial tension between droplets of a reaction mixture in organic solution and the alkaline aqueous phase, causing them to divide. Periodic sampling by a liquid handling robot revealed that the extent of droplet fission increased as the reaction progressed, producing more individual protocells with increased self-replication. This demonstrates coupling of the molecular scale phenomenon of template self-replication to a macroscale physicochemical effect.

Semigrupos numéricos

Um semigrupo numérico é um submonoide de (N, +) tal que o seu complementar em N é finito. Neste trabalho estudamos alguns invariantes de um semigrupo numérico S tais como: multiplicidade, dimensão de imersão, número de Frobenius, falhas e conjunto Apéry de S. Caracterizamos uma apresentação minimal para um semigrupo numérico S e descrevemos um método algorítmico para determinar esta apresentação. Definimos um semigrupo numérico irredutível como um semigrupo numérico que não pode ser expresso como intersecção de dois semigrupos numéricos que o contenham propriamente. A finalizar este trabalho, estudamos os semigrupos numéricos irredutíveis e obtemos a decomposição de um semigrupo numérico em irredutíveis. ABSTRACT: A numerical semigroup is a submonoid of (N, +) such that its complement of N is finite. ln this work we study some invariants of a numerical semigroup S such as: multiplicity, embedding dimension, Frobenius number, gaps and Apéry set of S. We characterize a minimal presentation of a numerical semigroup S and describe an algorithmic procedure which allows us to compute a minimal presentation of S. We define an irreducible numerical semigroup as a numerical semigroup that cannot be expressed as the intersection of two numerical semigroups properly containing it. Concluding this work, we study and characterize irreducible numerical semigroups, and describe methods for computing decompositions of a numerical semigroup into irreducible numerical semigroups.

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.

The three-dimensional single-bin-size bin packing problem: combining metaheuristic and machine learning approaches

The Three-Dimensional Single-Bin-Size Bin Packing Problem is one of the most studied problem in the Cutting & Packing category. From a strictly mathematical point of view, it consists of packing a finite set of strongly heterogeneous “small” boxes, called items, into a finite set of identical “large” rectangles, called bins, minimizing the unused volume and requiring that the items are packed without overlapping. The great interest is mainly due to the number of real-world applications in which it arises, such as pallet and container loading, cutting objects out of a piece of material and packaging design. Depending on these real-world applications, more objective functions and more practical constraints could be needed. After a brief discussion about the real-world applications of the problem and a exhaustive literature review, the design of a two-stage algorithm to solve the aforementioned problem is presented. The algorithm must be able to provide the spatial coordinates of the placed boxes vertices and also the optimal boxes input sequence, while guaranteeing geometric, stability, fragility constraints and a reduced computational time. Due to NP-hard complexity of this type of combinatorial problems, a fusion of metaheuristic and machine learning techniques is adopted. In particular, a hybrid genetic algorithm coupled with a feedforward neural network is used. In the first stage, a rich dataset is created starting from a set of real input instances provided by an industrial company and the feedforward neural network is trained on it. After its training, given a new input instance, the hybrid genetic algorithm is able to run using the neural network output as input parameter vector, providing as output the optimal solution. The effectiveness of the proposed works is confirmed via several experimental tests.

Homological and Hodge-theoretic aspects of matroids and polymatroids

In the first part of this thesis, we study the action of the automorphism group of a matroid on the homology space of the co-independent complex. This representation turns out to be isomorphic, up to tensoring with the sign representation, with that on the homology space associated with the lattice of flats. In the case of the cographic matroid of the complete graph, this result has application in algebraic geometry: indeed De Cataldo, Heinloth and Migliorini use this outcome to study the Hitchin fibration. In the second part, on the other hand, we use ideas from algebraic geometry to prove a purely combinatorial result. We construct a Leray model for a discrete polymatroid with arbitrary building set and we prove a generalized Goresky-MacPherson formula. The first row of the model is the Chow ring of the polymatroid; we prove Poincaré duality, Hard-Lefschetz theorem and Hodge-Riemann relations for the Chow ring.

Models and algorithms for real-world optimization problems

This thesis deals with efficient solution of optimization problems of practical interest. The first part of the thesis deals with bin packing problems. The bin packing problem (BPP) is one of the oldest and most fundamental combinatorial optimiza- tion problems. The bin packing problem and its generalizations arise often in real-world ap- plications, from manufacturing industry, logistics and transportation of goods, and scheduling. After an introductory chapter, I will present two applications of two of the most natural extensions of the bin packing: Chapter 2 will be dedicated to an application of bin packing in two dimension to a problem of scheduling a set of computational tasks on a computer cluster, while Chapter 3 deals with the generalization of BPP in three dimensions that arise frequently in logistic and transportation, often com- plemented with additional constraints on the placement of items and characteristics of the solution, like, for example, guarantees on the stability of the items, to avoid potential damage to the transported goods, on the distribution of the total weight of the bins, and on compatibility with loading and unloading operations. The second part of the thesis, and in particular Chapter 4 considers the Trans- mission Expansion Problem (TEP), where an electrical transmission grid must be expanded so as to satisfy future energy demand at the minimum cost, while main- taining some guarantees of robustness to potential line failures. These problems are gaining importance in a world where a shift towards renewable energy can impose a significant geographical reallocation of generation capacities, resulting in the ne- cessity of expanding current power transmission grids.

The combinatorics of Hilbert-Poincaré series of matroids

In this thesis we explore the combinatorial properties of several polynomials arising in matroid theory. Our main motivation comes from the problem of computing them in an efficient way and from a collection of conjectures, mainly the real-rootedness and the monotonicity of their coefficients with respect to weak maps. Most of these polynomials can be interpreted as Hilbert--Poincaré series of graded vector spaces associated to a matroid and thus some combinatorial properties can be inferred via combinatorial algebraic geometry (non-negativity, palindromicity, unimodality); one of our goals is also to provide purely combinatorial interpretations of these properties, for example by redefining these polynomials as poset invariants (via the incidence algebra of the lattice of flats); moreover, by exploiting the bases polytopes and the valuativity of these invariants with respect to matroid decompositions, we are able to produce efficient closed formulas for every paving matroid, a class that is conjectured to be predominant among all matroids. One last goal is to extend part of our results to a higher categorical level, by proving analogous results on the original graded vector spaces via abelian categorification or on equivariant versions of these polynomials.

Poset associahedra as sections of graph associahedra

Poset associahedra are a family of convex polytopes recently introduced by Pavel Galashin in 2021. The associahedron An is an (n-2)-dimensional convex polytope whose facial structure encodes the ways of parenthesizing an n-letter word (among several equivalent combinatorial objects). Associahedra are deeply studied polytopes that appear naturally in many areas of mathematics: algebra, combinatorics, geometry, topology... They have many presentations and generalizations. One of their incarnations is as a compactification of the configuration space of n points on a line. Similarly, the P-associahedron of a poset P is a compactification of the configuration space of order preserving maps from P to R. Galashin presents poset associahedra as combinatorial objects and shows that they can be realized as convex polytopes. However, his proof is not constructive, in the sense that no explicit coordinates are provided. The main goal of this thesis is to provide an explicit construction of poset associahedra as sections of graph associahedra, thus solving the open problem stated in Remark 1.5 of Galashin's paper.

Machine Learning in Automatic Tabulation for Constraint Model Reformulation

Combinatorial decision and optimization problems belong to numerous applications, such as logistics and scheduling, and can be solved with various approaches. Boolean Satisfiability and Constraint Programming solvers are some of the most used ones and their performance is significantly influenced by the model chosen to represent a given problem. This has led to the study of model reformulation methods, one of which is tabulation, that consists in rewriting the expression of a constraint in terms of a table constraint. To apply it, one should identify which constraints can help and which can hinder the solving process. So far this has been performed by hand, for example in MiniZinc, or automatically with manually designed heuristics, in Savile Row. Though, it has been shown that the performances of these heuristics differ across problems and solvers, in some cases helping and in others hindering the solving procedure. However, recent works in the field of combinatorial optimization have shown that Machine Learning (ML) can be increasingly useful in the model reformulation steps. This thesis aims to design a ML approach to identify the instances for which Savile Row’s heuristics should be activated. Additionally, it is possible that the heuristics miss some good tabulation opportunities, so we perform an exploratory analysis for the creation of a ML classifier able to predict whether or not a constraint should be tabulated. The results reached towards the first goal show that a random forest classifier leads to an increase in the performances of 4 different solvers. The experimental results in the second task show that a ML approach could improve the performance of a solver for some problem classes.