Algorithm creation and optimization for the crew pairing problem

Algoritmo que optimiza y crea pairings para tripulaciones de líneas aéreas mediante la posterior programación en Java.

A multi-objective model for a multi-period distribution management problem

The problems arising in commercial distribution are complex and involve several players and decision levels. One important decision is relatedwith the design of the routes to distribute the products, in an efficient and inexpensive way.This article deals with a complex vehicle routing problem that can beseen as a new extension of the basic vehicle routing problem. The proposed model is a multi-objective combinatorial optimization problemthat considers three objectives and multiple periods, which models in a closer way the real distribution problems. The first objective is costminimization, the second is balancing work levels and the third is amarketing objective. An application of the model on a small example, with5 clients and 3 days, is presented. The results of the model show the complexity of solving multi-objective combinatorial optimization problems and the contradiction between the several distribution management objective.

Iterated local search

Iterated Local Search has many of the desirable features of a metaheuristic: it is simple, easy to implement, robust, and highly effective. The essential idea of Iterated Local Search lies in focusing the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for a given optimization engine. The success of Iterated Local Search lies in the biased sampling of this set of local optima. How effective this approach turns out to be depends mainly on the choice of the local search, the perturbations, and the acceptance criterion. So far, in spite of its conceptual simplicity, it has lead to a number of state-of-the-art results without the use of too much problem-specific knowledge. But with further work so that the different modules are well adapted to the problem at hand, Iterated Local Search can often become a competitive or even state of the artalgorithm. The purpose of this review is both to give a detailed description of this metaheuristic and to show where it stands in terms of performance.

Assigning proctors to exams with scatter search

In this paper we present an algorithm to assign proctors toexams. This NP-hard problem is related to the generalized assignmentproblem with multiple objectives. The problem consists of assigningteaching assistants to proctor final exams at a university. We formulatethis problem as a multiobjective integer program (IP) with a preferencefunction and a workload-fairness function. We then consider also a weightedobjective that combines both functions. We develop a scatter searchprocedure and compare its outcome with solutions found by solving theIP model with CPLEX 6.5. Our test problems are real instances from aUniversity in Spain.

Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

Metaheuristics for the bus-driver scheduling problem

We present new metaheuristics for solving real crew scheduling problemsin a public transportation bus company. Since the crews of thesecompanies are drivers, we will designate the problem by the bus-driverscheduling problem. Crew scheduling problems are well known and severalmathematical programming based techniques have been proposed to solvethem, in particular using the set-covering formulation. However, inpractice, there exists the need for improvement in terms of computationalefficiency and capacity of solving large-scale instances. Moreover, thereal bus-driver scheduling problems that we consider can present variantaspects of the set covering, as for example a different objectivefunction, implying that alternative solutions methods have to bedeveloped. We propose metaheuristics based on the following approaches:GRASP (greedy randomized adaptive search procedure), tabu search andgenetic algorithms. These metaheuristics also present some innovationfeatures based on and genetic algorithms. These metaheuristics alsopresent some innovation features based on the structure of the crewscheduling problem, that guide the search efficiently and able them tofind good solutions. Some of these new features can also be applied inthe development of heuristics to other combinatorial optimizationproblems. A summary of computational results with real-data problems ispresented.

Exploiting fitness distance correlation of set covering problems

The set covering problem is an NP-hard combinatorial optimization problemthat arises in applications ranging from crew scheduling in airlines todriver scheduling in public mass transport. In this paper we analyze searchspace characteristics of a widely used set of benchmark instances throughan analysis of the fitness-distance correlation. This analysis shows thatthere exist several classes of set covering instances that have a largelydifferent behavior. For instances with high fitness distance correlation,we propose new ways of generating core problems and analyze the performanceof algorithms exploiting these core problems.

Exploring the effect of aminoglycoside guanidinylation on ligands for Tau exon 10 splicing regulatory element RNA

We describe the effect of guanidinylation of the aminoglycoside moiety on acridine-neamine-containing ligands for the stem-loop structure located at the exon 10-5′-intron junction of Tau pre-mRNA, an important regulatory element of tau gene alternative splicing. On the basis of dynamic combinatorial chemistry experiments, ligands that combine guanidinoneamine and two different acridines were synthesized and their RNA-binding properties were compared with those of their amino precursors. Fluorescence titration experiments and UV-monitored melting curves revealed that guanidinylation has a positive effect both on the binding affinity and specificity of the ligands for the stemloop RNA, as well as on the stabilization of all RNA sequences evaluated, particularly some mutated sequences associated with the development of FTDP-17 tauopathy. However, this correlation between binding affinity and stabilization due to guanidinylation was only found in ligands containing a longer spacer between the acridine and guanidinoneamine moieties, since a shorter spacer produced the opposite effect (e.g. lower binding affinity and lower stabilization). Furthermore, spectroscopic studies suggest that ligand binding does not significantly change the overall RNA structure upon binding (circular dichroism) and that the acridine moiety might intercalate near the bulged region of the stem->loop structure (UV-Vis and NMR spectroscopy).

Reconstruction of networks from their betweenness centrality

In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simulated annealing, as the combinatorial optimization method to generate the network from the values of the betweenness centrality. We compare the performance of this technique when reconstructing different categories of networks –random, regular, small-world, scale-free and clustered–. We show that the method allows an exact reconstruction of small networks and leads to good topological approximations in the case of networks with larger orders. The method can be used to generate a quasi-optimal topology fora communication network from a list with the values of the maximum allowable traffic for each node.

egr-4, a target of EGFR signaling, is required for the formation of the brian primordial and head regeneration in planarians

During the regeneration of freshwater planarians, polarity and patterning programs play essential roles in determining whether a head or a tail regenerates at anterior or posterior-facing wounds. This decision is made very soon after amputation. The pivotal role of the Wnt/β-catenin and Hh signaling pathways in re-establishing anterior-posterior (AP) polarity has been well documented. However, the mechanisms that control the growth and differentiation of the blastema in accordance with its AP identity are less well understood. Previous studies have described a role of Smed-egfr-3, a planarian epidermal growth factor receptor, in blastema growth and differentiation. Here, we identify Smed-egr-4, a zinc-finger transcription factor belonging to the early growth response gene family, as a putative downstream target of Smed-egfr-3. Smed-egr-4 is mainly expressed in the central nervous system and its silencing inhibits anterior regeneration without affecting the regeneration of posterior regions. Single and combinatorial RNA interference to target different elements of the Wnt/β-catenin pathway, together with expression analysis of brain- and anterior-specific markers, revealed that Smed-egr-4: (1) is expressed in two phases - an early Smed-egfr-3-independent phase and a late Smed-egfr-3-dependent phase; (2) is necessary for the differentiation of the brain primordia in the early stages of regeneration; and (3) that it appears to antagonize the activity of the Wnt/β-catenin pathway to allow head regeneration. These results suggest that a conserved EGFR/egr pathway plays an important role in cell differentiation during planarian regeneration and indicate an association between early brain differentiation and the proper progression of head regeneration.

Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

The role of fibroblast growth factor (FGF) and type beta transforming growth factot beta (TGF beta1, beta2 and beta3) during rat craniofacial development

Growth factors seem to be part of a complex cellular signalling language, in which individual growth factors are the equivalents of the letters that compose words. According to this analogy, informational content lies, not in an individual growth factor, but in the entire set of growth factors and others signals to which a cell is exposed. The ways in which growth factors exert their combinatorial effects are becoming clearer as the molecular mechanisms of growth factors actions are being investigated. A number of related extracellular signalling molecules that play widespread roles in regulating development in both invertebrates and vertebrates constitute the Fibroblast Growth Factor (FGF) and type beta Transforming Growth Factor ((TGF beta). The latest research literature about the role and fate of these Growth factors and their influence in the craniofacial bone growth ad development is reviewed

The role of fibroblast growth factor (FGF) and type beta transforming growth factot beta (TGF beta1, beta2 and beta3) during rat craniofacial development

Growth factors seem to be part of a complex cellular signalling language, in which individual growth factors are the equivalents of the letters that compose words. According to this analogy, informational content lies, not in an individual growth factor, but in the entire set of growth factors and others signals to which a cell is exposed. The ways in which growth factors exert their combinatorial effects are becoming clearer as the molecular mechanisms of growth factors actions are being investigated. A number of related extracellular signalling molecules that play widespread roles in regulating development in both invertebrates and vertebrates constitute the Fibroblast Growth Factor (FGF) and type beta Transforming Growth Factor ((TGF beta). The latest research literature about the role and fate of these Growth factors and their influence in the craniofacial bone growth ad development is reviewed

Uncovering the functional constraints underlying the genomic organisation of the Odorant-Binding Protein genes

Animal olfactory systems have a critical role for the survival and reproduction of individuals. In insects, the odorant-binding proteins (OBPs) are encoded by a moderately sized gene family, and mediate the first steps of the olfactory processing. Most OBPs are organized in clusters of a few paralogs, which are conserved over time. Currently, the biological mechanism explaining the close physical proximity among OBPs is not yet established. Here, we conducted a comprehensive study aiming to gain insights into the mechanisms underlying the OBP genomic organization. We found that the OBP clusters are embedded within large conserved arrangements. These organizations also include other non-OBP genes, which often encode proteins integral to plasma membrane. Moreover, the conservation degree of such large clusters is related to the following: 1) the promoter architecture of the confined genes, 2) a characteristic transcriptional environment, and 3) the chromatin conformation of the chromosomal region. Our results suggest that chromatin domains may restrict the location of OBP genes to regions having the appropriate transcriptional environment, leading to the OBP cluster structure. However, the appropriate transcriptional environment for OBP and the other neighbor genes is not dominated by reduced levels of expression noise. Indeed, the stochastic fluctuations in the OBP transcript abundance may have a critical role in the combinatorial nature of the olfactory coding process.

p-Nitrobenzyloxycarbonyl (pNZ) as Temporary Na-Protecting Group for Mild Solid-Phase Peptide Synthesis. Avoiding Diketopiperazine and Aspartimide Formation

p-Nitrobenzyloxycarbonyl was used as temporary protecting group for the -amino function in solid-phase peptide synthesis. The corresponding derivatives are solids, easy to be synthesized, and perform well in the solid-phase mode. pNZ is removed in practical neutral conditions in the presence of catalytic amounts of acid. They are orthogonal with the most common protecting groups used in peptide chemistry. They are specially useful in combination with Fmoc chemistry to overcome those side reactions associated with the used of the piperidine such DKP and aspartiimide formation. The flexibility of pNZ can be very useful for the preparation of libraries of small organic molecules.