La recherche autonome est un nouveau domaine d'intérêt de la programmation par contraintes, motivé par l'importance reconnue de l'utilisation de l'apprentissage automatique pour le problème de sélection de l'algorithme le plus approprié pour une instance donnée, avec une variété d'applications, par exemple: Planification, Configuration d'horaires, etc. En général, la recherche autonome a pour but le développement d'outils automatiques pour améliorer la performance d'algorithmes de recherche, e.g., trouver la meilleure configuration des paramètres pour un algorithme de résolution d'un problème combinatoire. Cette thèse présente l'étude de trois points de vue pour l'automatisation de la résolution de problèmes combinatoires; en particulier, les problèmes de satisfaction de contraintes, les problèmes d'optimisation de combinatoire, et les problèmes de satisfiabilité (SAT).Tout d'abord, nous présentons domFD, une nouvelle heuristique pour le choix de variable, dont l'objectif est de calculer une forme simplifiée de dépendance fonctionnelle, appelée dépendance-relaxée. Ces dépendances-relaxées sont utilisées pour guider l'algorithme de recherche à chaque point de décision.Ensuite, nous révisons la méthode traditionnelle pour construire un portefeuille d'algorithmes pour le problème de la prédiction de la structure des protéines. Nous proposons un nouveau paradigme de recherche-perpétuelle dont l'objectif est de permettre à l'utilisateur d'obtenir la meilleure performance de son moteur de résolution de contraintes. La recherche-perpétuelle utilise deux modes opératoires: le mode d'exploitation utilise le modèle en cours pour solutionner les instances de l'utilisateur; le mode d'exploration réutilise ces instances pour s'entraîner et améliorer la qualité d'un modèle d'heuristiques par le biais de l'apprentissage automatique. Cette deuxième phase est exécutée quand l'unité de calcul est disponible (idle-time). Finalement, la dernière partie de cette thèse considère l'ajout de la coopération au cours d'exécution d'algorithmes de recherche locale parallèle. De cette façon, on montre que si on partage la meilleure configuration de chaque algorithme dans un portefeuille parallèle, la performance globale peut être considérablement amélioré.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can be readily extended to high order, in combination with the Newton-Krylov-Schur iterative method to produce a powerful parallel algorithm for the numerical solution of the Reynolds-averaged Navier-Stokes equations. The algorithm can efficiently solve the flow over a range of clean geometries, making it suitable for use at the core of an optimization algorithm.

Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can be readily extended to high order, in combination with the Newton-Krylov-Schur iterative method to produce a powerful parallel algorithm for the numerical solution of the Reynolds-averaged Navier-Stokes equations. The algorithm can efficiently solve the flow over a range of clean geometries, making it suitable for use at the core of an optimization algorithm.

This study argues for the influence of Friedrich Nietzsche's philosophy on Elizabeth Smart's novel, By Grand Central Station I Sat Down and Wept. Following Goran Hermeren's guidelines for an influence argument, I argue the case for Smart's contact with Nietzsche's work, similarities between his work and Smart's novel, and the effect of his work on Smart's novel. Nietzsche's conception of tragedy applies to and describes the novel surprisingly well, explaining certain similarities between the authors' works while identifying another of the text's many genres. The argument is largely based on circumstantial evidence, but its cumulative force is highly suggestive of a hitherto unrecognized philosophical complexity in Smart's novel.

Nowadays there is an ever increasing demand to obtain more accurate numericalsimulation results while at the same time using fewer computations. One area withsuch a demand is oil reservoir simulations, which builds upon Poisson's equation withvariable coefficients (PEWVC). This thesis focuses on applying and testing a high ordernumerical scheme to solve the PEWVC, namely Summation By Parts - SimultaneousApproximation Term (SBP-SAT). The thesis opens with proving that the method isconvergent at arbitrary high orders given sufficiently smooth coefficients. Theconvergence is furthermore verified in practice by test cases on the Poisson'sequation with smoothly variable permeability coefficients. To balance observed lowerboundary flux convergence, the SBP-SAT method was modified with additionalpenalty terms that were subsequently shown to work as expected. Finally theSBP-SAT method was tested on a semi-realistic model of an oil reservoir withdiscontinuous permeability. The correctness of the resulting pressure distributionvaried and it was shown that flux leakage was the probable cause. Hence theproposed SBP-SAT method performs, as expected, very well in continuous settingsbut typically allows undesirable leakage in discontinuous settings. There are possiblefixes, but these are outside the scope of this thesis.

Dans cette thèse nous développons de nouvelles techniques pour résoudre les problèmes d'optimisation multi-critère. Ces problèmes se posent naturellement dans de nombreux domaines d'application (sinon tous) où les choix sont évalués selon différents critères conflictuels (coûts et performance par exemple). Contrairement au cas de l'optimisation classique, de tels problèmes n'admettent pas en général un optimum unique mais un ensemble de solutions incomparables, aussi connu comme le front de Pareto, qui représente les meilleurs compromis possibles entre les objectifs conflictuels. La contribution majeure de la thèse est le développement d'algorithmes pour trouver ou approximer ces solutions de Pareto pour les problèmes combinatoires difficiles. Plusieurs problèmes de ce type se posent naturellement lors du processus de placement et d'ordonnancement d'une application logicielle sur une architecture multi-coeur comme P2012, qui est actuellement développé par STMicroelectronics.