Boosting the performance of metaheuristics for the MinLA problem using a more discriminating evaluation function

International audience

Iterated responsive threshold search for the quadratic multiple knapsack problem

International audience

Effective Learning-Based Hybrid Search for Bandwidth Coloring

International audience

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.

Tau Functions and the Limit of Block Toeplitz Determinants

International audience

Development of docetaxel and alendronate-loaded chitosan-conjugated polylactide-co-glycolide nanoparticles: In vitro characterization in osteosarcoma cells

Purpose: To develop docetaxel (DTX)- and alendronate (ALN)-loaded, chitosan (CS)-conjugated polylactide- co-glycolide (PLGA) nanoparticles (NPs) to increase therapeutic efficacy in osteosarcoma cells. Methods: Drug-loaded PLGA NPs were prepared by nanoprecipitation and chemically conjugated by the carboxylic group of PLGA to the amine-bearing CS polymer. The nanocarrier was characterized by dynamic light scattering, transmission electron microscopy, scanning electron microscopy, and differential scanning calorimetry as well as by in vitro drug release and cell culture studies. Results: NP size was within the tumour targeting range (~200 nm) with an effective positive charge (20 mV), thus increasing cellular uptake efficiency. Morphological analysis revealed clear spherical particles with uniform dispersion. The NPs exhibited identical sustained release kinetics for both DTX and ALN. CS-conjugated PLGA with dual-drug-loaded (DTX and AL) NPs showed typical time-dependent cellular uptake and also displayed superior cytotoxicity in MG-63 cells compared with blank NPs, which were safe and biocompatible. Conclusion: Combined loading of DTX and ALN in NPs increased the therapeutic efficacy of the formulation for osteosarcoma treatment, thus indicating the potential benefit of a combinatorial drug regimen using nanocarriers for effective treatment of osteosarcoma.

Tools For Spatiotemporally Specific Proteomic Analysis In Multicellular Organisms

The emergence of mass spectrometry-based proteomics has revolutionized the study of proteins and their abundances, functions, interactions, and modifications. However, in a multicellular organism, it is difficult to monitor dynamic changes in protein synthesis in a specific cell type within its native environment. In this thesis, we describe methods that enable the metabolic labeling, purification, and analysis of proteins in specific cell types and during defined periods in live animals. We first engineered a eukaryotic phenylalanyl-tRNA synthetase (PheRS) to selectively recognize the unnatural L-phenylalanine analog p-azido-L-phenylalanine (Azf). Using Caenorhabditis elegans, we expressed the engineered PheRS in a cell type of choice (i.e. body wall muscles, intestinal epithelial cells, neurons, pharyngeal muscles), permitting proteins in those cells -- and only those cells -- to be labeled with azides. Labeled proteins are therefore subject to "click" conjugation to cyclooctyne-functionalized affnity probes, separation from the rest of the protein pool and identification by mass spectrometry. By coupling our methodology with heavy isotopic labeling, we successfully identified proteins -- including proteins with previously unknown expression patterns -- expressed in targeted subsets of cells. While cell types like body wall or pharyngeal muscles can be targeted with a single promoter, many cells cannot; spatiotemporal selectivity typically results from the combinatorial action of multiple regulators. To enhance spatiotemporal selectivity, we next developed a two-component system to drive overlapping -- but not identical -- patterns of expression of engineered PheRS, restricting labeling to cells that express both elements. Specifically, we developed a split-intein-based split-PheRS system for highly efficient PheRS-reconstitution through protein splicing. Together, these tools represent a powerful approach for unbiased discovery of proteins uniquely expressed in a subset of cells at specific developmental stages.

É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.

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.