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.

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

Search for the MSSM Neutral Higgs Boson in the mu+mu- final state with the CMS experiment at LHC

In this thesis, my work in the Compact Muon Solenoid (CMS) experiment on the search for the neutral Minimal Supersymmetric Standard Model (MSSM) Higgs decaying into two muons is presented. The search is performed on the full data collected during the years 2011 and 2012 by CMS in proton-proton collisions at CERN Large Hadron Collider (LHC). The MSSM is explored within the most conservative benchmark scenario, m_h^{max}, and within its modified versions, m_h^{mod +} and m_h^{mod -}. The search is sensitive to MSSM Higgs boson production in association with a b\bar{b} quark pair and to the gluon-gluon fusion process. In the m_h^{max} scenario, the results exclude values of tanB larger than 15 in the m_A range 115-200 GeV, and values of tanB greater than 30 in the m_A range up to 300 GeV. There are no significant differences in the results obtained within the three different scenarios considered. Comparisons with other neutral MSSM Higgs searches are shown.

Search for same-sign top quark pairs with the ATLAS detector at the LHC

In this thesis, a search for same-sign top quark pairs produced according to the Standard Model Effective Field Theory (SMEFT) is presented. The analysis is carried out within the ATLAS Collaboration using collision data at a center-of-mass energy of $\sqrt{s} = 13$ TeV, collected by the ATLAS detector during the Run 2 of the Large Hadron Collider, corresponding to an integrated luminosity of $140$ fb$^{-1}$. Three SMEFT operators are considered in the analysis, namely $\mathcal{O}_{RR}$, $\mathcal{O}_{LR}^{(1)}$, and $\mathcal{O}_{LR}^{(8)}$. The signal associated to same-sign top pairs is searched in the dilepton channel, with the top quarks decaying via $t \longrightarrow W^+ b \longrightarrow \ell^+ \nu b$, leading to a final state signature composed of a pair of high-transverse momentum same-sign leptons and $b$-jets. Deep Neural Networks are employed in the analysis to enhance sensitivity to the different SMEFT operators and to perform signal-background discrimination. This is the first result of the ATLAS Collaboration concerning the search for same-sign top quark pairs production in proton-proton collision data at $\sqrt{s} = 13$ TeV, in the framework of the SMEFT.