The Algorithm Selection Problem is to select the most appropriate way for solving a problem given a choice of different ways. Some of the most prominent and successful applications come from Artificial Intelligence and in particular combinatorial search problems. Machine Learning has established itself as the de facto way of tackling the Algorithm Selection Problem. Yet even after a decade of intensive research, there are no established guidelines as to what kind of Machine Learning to use and how. This dissertation presents an overview of the field of Algorithm Selection and associated research and highlights the fundamental questions left open and problems facing practitioners. In a series of case studies, it underlines the difficulty of doing Algorithm Selection in practice and tackles issues related to this. The case studies apply Algorithm Selection techniques to new problem domains and show how to achieve significant performance improvements. Lazy learning in constraint solving and the implementation of the alldifferent constraint are the areas in which we improve on the performance of current state of the art systems. The case studies furthermore provide empirical evidence for the effectiveness of using the misclassification penalty as an input to Machine Learning. After having established the difficulty, we present an effective technique for reducing it. Machine Learning ensembles are a way of reducing the background knowledge and experimentation required from the researcher while increasing the robustness of the system. Ensembles do not only decrease the difficulty, but can also increase the performance of Algorithm Selection systems. They are used to much the same ends in Machine Learning itself. We finally tackle one of the great remaining challenges of Algorithm Selection -- which Machine Learning technique to use in practice. Through a large-scale empirical evaluation on diverse data taken from Algorithm Selection applications in the literature, we establish recommendations for Machine Learning algorithms that are likely to perform well in Algorithm Selection for combinatorial search problems. The recommendations are based on strong empirical evidence and additional statistical simulations. The research presented in this dissertation significantly reduces the knowledge threshold for researchers who want to perform Algorithm Selection in practice. It makes major contributions to the field of Algorithm Selection by investigating fundamental issues that have been largely ignored by the research community so far.

L’efficacité énergétique devient un domaine de recherche incontournable dans la communauté scientifique vu son importance dans la lutte contre les crises énergétiques actuelles et futures. L'analyse des performances énergétiques, pour les procédés industriels, nécessite la connaissance des grandeurs physiques impliquées dans les équilibres de masse et d'énergie. D’où la problématique : comment choisir les points de mesure sur un site industriel de façon à trouver les valeurs de tous les indicateurs énergétiques sans avoir des redondances de mesure (respect des contraintes économiques), et en conservant un niveau de précision des résultats ? La première partie présente la formulation du problème d’instrumentation ayant pour but de garantir une observabilité minimale du système en faveur des variables clés. Ce problème est combinatoire. Une méthode de validation des différentes combinaisons de capteurs a été introduite. Elle est basée sur l’interprétation structurelle de la matrice représentant le procédé. Le verrou de long temps de calcul lors du traitement des procédés de moyenne et grande taille a été levé. Des méthodes séquentielles ont été développées pour trouver un ensemble de schémas de capteurs pouvant être employés, en moins de 1% du temps de calcul initialement requis. La deuxième partie traite le choix du schéma d’instrumentation optimal. Le verrou de propagation des incertitudes dans un problème de taille variable a été levé. Une modélisation du procédé basée sur des paramètres binaires a été proposée pour automatiser les calculs, et évaluer les incertitudes des schémas trouvés. Enfin la méthodologie complète a été appliquée sur un cas industriel et les résultats ont été présentés. / Energy efficiency is becoming an essential research area in the scientific community given its importance in the fight against current and future energy crises. The analysis of the energy performances of the industrial processes requires the determination of the quantities involved in the mass and energy balances. Hence: how to choose the placement of the measurement points in an industrial site to find the values of all the energy indicators, without engendering an excess of unnecessary information due to redundancies (reducing measurements costs) and while respecting an accepted level of accuracy of the results ? The first part presents the formulation of the instrumentation problem which aims to guaranteeing a minimal observability of the system in favor of the key variables. This problem is combinatory. A method of validation of the different sensors combinations has been introduced. It is based on the structural interpretation of the matrix representing the process. The issue of long computing times while addressing medium and large processes was tackled. Sequential methods were developed to find a set of different sensor networks to be used satisfying the observability requirements, in less than 1% of the initial required computation time. The second part deals with the choice of the optimal instrumentation scheme. The difficulty of uncertainty propagation in a problem of variable size was addressed. To automate the evaluation of the uncertainty for all the found sensor networks, the proposed method suggested modeling the process based on binary parameters. Finally, the complete methodology is applied to an industrial case and the results were presented.