Cette thèse s’inscrit dans le cadre de la conception, l’analyse et la mise en œuvre d’algorithmes efficaces et fiables pour la résolution de problèmes d’optimisation non linéaire avec contraintes. Nous présentons trois nouveaux algorithmes fortement primaux-duaux pour résoudre ces problèmes. La première caractéristique de ces algorithmes est que le contrôle des itérés s’effectue dans l’espace primal-dual tout au long du processus de la minimisation, d’où l’appellation “fortement primaux-duaux”. En particulier, la globalisation est effectuée par une méthode de recherche linéaire qui utilise une fonction de mérite primale-duale. La deuxième caractéristique est l’introduction d’une régularisation naturelle du système linéaire qui est résolu à chaque itération pour calculer une direction de descente. Ceci permet à nos algorithmes de bien se comporter pour résoudre les problèmes dégénérés pour lesquels la jacobienne des contraintes n’est pas de plein rang. La troisième caractéristique est que le paramètre de pénalisation est autorisé à augmenter au cours des itérations internes, alors qu’il est généralement maintenu constant. Cela permet de réduire le nombre d’itérations internes. Une étude théorique détaillée incluant l’analyse de convergence globale des itérations internes et externes, ainsi qu’une analyse asymptotique a été présentée pour chaque algorithme. En particulier, nous montrons qu’ils jouissent d’un taux de convergence rapide, superlinéaire ou quadratique. Ces algorithmes sont implémentés dans un nouveau solveur d’optimisation non linéaire qui est appelé SPDOPT. Les bonnes performances de ce solveur ont été montrées en effectuant des comparaisons avec les codes de références IPOPT, ALGENCAN et LANCELOT sur une large collection de problèmes. / This thesis focuses on the design, analysis, and implementation of efficient and reliable algorithms for solving nonlinearly constrained optimization problems. We present three new strongly primal-dual algorithms to solve such problems. The first feature of these algorithms is that the control of the iterates is done in both primal and dual spaces during the whole minimization process, hence the name “strongly primal-dual”. In particular, the globalization is performed by applying a backtracking line search algorithm based on a primal-dual merit function. The second feature is the introduction of a natural regularization of the linear system solved at each iteration to compute a descent direction. This allows our algorithms to perform well when solving degenerate problems for which the Jacobian of constraints is rank deficient. The third feature is that the penalty parameter is allowed to increase along the inner iterations, while it is usually kept constant. This allows to reduce the number of inner iterations. A detailed theoretical study including the global convergence analysis of both inner and outer iterations, as well as an asymptotic convergence analysis is presented for each algorithm. In particular, we prove that these methods have a high rate of convergence : superlinear or quadratic. These algorithms have been implemented in a new solver for nonlinear optimization which is called SPDOPT. The good practical performances of this solver have been demonstrated by comparing it to the reference codes IPOPT, ALGENCAN and LANCELOT on a large collection of test problems.

Depuis son introduction, la programmation mathématique à deux niveaux suscite un intérêt toujours croissant. En effet, vu ses applications dans une multitude de problèmes concrets (problèmes de gestion, planification économique, chimie, sciences environnementales,...), beaucoup de recherches ont été effectuées afin de contribuer à la résolution de cette classe de problèmes. Cette thèse est consacrée à l'étude de quelques classes de problèmes d'optimisation à deux niveaux, à savoir, les problèmes à deux niveaux forts, les problèmes à deux niveaux forts-faibles et les problèmes à deux niveaux semi-vectoriels. Le premier chapitre est consacré aux rappels de quelques définitions et résultats de topologie et d'analyse convexe que nous avons utilisé dans la suite. Dans le deuxième chapitre, nous avons rappelé quelques résultats théoriques et algorithmiques établis dans la littérature pour la résolution de quelques classes de problèmes d'optimisation à deux niveaux. Le troisième chapitre est consacré à l'étude d'un problème à deux niveaux fort-faible (SWBL). Vu la difficulté que présente cette classe de problèmes dans l'étude de l'existence de solutions, et afin de donner de nouvelles perspectives à leur résolution, nous avons procédé à une régularisation du problème. Sous des conditions suffisantes et via cette régularisation, nous avons montré que le problème (SWBL) admet au moins une solution. Dans le quatrième chapitre, nous avons donné une approche de dualité à un problème d'optimisation à deux niveaux fort (S). Cette approche est basée sur l'utilisation d'une régularisation et la dualité de Fenchel-Lagrange. En utilisant cette approche, nous avons donné des conditions nécessaires d'optimalité pour le problème (S). Enfin, des conditions suffisantes d'optimalité sont obtenues pour (S) sans utiliser l'approche. Une application concrète est donnée sur l'allocation de ressources. Dans le cinquième chapitre, nous avons étudié un problème à deux niveaux semi-vectoriel (SVBL). Pour ce problème, nous avons donné une approche de dualité en utilisant une régularisation, une scalarisation et la dualité de Fenchel-Lagrange. Puis, via cette approche et sous des hypothèses appropriées, nous avons donné des conditions nécessaires d'optimalité pour une classe de solutions du problème (SVBL). Finalement, des conditions suffisantes d'optimalité sont établies sont établies sans utiliser l'approche de dualité. / Since its introduction, the class of tao-level programming problems has attracted increasing interest. Indeed, because of its applications in a multitude of concrete problems (management problems, economic planning, chemistry, environmental sciences,...), several researchers have been interested in the study of such class of problems. This thesis deals with the study of some classes of two-level optimization problems, namely, strong two-level problems, strong-weak two-level problems and semi-vectorial two-level problems. In the first chapter, we have recalled some definitions and results related to topology and convex analysis that we have used in our study. In the second chapter, we have discussed some theoretical and algorithmic results established in the literature for solving some classes of two-level optimization problems. The third chapter deals with strong-weak Stackelberg problems. As it is well-known, such a class of problems presents difficulties in its study concerning the existence of solutions. So that, for a strong-weak two-level optimization problem, we have first given a regularization. Then, via this regularization and under appropriate assumptions we have shown the existence of solutions to such a problem. This result generalizes the one given in the literature for weak Stackelberg problems. In the fourth chapter, we have given a duality approach for a strong two-level programming problem (S). The duality approach is based on the use of a regularization and the Fenchel-Lagrange duality. Then, via this approach, we have given necessary optimality conditions for (S). Finally, sufficient optimality conditions are given for the initial problem (S). An application to a two-level resource allocation problem is given. In the fifth chapter, we have considered a semivectorial two-level programming problem (SVBL) where the upper and lower levels are vectorial and scalar respectively. For such a problem, we have given a duality approach based on the use of a regularization, a scalarization and the Fenchel-Lagrange duality. Then, via this approach we have established necessary optimality conditions for (SVBL). Finally, we have given sufficient optimality conditions without using the duality approach.

Plusieurs modèles pharmacocinétiques-pharmacodynamiques moléculaires ont été proposés au cours des dernières décennies afin de représenter et de prédire les effets d'un médicament dans les chimiothérapies anticancéreuses. La plupart de ces modèles ont été développés au niveau de la population de cellules, puisque des effets mesurables peuvent y être observés beaucoup plus facilement que dans les cellules individuelles.Cependant, les véritables cibles moléculaires des médicaments se trouvent au niveau de la cellule isolée. Les médicaments utilisés soit perturbent l'intégrité du génome en provoquant des ruptures de brins de l'ADN et par conséquent initialisent la mort cellulaire programmée (apoptose), soit bloquent la prolifération cellulaire, par inhibition des protéines (cdks) qui permettent aux cellules de procéder d'une phase du cycle cellulaire à la suivante en passant par des points de contrôle (principalement en $G_1/S$ et $G_2/M$). Les dommages à l'ADN causés par les médicaments cytotoxiques ou la $\gamma$-irradiation activent, entre autres, les voies de signalisation contrôlées par la protéine p53 qui forcent directement ou indirectement la cellule à choisir entre la survie et la mort.Cette thèse vise à explorer en détail les voies intracellulaires impliquant la protéine p53, ``le gardien du génome", qui sont initiées par des lésions de l'ADN, et donc de fournir un rationnel aux cancérologues pour prédire et optimiser les effets des médicaments anticancéreux en clinique. Elle décrit l'activation et la régulation de la protéine p53 dans les cellules individuelles après leur exposition à des agents causant des dommages à l'ADN. On montre que les comportements dynamiques qui ont été observés dans les cellules individuelles peuvent être reconstruits et prédits par fragmentation des événements cellulaires survenant après lésion de l'ADN, soit dans le noyau, soit dans le cytoplasme. Ceci est mis en œuvre par la description du réseau des protéines à l'aide d'équations différentielles ordinaires (EDO) et partielles (EDP) impliquant plusieurs agents dont les protéines ATM, p53, Mdm2 et Wip1, dans le noyau aussi bien que dans le cytoplasme, et entre les deux compartiments. Un rôle positif de Mdm2 dans la synthèse de p53, qui a été récemment observé, est exploré et un nouveau mécanisme provoquant les oscillations de p53 est proposé. On pourra noter en particulier que le nouveau modèle rend compte d'observations expérimentales qui n'ont pas pu être entièrement expliquées par les modèles précédents, par exemple, l'excitabilité de p53.En utilisant des méthodes mathématiques, on observe de près la façon dont un stimulus (par exemple, une $\gamma$-irradiation ou des médicaments utilisés en chimiothérapie) est converti en un comportement dynamique spécifiques (spatio-temporel) de p53, en particulier que ces dynamiques spécifiques de p53, comme messager de l'information cellulaire, peuvent moduler le cycle de division cellulaire, par exemple provoquant l'arrêt du cycle ou l'apoptose. Des modèles mathématiques EDO et EDP de réaction-diffusion sont utilisés pour examiner comment le comportement (spatio-temporel) de p53 émerge, et nous discutons des conséquences de ce comportement sur les réseaux moléculaires, avec des applications possibles dans le traitement du cancer.Les interactions protéine-protéine sont considérées comme des réactions enzymatiques. On présente quelques résultats mathématiques pour les réactions enzymatiques, en particulier on étudie le comportement en temps grand du système de réaction-diffusion pour la réaction enzymatique réversible à l'aide d'une approche entropique. À notre connaissance, c'est la première fois qu'une telle étude est publiée sur ce sujet. / Various molecular pharmacokinetic–pharmacodynamic models have been proposed in the last decades to represent and predict drug effects in anticancer therapies. Most of these models are cell population based models since clearly measurable effects of drugs can be seen on populations of (healthy and tumour) cells much more easily than in individual cells.The actual targets of drugs are, however, cells themselves. The drugs in use either disrupt genome integrity by causing DNA strand breaks and consequently initiate programmed cell death or block cell proliferation mainly by inhibiting proteins (cdks) that enable cells to proceed from one cell cycle phase to another. DNA damage caused by cytotoxic drugs or $\gamma$-irradiation activates, among others, the p53 protein-modulated signalling pathways that directly or indirectly force the cell to make a decision between survival and death.The thesis aims to explore closely intracellular pathways involving p53, ``the guardian of the genome", initiated by DNA damage and thus to provide oncologists with a rationale to predict and optimise the effects of anticancer drugs in the clinic. It describes p53 activation and regulation in single cells following their exposure to DNA damaging agents. We show that dynamical patterns that have been observed in individual cells can be reconstructed and predicted by compartmentalisation of cellular events occurring either in the nucleus or in the cytoplasm, and by describing protein interactions, using both ordinary and partial differential equations, among several key antagonists including ATM, p53, Mdm2 and Wip1, in each compartment and in between them. Recently observed positive role of Mdm2 in the synthesis of p53 is explored and a novel mechanism triggering oscillations is proposed. For example, new model can explain experimental observations that previous (not only our) models could not, e.g., excitability of p53.Using mathematical methods we look closely on how a stimulus (e.g., $\gamma$-radiation or drugs used in chemotherapy) is converted to a specific (spatio-temporal) pattern of p53 whereas such specific p53 dynamics as a transmitter of cellular information can modulate cellular outcomes, e.g., cell cycle arrest or apoptosis. Mathematical ODE and reaction-diffusion PDE models are thus used to see how the (spatio-temporal) behaviour of p53 is shaped and what possible applications in cancer treatment this behaviour might have. Protein-protein interactions are considered as enzyme reactions. We present some mathematical results for enzyme reactions, among them the large-time behaviour of the reaction-diffusion system for the reversible enzyme reaction treated by an entropy approach. To our best knowledge this is published for the first time.

Le premier objectif de cette thèse est de bien comprendre les propriétés de la dynamique du problème circulaire restreint des trois corps et de les utiliser pour calculer des missions pour satellites pourvus de moteurs à faible poussée. Une propriété fondamentale est l'existence de variétés invariantes associées à des orbites périodiques autour des points de \bsc{Lagrange}. En suivant l'idée de l'\emph{Interplanetary Transport Network}, la connaissance et le calcul des variétés invariantes, comme courants gravitationnels, sont cruciaux pour le \emph{design} de missions spatiales. Une grande partie de ce travail de thèse est consacrée au développement de méthodes numériques pour calculer le transfert entre variétés invariantes de façon optimale. Le coût que l'on cherche alors à minimiser est la norme $L^{1}$ du contrôle car elle est équivalente à minimiser la consommation des moteurs. On considère aussi la norme $L^{2}$ du contrôle car elle est, numériquement, plus facile à minimiser. Les méthodes numériques que nous utilisons sont des méthodes indirectes rendues plus robustes par des méthodes de continuation sur le coût, sur la poussée, et sur l'état final. La mise en œuvre de ces méthodes repose sur l'application du Principe du Maximum de Pontryagin. Les algorithmes développés dans ce travail permettent de calculer des missions réelles telles que des missions entre des voisinages des points de \bsc{Lagrange}. L'idée principale est d'initialiser un tir multiple avec une trajectoire admissible composée de parties contrôlées (des transferts locaux) et de parties non-contrôlées suivant la dynamique libre (les variétés invariantes). Les méthodes mises au point ici, sont efficaces et rapides puisqu'il suffit de quelques minutes pour obtenir la trajectoire optimale complète. Enfin, on développe une méthode hybride, avec à la fois des méthodes directes et indirectes, qui permettent d'ajuster la positions des points de raccord sur les variétés invariantes pour les missions à grandes variations d'énergie. Le gradient de la fonction valeur est donné par les valeurs des états adjoints aux points de raccord et donc ne nécessite pas de calculs supplémentaire. Ainsi, l'implémentation de algorithme du gradient est aisée. / The first objective of this work is to understand the dynamical properties of the circular restricted three body problem in order to use them to design low consumption missions for spacecrafts with a low thrust engine. A fundamental property is the existence of invariant manifolds associated with periodic orbits around Lagrange points. Following the Interplanetary Transport Network concept, invariant manifolds are very useful to design spacecraft missions because they are gravitational currents. A large part of this work is devoted to designing a numerical method that performs an optimal transfer between invariant manifolds. The cost we want to minimize is the $L^{1}$-norm of the control which is equivalent to minimizing the consumption of the engines. We also consider the $L^{2}$-norm of the control which is easier to minimize numerically. The numerical methods are indirect ones coupled with different continuations on the thrust, on the cost, and on the final state, to provide robustness. These methods are based on the application of the Pontryagin Maximum Principal. The algorithms developed in this work allow for the design of real life missions such as missions between the realms of libration points. The basic idea is to initialize a multiple shooting method with an admissible trajectory that contains controlled parts (local transfers) and uncontrolled parts following the natural dynamics (invariant manifolds). The methods developed here are efficient and fast (less than a few minutes to obtain the whole optimal trajectory). Finally, we develop a hybrid method, with both direct and indirect methods, to adjust the position of the matching points on the invariant manifolds for missions with large energy gaps. The gradient of the value function is given by the values of the costates at the matching points and does not require any additional computation. Hence, the implementation of the gradient descent is easy.

Let but de cette thèse est de proposer différents modèles mathématiques de neurones pour l'Optogénétique et d'étudier leur contrôle optimal. Nous définissons d'abord une version contrôlée des modèles déterministes de dimension finie, dits à conductances. Nous étudions un problème de temps minimal pour un système affine mono-entrée dont nous étudions les singulières. Nous appliquons une méthode numérique directe pour observer les trajectoires et contrôles optimaux. Le contrôle optogénétique apparaît comme une nouvelle façon de juger de la capacité des modèles à conductances de reproduire les caractéristiques de la dynamique du potentiel de membrane, observées expérimentalement. Nous définissons ensuite un modèle stochastique en dimension infinie pour prendre en compte le caractère aléatoire des mécanismes des canaux ioniques et la propagation des potentiels d'action. Il s'agit d'un processus de Markov déterministe par morceaux (PDMP) contrôlé, à valeurs dans un espace de Hilbert. Nous définissons une large classe de PDMPs contrôlés en dimension infinie et prouvons le caractère fortement Markovien de ces processus. Nous traitons un problème de contrôle optimal à horizon de temps fini. Nous étudions le processus de décision Markovien (MDP) inclus dans le PDMP et montrons l'équivalence des deux problèmes. Nous donnons des conditions suffisantes pour l'existence de contrôles optimaux pour le MDP, et donc le PDMP. Nous discutons des variantes pour le modèle d'Optogénétique stochastique en dimension infinie. Enfin, nous étudions l'extension du modèle à un espace de Banach réflexif, puis, dans un cas particulier, à un espace de Banach non réflexif. / The aim of this thesis is to propose different mathematical neuron models that take into account Optogenetics, and study their optimal control. We first define a controlled version of finite-dimensional, deterministic, conductance based neuron models. We study a minimal time problem for a single-input affine control system and we study its singular extremals. We implement a direct method to observe the optimal trajectories and controls. The optogenetic control appears as a new way to assess the capability of conductance-based models to reproduce the characteristics of the membrane potential dynamics experimentally observed. We then define an infinite-dimensional stochastic model to take into account the stochastic nature of the ion channel mechanisms and the action potential propagation along the axon. It is a controlled piecewise deterministic Markov process (PDMP), taking values in an Hilbert space. We define a large class of infinite-dimensional controlled PDMPs and we prove that these processes are strongly Markovian. We address a finite time optimal control problem. We study the Markov decision process (MDP) embedded in the PDMP. We show the equivalence of the two control problems. We give sufficient conditions for the existence of an optimal control for the MDP, and thus, for the initial PDMP as well. The theoretical framework is large enough to consider several modifications of the infinite-dimensional stochastic optogenetic model. Finally, we study the extension of the model to a reflexive Banach space, and then, on a particular case, to a nonreflexive Banach space.

Cette thèse s’insère dans le cadre général de l’étude de la dynamique des populations. La population prise en compte étant constituée de cellules souches normales et/ou cancéreuses. Nous proposons et analysons trois modèles mathématiques décrivant la dynamique de cellules souches. Le premier modèle proposé est un modèle d’équations aux dérivées partielles structurées en âge que nous transformons, via la méthode des caractéristiques, en un système d'équations différentielles à retard pour lequel on étudie l'existence et la stabilité des points d'équilibres. On effectue, après, des simulations numériques permettant d'illustrer le comportement des états d'équilibres. Dans le deuxième modèle, on considère que la durée du cycle cellulaire dépend de la population totale de cellules quiescentes. La méthode des caractéristiques nous permet de réduire notre modèle structuré en âge à un système d'équations différentielles avec un retard dépendant de l'état pour lequel on effectue une analyse détaillée de la stabilité. Nous confirmons, ensuite, les résultas analytiquement obtenus par des simulations numériques. Pour le troisième et dernier modèle de cette thèse, on propose un système d'équations différentielles ordinaires décrivant la dynamique de cellules souches saines et cancéreuses et prenant en compte leurs interactions avec les réponses immunitaires. Ce modèle nous a permis de souligner l'ampleur de l'impact que peuvent avoir différentes infections sur la prolifération tumoral que ce soit par le biais de leurs fréquences, leurs durées ou la façon dont ils agissent sur le système immunitaire. / This thesis fits into the general framework of the study of population dynamics. The population particularly considered in this work is comprised of stem cells with both cases of healthy and cancerous cells being investigated. We propose and analyze three mathematical models describing stem cells dynamics. The first model is an age-structured partial differential model that we reduce to a delay differential system using the characteristics method. We investigate the existence and stability of the steady states of the reduced delay differential system. We, then, conduct some numerical simulations to illustrate the behavior of the steady states. In the second model, the duration of the cell cycle is considered to depend upon the total population of quiescent cells. The method of characteristics reduces the age-structured model to a system of differentialequations with a state-dependent delay. We perform a detailed stability analysis of the resulting delay differential system. We confirm the analytical results by numerical simulations. The third and final model, proposed in this thesis, is an ordinary differential equations model describing healthy and cancerous stem cells dynamics and their interactions with immune system responses. Through this model, we show that the frequency, the duration of infections and their action (positive or negative) on immune responses may impact significantly tumor proliferation.

Cette thèse est consacrée la contrôlabilité lagrangienne, l'étude du champ de vitesse de l'Équation de Korteweg-de Vries, le problème de stabilisation rapide d'une équation aux dérivées partielles linéaires et aux méthodes numériques permettant d'obtenir la convergence des contrôles numériques vers les contrôles optimaux. Dans la première partie, on montre, l'aide de la solution de N-solitons de l'équation de Korteweg-de Vries, qu'il est possible de faire sortir des particules du fluide l’extérieur d'un domaine déterminé en temps arbitrairement petit. Une meilleure approximation du champ de vitesse associée la solution de N-solitons est également présentée, permettant de retrouver en particulier une propriété typique des trajectoires des particules soumises des ondes solitaires : les particules situées plus haut dans le fluide ont un plus grand déplacement. Dans la deuxième partie, la stabilisation rapide d'une équation de Schrödinger est obtenue grâce une méthode inspirée du backstepping en dimension infinie. Une équation de Schrödinger stable est considérée comme l'image d'une transformation ayant comme domaine de définition les solutions de l'équation de Schrödinger stabilisé. La stabilisation de l'équation de Schrödinger est obtenue en montrant l'inversibilité de la transformation. La nouveauté du travail présentée est l'introduction d'une condition d’unicité sur la transformation. Finalement, un filtre spectral, une formulation mixte et une formulation de Nitsche sont proposées comme technique afin d'obtenir numériquement l’observabilité uniforme de l'équation des ondes semi-discrétisée avec une méthode spectrale de Legendre-Galerkin. Une étude numérique de la convergence des contrôles numériques sans l’admissibilité uniforme de l’opérateur de contrôle est également présentée. / This thesis is devoted to the Lagrangian controllability and the analysis of the particle trajectories for the Korteweg-de Vries equation, to the rapid stabilization problem of the bilinear Schrödinger equation and to the convergence of the numerical controls of the wave equation. In the first part, we prove that the N-solitons solution of the Korteweg-de Vries equation allows one to move the particles outside an arbitrarily long domain in an arbitrarily small time. A higher approximation of the velocity field associated to the N-soliton is also presented, allowing to recover a typical property of solitary waves: the higher the particle is located in the fluid, the greater its displacement. These results are of a nonlinear nature since there exists no linear approximation of solitons. In the second part, inspired by the backstepping method, the rapid stabilization of a linearized Schrödinger equation is obtained. The proof consists to prove the invertibility of a transformation mapping the equation to stabilize to a stable linearized Schrödinger equation. The key ingredient of this proof is the introduction of a uniqueness condition. In the last part, a spectral filter, a mixed method and the Nitsche's method are proposed as a remedy to the lack of uniformness of the discrete observability constant for the Legendre-Galerkin semi-discretization of the wave equation. A numerical study of the convergence of the numerical controls is also presented.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

Le développement des nouvelles techniques de séquençage élargit l' horizon de la génétique de populations. Une analyse appropriée des données génétiques peut augmenter notre capacité à reconstruire l'histoire des populations. Cette énorme quantité de données disponibles peut aider les chercheurs en biologie et anthropologie à mieux estimer les changements démographiques subis par une population au cours du temps, mais induit aussi de nouveaux défis. Lorsque les modèles sous-jacents sont trop simplistes il existe unrisque très fort d'être amené à des conclusions erronées sur la population étudiée. Il a été montré que certaines caractéristiques présentes dans l'ADN des individus d'une population structurée se trouvent aussi dans l'ADN de ceux qui proviennent d'une population sans structure dont la taille a changé au cours du temps. Par conséquent il peut s'avérer très difficile de déterminer si les changements de taille inférés à partir des données génétiquesont vraiment eu lieu ou s'il s'agit simplement des effets liés à la structure. D'ailleurs la quasi totalité des méthodes pour inférer les changements de taille d'une population au cours du temps sont basées sur des modèles qui négligent la structure.Dans cette thèse, de nouveaux résultats de génétique de populations sont présentés. Premièrement, nous présentons une méthodologie permettant de faire de la sélection de modèle à partir de l'ADN d'un seul individudiploïde. Cette première étude se limite à un modèle simple de population non structurée avec un changement de taille et à un modèle considérant une population de taille constante mais structurée. Cette nouvelle méthode utilise la distribution des temps de coalescence de deux gènes pour identifier le modèle le plus probable et ouvreainsi la voie pour de nouvelles méthodes de sélection de modèles structurés et non structurés, à partir de données génomiques issues d'un seul individu. Deuxièmement, nous montrons, par une ré-interprétation du taux de coalescence que, pour n'importe quel scénario structuré, et plus généralement n'importe quel modèle, il existe toujours un scénario considérant une population panmictique avec une fonction précise de changements de taille dont la distribution des temps de coalescence de deux gènes est identique a celle du scénario structuré. Cela non seulement explique pourquoi les méthodes d'inférence démographique détectent souvent des changements de taille n'ayant peut-être jamais eu lieu, mais permet aussi de prédire les changements de taille qui seront reconstruits lorsque des méthodes basées sur l'hypothèse de panmixie sont appliquées à des données issues de scénarios plus complexes. Finalement, une nouvelle approche basée sur un processus de Markov est développée et permet de caractériser la distribution du temps de coalescence de deux gènes dans une population structurée soumise à des événements démographiques tel que changement de flux de gènes et changements de taille. Une discussion est menée afin de décrire comment cette méthode donne la possibilité de reconstruire l'histoire démographique à partir de données génomiques tout en considérant la structure. / The rapid development of DNA sequencing technologies is expanding the horizons of population genetic studies. It is expected that genomic data will increase our ability to reconstruct the history of populations.While this increase in genetic information will likely help biologists and anthropologists to reconstruct the demographic history of populations, it also poses big challenges. In some cases, simplicity of the model maylead to erroneous conclusions about the population under study. Recent works have shown that DNA patterns expected in individuals coming from structured populations correspond with those of unstructured populations with changes in size through time. As a consequence it is often difficult to determine whether demographic events such as expansions or contractions (bottlenecks) inferred from genetic data are real or due to the fact that populations are structured in nature. Moreover, almost no inferential method allowing to reconstruct pastdemographic size changes takes into account structure effects. In this thesis, some recent results in population genetics are presented: (i) a model choice procedure is proposed to distinguish one simple scenario of population size change from one of structured population, based on the coalescence times of two genes, showing that for these simple cases, it is possible to distinguish both models using genetic information form one single individual; (ii) by using the notion of instantaneous coalescent rate, it is demonstrated that for any scenario of structured population or any other one, regardless how complex it could be, there always exists a panmitic scenario with a precise function of population size changes havingexactly the same distribution for the coalescence times of two genes. This not only explains why spurious signals of bottlenecks can be found in structured populations but also predicts the demographic history that actual inference methods are likely to reconstruct when applied to non panmitic populations. Finally, (iii) a method based on a Markov process is developed for inferring past demographic events taking the structure into account. This is method uses the distribution of coalescence times of two genes to detect past demographic changes instructured populations from the DNA of one single individual. Some applications of the model to genomic data are discussed.

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire. / This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem.