Dans cette thèse, nous nous intéressons à la résolution exacte de programmes linéaires en variables binaires. L'ensemble de nos travaux s'articule autour de l'étude de Resolution search (Chvátal (1997)) pour la résolution du problème du sac à dos multidimensionnel en 0-1. Dans un premier temps, nous proposons un algorithme d'énumération implicite centré sur une analyse des coûts réduits à l'optimum de la relaxation continue ainsi que sur une décomposition de l'espace de recherche en hyperplans. Nous proposons une stratégie de branchement originale visant à élaguer au plus tôt l'arbre de recherche. Cette stratégie est efficace pour résoudre des instances jugées difficiles mais rend l'algorithme dépendant de la connaissance d'une bonne solution de départ. Dans un deuxième temps, nous proposons une méthode de résolution plus autonome combinant Resolution search avec une énumération implicite inspirée du premier algorithme. Cette coopération permet d'obtenir rapidement de bonnes solutions et prouve les optimums d'instances de plus grande taille. Finalement, nous présentons une application de Resolution Search à la résolution d'un problème de planification dans le domaine des télécommunications.

Cette thése étudie le problème NP-difficile de optimization quadratique en variables binaires (BQO), à savoir le problème de la maximisation d'une fonction quadratique en variables binaires. BQO peut représenter de nombreux problèmes importants de différents domaines et servir de modèle unifié pour un grand nombre de problèmes d'optimisation combinatoire portant sur les graphes. Cette thèse est consacrée au développement d'algorithmes métaheuristiques efficaces pour résoudre le BQO et ses applications. Premièrement, nous proposons algorithmes de "backbone guided" recherche tabou et d'un algorithme mémétique multi-niveaux sur la base de la technique de la fixation de variables. Ces techniques sont toutes deux basées sur l'idée de la réduction du problème afin de mener à bien une exploitation exhaustive d'une petite région de recherche. Ensuite, nous nous concentrons sur des procédés avancés de génération des solutions initiales préférables et développons des algorithmes combinant GRASP avec la recherche tabou et les algorithmes de path-relinking. En outre, nous résolvons des problèmes, y compris le problème de coupe maximum, de clique maximum, de clique maximale de sommets pondérés et la somme coloration minimum, soit en appliquant directement ou avec une légère adaptation de nos algorithmes développés pour BQO, avec l'hypothèse que ces problèmes sont reformulés en BQO. Enfin, nous présentons un algorithme mémétique basé sur la recherche tabou qui s'attaque efficacement au BQO avec contrainte de cardinalité.

Cette thèse s'intéresse à la résolution de problèmes inverses non linéaires exploitant un a priori de parcimonie ; plus particulièrement, des problèmes où les données se modélisent comme la combinaison linéaire d'un faible nombre de fonctions non linéaires en un paramètre dit de " localisation " (par exemple la fréquence en analyse spectrale ou le décalage temporel en déconvolution impulsionnelle). Ces problèmes se reformulent classiquement en un problème d'approximation parcimonieuse linéaire (APL) en évaluant les fonctions non linéaires sur une grille de discrétisation arbitrairement fine du paramètre de localisation, formant ainsi un " dictionnaire discret ". Cependant, une telle approche se heurte à deux difficultés majeures. D'une part, le dictionnaire provenant d'une telle discrétisation est fortement corrélé et met en échec les méthodes de résolution sous-optimales classiques comme la pénalisation L1 ou les algorithmes gloutons. D'autre part, l'estimation du paramètre de localisation, appartenant nécessairement à la grille de discrétisation, se fait de manière discrète, ce qui entraîne une erreur de modélisation. Dans ce travail nous proposons des solutions pour faire face à ces deux enjeux, d'une part via la prise en compte de la parcimonie de façon exacte en introduisant un ensemble de variables binaires, et d'autre part via la résolution " optimale " de tels problèmes sur " dictionnaire continu " permettant l'estimation continue du paramètre de localisation. Deux axes de recherches ont été suivis, et l'utilisation des algorithmes proposés est illustrée sur des problèmes de type déconvolution impulsionnelle et analyse spectrale de signaux irrégulièrement échantillonnés. Le premier axe de ce travail exploite le principe " d'interpolation de dictionnaire ", consistant en une linéarisation du dictionnaire continu pour obtenir un problème d'APL sous contraintes. L'introduction des variables binaires nous permet de reformuler ce problème sous forme de " programmation mixte en nombres entiers " (Mixed Integer Programming - MIP) et ainsi de modéliser de façon exacte la parcimonie sous la forme de la " pseudo-norme L0 ". Différents types d'interpolation de dictionnaires et de relaxation des contraintes sont étudiés afin de résoudre de façon optimale le problème grâce à des algorithmes classiques de type MIP. Le second axe se place dans le cadre probabiliste Bayésien, où les variables binaires nous permettent de modéliser la parcimonie en exploitant un modèle de type Bernoulli-Gaussien. Ce modèle est étendu (modèle BGE) pour la prise en compte de la variable de localisation continue. L'estimation des paramètres est alors effectuée à partir d'échantillons tirés avec des algorithmes de type Monte Carlo par Chaîne de Markov. Plus précisément, nous montrons que la marginalisation des amplitudes permet une accélération de l'algorithme de Gibbs dans le cas supervisé (hyperparamètres du modèle connu). De plus, nous proposons de bénéficier d'une telle marginalisation dans le cas non supervisé via une approche de type " Partially Collapsed Gibbs Sampler. " Enfin, nous avons adapté le modèle BGE et les algorithmes associés à un problème d'actualité en astrophysique : la détection d'exoplanètes par la méthode des vitesses radiales. Son efficacité sera illustrée sur des données simulées ainsi que sur des données réelles. / This thesis deals with solutions of nonlinear inverse problems using a sparsity prior; more specifically when the data can be modelled as a linear combination of a few functions, which depend non-linearly on a "location" parameter, i.e. frequencies for spectral analysis or time-delay for spike train deconvolution. These problems are generally reformulated as linear sparse approximation problems, thanks to an evaluation of the nonlinear functions at location parameters discretised on a thin grid, building a "discrete dictionary". However, such an approach has two major drawbacks. On the one hand, the discrete dictionary is highly correlated; classical sub-optimal methods such as L1- penalisation or greedy algorithms can then fail. On the other hand, the estimated location parameter, which belongs to the discretisation grid, is necessarily discrete and that leads to model errors. To deal with these issues, we propose in this work an exact sparsity model, thanks to the introduction of binary variables, and an optimal solution of the problem with a "continuous dictionary" allowing a continuous estimation of the location parameter. We focus on two research axes, which we illustrate with problems such as spike train deconvolution and spectral analysis of unevenly sampled data. The first axis focusses on the "dictionary interpolation" principle, which consists in a linearisation of the continuous dictionary in order to get a constrained linear sparse approximation problem. The introduction of binary variables allows us to reformulate this problem as a "Mixed Integer Program" (MIP) and to exactly model the sparsity thanks to the "pseudo-norm L0". We study different kinds of dictionary interpolation and constraints relaxation, in order to solve the problem optimally thanks to MIP classical algorithms. For the second axis, in a Bayesian framework, the binary variables are supposed random with a Bernoulli distribution and we model the sparsity through a Bernoulli-Gaussian prior. This model is extended to take into account continuous location parameters (BGE model). We then estimate the parameters from samples drawn using Markov chain Monte Carlo algorithms. In particular, we show that marginalising the amplitudes allows us to improve the sampling of a Gibbs algorithm in a supervised case (when the model's hyperparameters are known). In an unsupervised case, we propose to take advantage of such a marginalisation through a "Partially Collapsed Gibbs Sampler." Finally, we adapt the BGE model and associated samplers to a topical science case in Astrophysics: the detection of exoplanets from radial velocity measurements. The efficiency of our method will be illustrated with simulated data, as well as actual astrophysical data.

Ce travail porte sur la résolution exacte d'un problème d'optimisation combinatoire multi-objectif. Nous cherchons d'une part à confirmer l'efficacité de l'algorithme dit en deux phases, et d'autre part à poser une généralisation des procédures de séparation et évaluation, populaires dans le cadre mono-objectif mais presque absentes en multi-objectif. Notre étude s'appuie sur le problème multi-objectif de sac à dos unidimensionnel en variables binaires. Ce dernier est un classique de l'optimisation combinatoire, présent comme sous problème dans de nombreux problèmes d'optimisation. La première partie de nos travaux porte sur un pré-traitement permettant de réduire la taille d'instances de ce problème. Nous mettons en évidence plusieurs propriétés permettant de déterminer a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite à décrire une procédure performante de type deux phases pour ce problème, tout d'abord dans le cas bi-objectif. Nous étendons ensuite cette procédure pour des instances ayant trois objectifs ou plus. Les résultats obtenus sont comparés aux meilleurs algorithmes existants pour ce problème et confirment l'efficacité de l'approche en deux phases. La dernière partie de notre travail concerne la généralisation au cas multi-objectif d'une procédure de séparation et évaluation. Nous identifions plusieurs difficultés auxquelles nous répondons en proposant deux nouvelles procédures. Les expérimentations numériques indiquent que ces dernières permettent de résoudre des instances en des temps raisonnables, bien qu'elles n'atteignent pas les performances d'une procédure de type deux phases.