Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Innovative Strategies for the Synthesis of Biologically Active Small Molecules

The post genomic era, set the challenge to develop drugs that target an ever-growing list of proteins associated with diseases. However, an increase in the number of drugs approved every year is nowadays still not observed. To overcome this gap, innovative approaches should be applied in drug discovery for target validation, and at the same time organic synthetic chemistry has to find new fruitful strategies to obtain biologically active small molecules not only as therapeutic agents, but also as diagnostic tools to identify possible cellular targets. In this context, in view of the multifactorial mechanistic nature of cancer, new chimeric molecules, which can be either antitumor lead candidates, or valuable chemical tools to study molecular pathways in cancer cells, were developed using a multitarget-directed drug design strategy. According to this approach, the desired hybrid compounds were obtained by combining in a single chemical entity SAHA analogues, targeting histone deacetylases (HDACs), with substituted stilbene or terphenyl derivatives able to block cell cycle, to induce apoptosis and cell differentiation and with Sorafenib derivative, a multikinase inhibitor. The new chimeric derivatives were characterized with respect to their cytotoxic activity and their effects on cell cycle progression on leukemia Bcr-Abl-expressing K562 cell lines, as well as their HDACs inhibition. Preliminary results confirmed that one of the hybrid compounds has the desired chimeric profile. A distinct project was developed in the laboratory of Dr Spring, regarding the synthesis of a diversity-oriented synthesis (DOS) library of macrocyclic peptidomimetics. From a biological point of view, this class of molecules is extremely interesting but underrepresented in drug discovery due to the poor synthetic accessibility. Therefore it represents a valid challenge for DOS to take on. A build/couple/pair (B/C/P) approach provided, in an efficient manner and in few steps, the structural diversity and complexity required for such compounds.