Spelling suggestions: "subject:"problème dde satisfaction dde contraintes"" "subject:"problème dde satisfaction dee contraintes""
1 |
Modélisation tridimensionnelle des ARN par exploration de l'espace conformationnel et satisfaction de contraintesThibault, Philippe January 2004 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
|
2 |
Intégration de techniques CSP pour la résolution du problème WCSP / Integration of CSP techniques to solve WCSPParis, Nicolas 06 November 2014 (has links)
Cette thèse se situe dans le contexte de la programmation par contraintes (CP). Plus précisément, nous nous sommes intéressés au problème de satisfaction de contraintes pondérées (WCSP). De nombreuses approches ont été proposées pour traiter ce problème d’optimisation. Les méthodes les plus efficaces utilisent des cohérences locales souples sophistiquées comme par exemple la cohérence d’arc directionnelle complète FDAC∗, la cohérence d’arc directionnelle existentielle EDAC∗, etc. Établies grâce à des opérations de transferts de coût préservant l’équivalence des réseaux, l’utilisation de ces cohérences permet généralement d’accélérer la résolution en réduisant l’espace de recherche via la suppression de valeurs et le calcul de bornes inférieures utiles en pratique. Cependant, l’utilisation de ces méthodes pose un problème lorsque l’arité des contraintes augmente de manière significative. L’efficacité des techniques du cadre du problème de satisfaction de contraintes (CSP) étant avérée, nous pensons que l’intégration de techniques CSP peut être très utile à la résolution d’instances WCSP. Dans cette thèse, nous proposons tout d’abord un algorithme de filtrage établissant la cohérence d’arc souple généralisée GAC∗ sur des contraintes tables souples de grande arité. Cette approche combine la technique de réduction tabulaire simple (STR), issue du cadre CSP, et le principe de transfert de coûts. Notre approche qui est polynomiale calcule efficacement pour chaque valeur les coûts minimaux dans les tuples explicites et implicites des contraintes tables souples. Ces coûts minimaux sont ensuite utilisés pour transférer les coûts afin d’établir GAC∗. Dans un second temps, nous proposons une approche alternative aux méthodes de résolution habituelles du problème WCSP. Elle consiste à résoudre une instance WCSP en résolvant une séquence d’instances CSP classiques obtenues depuis cette instance WCSP. À partir d’une instance CSP dans laquelle toutes les contraintes de l’instanceWCSP d’origine sont durcies au maximum, les instances CSP suivantes correspondent à un relâchement progressif de contraintes de l’instance WCSP déterminées par l’extraction de noyaux insatisfaisables minimaux (MUC) depuis les réseaux insatisfaisables de la séquence. Nos résultats expérimentaux montrent que notre première approche est compétitive avec l’état de l’art, tandis que la deuxième représente une approche alternative aux méthodes de résolutionhabituelles d’instances WCSP. / This thesis is in the context of constraint programming (CP). Specifically, we are interested in the Weighted Constraint Satisfaction Problem (WCSP). Many approaches have been proposed to handle this optimization problem. The most effective methods use sophisticated soft local consistencies such as, for example, full directional arc consistency FDAC∗, existential directional arc consistency EDAC∗, etc. Established by equivalence preserving transformations (cost transfer operations), the use of these consistencies generally allows both to accelerate the resolution by reducing the search space through the elimination of values and to compute lower bounds useful in practice. However, these methods reach theirlimits when the arity of constraints increases significantly. The techniques of the Constraint Satisfaction Problem framework (CSP) having proved efficienty, we believe that the integration of CSP techniques can be very useful for solving WCSP instances. In this thesis, we first propose a filtering algorithm to enforce a soft version of generalized arc consistency (GAC∗) on soft table constraints of large arity. This approach combines the techniques of simple tabular reduction (STR), from the CSP framework, with the techniques of cost transfer. Our approach, proved polynomial, efficiently calculates for each value the minimum cost of the explicit and implicit tuples from soft table constraints. The minimum costs are thenused to transfer costs to establish GAC∗. In a second step, we propose an alternative approach to the usual techniques to solve WCSP. The principle is to solve a WCSP instance by solving a sequence of classical CSP instances obtained from this WCSP instance. From a CSP instance containing all the constraints hardened to the maximum from the WCSP instance, the next CSP instances correspond to a progressive relaxation of constraints defined by extraction of minimal unsatisfiable cores (MUC) from unsatisfiable networks of the sequence. Our experimental results show that our first approach is competitive with the state-of-the-art, whereas the second one represents an alternative approach to the usual methods to solve WCSP instances.
|
3 |
Formulation préalable d'un problème de conception, pour l'aide à la décision en conception préliminaireSCARAVETTI, Dominique 03 December 2004 (has links) (PDF)
La conception architecturale est souvent réalisée grâce aux habitudes professionnelles et à l'expérience des concepteurs, qui leur permettent d'identifier les paramètres de conception pertinents à prendre en compte pour commencer l'étude et de faire les choix qu'impliquent une démarche séquentielle de détermination d'architecture. Ces décisions sont difficiles à prendre car les concepteurs ne disposent pas forcément d'éléments suffisants pour comparer les différentes alternatives. Ainsi, ils procèdent souvent par essai-erreur, jusqu'à l'obtention d'une configuration opérationnelle, mais qui n'est pas nécessairement optimale. Ces itérations sont, de plus, coûteuses en temps.<br /><br />Nous proposons un système d'aide à la décision en conception préliminaire, permettant de partir de plusieurs concepts de solution pertinents, pour arriver à une architecture validée et prédimensionnée en objectivant les choix de conception. <br />Les grandes étapes sont : (i) l'écriture du problème de conception préliminaire sous forme de Problème par Satisfaction de Contraintes (PSC), (ii) la recherche exhaustive des architectures solutions, (iii) l'exploitation et la réduction de l'espace des solutions pour aider à la décision. C'est seulement ensuite qu'un choix est à faire parmi ces solutions, qui n'ont pas été arbitrairement restreintes par des choix initiaux.<br /><br />Les étapes (i) et (iii) nécessitent une analyse préalable du problème de conception. Il faut, d'une part, le limiter aux seules caractéristiques nécessaires et suffisantes pour la conception architecturale, que nous nommons caractéristiques structurantes. D'autre part, il faut exprimer les objectifs de conception et les critères de qualification de la conception, qui permettent de hiérarchiser les architectures-solutions obtenues et ainsi aider au choix final parmi elles.<br />Nous proposons pour cela une démarche systématique d'analyse et structuration du problème de conception, basée sur quatre étapes, depuis l'analyse du besoin jusqu'à une approche physique, en passant par des approches fonctionnelle et organique du produit à concevoir. Des tableaux systématiques sont proposés.<br /><br />Notre approche est confrontée avec la démarche 'classique' d'un groupe de concepteurs, pour une même conception architecturale. L'utilisation du système d'aide à la décision permet une amélioration de la satisfaction des objectifs de conception, le choix du concept de solution le plus performant, l'obtention d'architectures-solutions valides et respectant toutes les contraintes énoncées. On dispose ainsi d'éléments dimensionnels pour poursuivre en conception détaillée sans subir les itérations engendrées par le processus essai-erreur.
|
4 |
Formalisation et qualification de modèles par contraintes en conception préliminaireVernat, Yoann 11 1900 (has links) (PDF)
La conception architecturale constitue une étape complexe du développement d'un produit, car elle implique: (i) une prise de décision dans un contexte où les données du problème sont mal définies ou imprécises, (ii) une exploration de l'espace des solutions qui doit rester aussi large que possible, (iii) des choix de conception basés sur des variables continues ou discrètes, et (iv) une optimisation multidisciplinaire. Ainsi, les modèles de simulation classiquement utilisés en conception sont souvent mal adaptés à une réelle prise de décision: certains modèles sont trop simples, les choix sont alors entachés d'erreur de modélisation, d'autres sont trop spécialisés et certaines solutions risquent d'être ignorées. Nous proposons dans cette étude une approche de la formalisation de modèles plus adaptée à la prise de décision en conception architecturale. Cette méthodologie vise à obtenir des modèles à la fois parcimonieux et exacts. Ainsi, les modèles sont plus faciles à exploiter en conception préliminaire et cohérents avec les attentes du concepteur. La méthode développée repose sur: (i) une approche globale basée sur la décomposition fonctionnelle pour conserver une cohérence entre les modèles des différents composants, (ii) l'utilisation de quatre critères de qualification des modèles permettant de s'assurer de leur adéquation avec les objectifs de la conception préliminaire, (iii) l'utilisation des techniques d'adaptation de modèles, permettant de faire des choix de conception à l'aide de solveurs de Problèmes par Satisfaction de Contraintes (PSC). Les quatre critères de qualification utilisés sont: (i) la parcimonie du modèle, liée au nombre minimal de variables et d'équations décrivant correctement le comportement du système, (ii) l'exactitude du modèle, estimant l'adéquation entre les résultats du modèle et des résultats issus d'un modèle de référence, (iii) la précision du modèle, évaluant l'étendue du domaine de variation de chaque variable, due à un manque de connaissance ou à une incertitude et (iv) la spécialisation du modèle, qui est une mesure de la restriction du domaine d'application du modèle, relativement à la quantité d'information introduite dans le modèle. Les quatre critères retenus sont pertinents de la conception préliminaire dans la mesure où: la parcimonie assure la simplicité du modèle, la spécialisation contribue à définir l'étendue du domaine d'application du modèle, et donc les limites de l'espace de conception, enfin, l'exactitude et la précision donnent une mesure de la fidélité du modèle à la réalité. Utilisés au cours de la méthodologie proposée, ces critères constituent un moyen de contrôle des modèles jusqu'à atteindre la forme souhaitée. Enfin, cette méthodologie est illustrée au travers de l'exemple d'une batterie de véhicule électrique, pour lequel deux modèles de niveaux systémiques différents sont comparés.
|
5 |
Unfolding RNA 3D structures for secondary structure prediction benchmarkingC-Parent, Gabriel 01 1900 (has links)
Les acides ribonucléiques (ARN) forment des structures tri-dimensionnelles complexes
stabilisées par la formation de la structure secondaire (2D), elle-même formée de paires
de bases. Plusieurs méthodes computationnelles ont été créées dans les dernières années
afin de prédire la structure 2D d’ARNs, en partant de la séquence. Afin de simplifier
le calcul, ces méthodes appliquent généralement des restrictions sur le type de paire de
bases et la topologie des structures 2D prédites. Ces restrictions font en sorte qu’il est
parfois difficile de savoir à quel point la totalité des paires de bases peut être représentée
par ces structures 2D restreintes.
MC-Unfold fut créé afin de trouver les structures 2D restreintes qui pourraient être associées à une structure secondaire complète, en fonction des restrictions communément
utilisées par les méthodes de prédiction de structure secondaire.
Un ensemble de 321 monomères d’ARN totalisant plus de 4223 structures fut assemblé
afin d’évaluer les méthodes de prédiction de structure 2D. La majorité de ces structures
ont été déterminées par résonance magnétique nucléaire et crystallographie aux rayons
X. Ces structures ont été dépliés par MC-Unfold et les structures résultantes ont été comparées à celles prédites par les méthodes de prédiction.
La performance de MC-Unfold sur un ensemble de structures expérimentales est encourageante. En moins de 5 minutes, 96% des 227 structures ont été complètement dépliées,
le reste des structures étant trop complexes pour être déplié rapidement. Pour ce qui est
des méthodes de prédiction de structure 2D, les résultats indiquent qu’elles sont capable
de prédire avec un certain succès les structures expérimentales, particulièrement les petites molécules. Toutefois, si on considère les structures larges ou contenant des pseudo-noeuds, les résultats sont généralement défavorables. Les résultats obtenus indiquent que
les méthodes de prédiction de structure 2D devraient être utilisées avec prudence, particulièrement pour de larges molécules. / Ribonucleic acids (RNA) adopt complex three dimensional structures which are stabilized by the formation of base pairs, also known as the secondary (2D) structure. Predicting where and how many of these interactions occur has been the focus of many computational methods called 2D structure prediction algorithms. These methods disregard
some interactions, which makes it difficult to know how well a 2D structure represents
an RNA structure, especially when large amounts of base pairs are ignored.
MC-Unfold was created to remove interactions violating the assumptions used by prediction methods. This process, named unfolding, extends previous planarization and
pseudoknot removal methods. To evaluate how well computational methods can predict
experimental structures, a set of 321 RNA monomers corresponding to more than 4223
experimental structures was acquired. These structures were mostly determined using
nuclear magnetic resonance and X-ray crystallography. MC-Unfold was used to remove
interactions the prediction algorithms were not expected to predict. These structures
were then compared with the structured predicted.
MC-Unfold performed very well on the test set it was given. In less than five minutes,
96% of the 227 structure could be exhaustively unfolded. The few remaining structures
are very large and could not be unfolded in reasonable time. MC-Unfold is therefore a
practical alternative to the current methods.
As for the evaluation of prediction methods, MC-Unfold demonstrated that the computational methods do find experimental structures, especially for small molecules. However,
when considering large or pseudoknotted molecules, the results are not so encouraging.
As a consequence, 2D structure prediction methods should be used with caution, especially for large structures.
|
6 |
Estimations de satisfaisabilitéHugel, Thomas 07 December 2010 (has links) (PDF)
Le problème de satisfaisabilité booléenne 3-SAT est connu pour présenter un phénomène de seuil en fonction du quotient entre le nombre de clauses et le nombre de variables. Nous donnons des estimations de la valeur de ce seuil au moyen de méthodes combinatoires et probabilistes: la méthode du premier moment et la méthode du second moment. Ces méthodes mettent en jeu des problèmes d'optimisation sous contraintes et nous amènent à employer de façon intensive la méthode des multiplicateurs de Lagrange. Nous mettons en œuvre une forme pondérée de la méthode du premier moment sur les affectations partielles valides de Maneva ainsi que des variantes. Cela nous conduit à élaborer une pondération générale pour les problèmes de satisfaction de contraintes qui soit compatible avec la méthode du premier moment. Cette pondération est constituée d'une graine et d'un répartiteur, et nous permet d'obtenir une pondération des affectations partielles valides meilleure que celle de Maneva. Nous comparons aussi dans certains cas les performances de la pondération et de l'orientation de l'espace des solutions des problèmes de satisfaction de contraintes relativement à la méthode du premier moment. Nous développons la première sélection non uniforme de solutions pour majorer le seuil de 3-SAT et nous montrons sa supériorité sur ses prédécesseurs. Nous construisons un cadre général pour appliquer la méthode du second moment à k-SAT et nous discutons des conditions qui la font fonctionner. Nous faisons notamment fonctionner la méthode du second moment sur les solutions booléennes et sur les impliquants. Nous étendons cela au modèle distributionnel de k-SAT.
|
7 |
Méthodes ensemblistes pour la localisation en robotique mobileGuyonneau, Rémy 19 November 2013 (has links) (PDF)
Cette thèse s'intéresse aux problèmes de localisation en robotique mobile, et plus particulièrement à l'intérêt d'une approche ensembliste pour ces problèmes. Actuellement les méthodes probabilistes sont les plus utilisées pour localiser un robot dans son environnement, cette thèse propose des approches alternatives basées sur l'analyse par intervalles. Dans un premier temps, une méthode ensembliste s'intéressant au problème de localisation globale est proposée. Le problème de localisation globale correspond à la localisation d'un robot dans son environnement, sans connaissance à priori sur sa posture (position et orientation) initiale. La méthode proposée associe le problème de localisation à un problème de satisfaction de contraintes (CSP). Elle permet de localiser le robot en utilisant la connaissance de l'environnement, ainsi qu'un jeu de mesures LIDAR. Cette méthode est validée à l'aide de différentes expérimentations et est comparée à une approche probabiliste classique : la Localisation Monte Carlo (MCL). Dans un second temps une notion de visibilité est étudiée. Deux points sont supposés visibles, si le segment défini par ces deux points n'intersecte pas d'obstacle, autrement ils sont dit non-visibles. À l'aide de l'analyse par intervalles, des contracteurs associés à cette notion de visibilité sont développés. Après une présentation théorique de la visibilité, deux applications de ces contracteurs à la localisation en robotique mobile sont présentées : le suivi de posture d'une meute de robots à l'aide d'une information booléenne, et la prise en compte d'une contrainte supplémentaire dans le CSP associé à la localisation globale.
|
8 |
Contribution à l'évaluation des risques liés au TMD (transport de matières dangereuses) en prenant en compte les incertitudes / Contribution to the risk assessment related to DGT (dangerous goods transportation) by taking into account uncertaintiesSafadi, El Abed El 09 July 2015 (has links)
Le processus d'évaluation des risques technologiques, notamment liés au Transport de Matières Dangereuses (TMD), consiste, quand un événement accidentel se produit, à évaluer le niveau de risque potentiel des zones impactées afin de pouvoir dimensionner et prendre rapidement des mesures de prévention et de protection (confinement, évacuation...) dans le but de réduire et maitriser les effets sur les personnes et l'environnement. La première problématique de ce travail consiste donc à évaluer le niveau de risque des zones soumises au transport des matières dangereuses. Pour ce faire, un certain nombre d'informations sont utilisées, comme la quantification de l'intensité des phénomènes qui se produisent à l'aide de modèles d'effets (analytique ou code informatique). Pour ce qui concerne le problème de dispersion de produits toxiques, ces modèles contiennent principalement des variables d'entrée liées à la base de données d'exposition, de données météorologiques,… La deuxième problématique réside dans les incertitudes affectant certaines entrées de ces modèles. Pour correctement réaliser une cartographie en déterminant la zone de de danger où le niveau de risque est jugé trop élevé, il est nécessaire d'identifier et de prendre en compte les incertitudes sur les entrées afin de les propager dans le modèle d'effets et ainsi d'avoir une évaluation fiable du niveau de risque. Une première phase de ce travail a consisté à évaluer et propager l'incertitude sur la concentration qui est induite par les grandeurs d'entrée incertaines lors de son évaluation par les modèles de dispersion. Deux approches sont utilisées pour modéliser et propager les incertitudes : l'approche ensembliste pour les modèles analytiques et l'approche probabiliste (Monte-Carlo) qui est plus classique et utilisable que le modèle de dispersion soit analytique ou défini par du code informatique. L'objectif consiste à comparer les deux approches pour connaitre leurs avantages et inconvénients en termes de précision et temps de calcul afin de résoudre le problème proposé. Pour réaliser les cartographies, deux modèles de dispersion (Gaussien et SLAB) sont utilisés pour évaluer l'intensité des risques dans la zone contaminée. La réalisation des cartographies a été abordée avec une méthode probabiliste (Monte Carlo) qui consiste à inverser le modèle d'effets et avec une méthode ensembliste générique qui consiste à formuler ce problème sous la forme d'un ensemble de contraintes à satisfaire (CSP) et le résoudre ensuite par inversion ensembliste. La deuxième phase a eu pour but d'établir une méthodologie générale pour réaliser les cartographies et améliorer les performances en termes de temps du calcul et de précision. Cette méthodologie s'appuie sur 3 étapes : l'analyse préalable des modèles d'effets utilisés, la proposition d'une nouvelle approche pour la propagation des incertitudes mixant les approches probabiliste et ensembliste en tirant notamment partie des avantages des deux approches précitées, et utilisable pour n'importe quel type de modèle d'effets spatialisé et statique, puis finalement la réalisation des cartographies en inversant les modèles d'effets. L'analyse de sensibilité présente dans la première étape s'adresse classiquement à des modèles probabilistes. Nous discutons de la validité d'utiliser des indices de type Sobol dans le cas de modèles intervalles et nous proposerons un nouvel indice de sensibilité purement intervalle cette fois-ci. / When an accidental event is occurring, the process of technological risk assessment, in particular the one related to Dangerous Goods Transportation (DGT), allows assessing the level of potential risk of impacted areas in order to provide and quickly take prevention and protection actions (containment, evacuation ...). The objective is to reduce and control its effects on people and environment. The first issue of this work is to evaluate the risk level for areas subjected to dangerous goods transportation. The quantification of the intensity of the occurring events needed to do this evaluation is based on effect models (analytical or computer code). Regarding the problem of dispersion of toxic products, these models mainly contain inputs linked to different databases, like the exposure data and meteorological data. The second problematic is related to the uncertainties affecting some model inputs. To determine the geographical danger zone where the estimated risk level is not acceptable, it is necessary to identify and take in consideration the uncertainties on the inputs in aim to propagate them in the effect model and thus to have a reliable evaluation of the risk level. The first phase of this work is to evaluate and propagate the uncertainty on the gas concentration induced by uncertain model inputs during its evaluation by dispersion models. Two approaches are used to model and propagate the uncertainties. The first one is the set-membership approach based on interval calculus for analytical models. The second one is the probabilistic approach (Monte Carlo), which is more classical and used more frequently when the dispersion model is described by an analytic expression or is is defined by a computer code. The objective is to compare the two approaches to define their advantages and disadvantages in terms of precision and computation time to solve the proposed problem. To determine the danger zones, two dispersion models (Gaussian and SLAB) are used to evaluate the risk intensity in the contaminated area. The risk mapping is achieved by using two methods: a probabilistic method (Monte Carlo) which consists in solving an inverse problem on the effect model and a set-membership generic method that defines the problem as a constraint satisfaction problem (CSP) and to resolve it with an set-membership inversion method. The second phase consists in establishing a general methodology to realize the risk mapping and to improve performance in terms of computation time and precision. This methodology is based on three steps: - Firstly the analysis of the used effect model. - Secondly the proposal of a new method for the uncertainty propagationbased on a mix between the probabilistic and set-membership approaches that takes advantage of both approaches and that is suited to any type of spatial and static effect model. -Finally the realization of risk mapping by inversing the effect models. The sensitivity analysis present in the first step is typically addressed to probabilistic models. The validity of using Sobol indices for interval models is discussed and a new interval sensitivity indiceis proposed.
|
9 |
Statistical Physics of Sparse and Dense Models in Optimization and Inference / Physique statistique des modèles épars et denses en optimisation et inférenceSchmidt, Hinnerk Christian 10 October 2018 (has links)
Une donnée peut avoir diverses formes et peut provenir d'un large panel d'applications. Habituellement, une donnée possède beaucoup de bruit et peut être soumise aux effets du hasard. Les récents progrès en apprentissage automatique ont relancé les recherches théoriques sur les limites des différentes méthodes probabilistes de traitement du signal. Dans cette thèse, nous nous intéressons aux questions suivantes : quelle est la meilleure performance possible atteignable ? Et comment peut-elle être atteinte, i.e., quelle est la stratégie algorithmique optimale ?La réponse dépend de la forme des données. Les sujets traités dans cette thèse peuvent tous être représentés par des modèles graphiques. Les propriétés des données déterminent la structure intrinsèque du modèle graphique correspondant. Les structures considérées ici sont soit éparses, soit denses. Les questions précédentes peuvent être étudiées dans un cadre probabiliste, qui permet d'apporter des réponses typiques. Un tel cadre est naturel en physique statistique et crée une analogie formelle avec la physique des systèmes désordonnés. En retour, cela permet l'utilisation d'outils spécifiques à ce domaine et de résoudre des problèmes de satisfaction de contraintes et d'inférence statistique. La problématique de performance optimale est directement reliée à la structure des extrema de la fonction d'énergie libre macroscopique, tandis que les aspects algorithmiques proviennent eux de la minimisation de la fonction d'énergie libre microscopique (c'est-à-dire, dans la forme de Bethe).Cette thèse est divisée en quatre parties. Premièrement, nous aborderons par une approche de physique statistique le problème de la coloration de graphes aléatoires et mettrons en évidence un certain nombre de caractéristiques. Dans un second temps, nous calculerons une nouvelle limite supérieure de la taille de l'ensemble contagieux. Troisièmement, nous calculerons le diagramme de phase du modèle de Dawid et Skene dans la région dense en modélisant le problème par une factorisation matricielle de petit rang. Enfin, nous calculerons l'erreur optimale de Bayes pour une classe restreinte de l'estimation matricielle de rang élevé. / Datasets come in a variety of forms and from a broad range of different applications. Typically, the observed data is noisy or in some other way subject to randomness. The recent developments in machine learning have revived the need for exact theoretical limits of probabilistic methods that recover information from noisy data. In this thesis we are concerned with the following two questions: what is the asymptotically best achievable performance? And how can this performance be achieved, i.e., what is the optimal algorithmic strategy? The answer depends on the properties of the data. The problems in this thesis can all be represented as probabilistic graphical models. The generative process of the data determines the structure of the underlying graphical model. The structures considered here are either sparse random graphs or dense (fully connected) models. The above questions can be studied in a probabilistic framework, which leads to an average (or typical) case answer. Such a probabilistic formulation is natural to statistical physics and leads to a formal analogy with problems in disordered systems. In turn, this permits to harvest the methods developed in the study of disordered systems, to attack constraint satisfaction and statistical inference problems. The formal analogy can be exploited as follows. The optimal performance analysis is directly related to the structure of the extrema of the macroscopic free energy. The algorithmic aspects follow from the minimization of the microscopic free energy (that is, the Bethe free energy in this work) which is closely related to message passing algorithms. This thesis is divided into four contributions. First, a statistical physics investigation of the circular coloring problem is carried out that reveals several distinct features. Second, new rigorous upper bounds on the size of minimal contagious sets in random graphs, with bounded maximum degree, are obtained. Third, the phase diagram of the dense Dawid-Skene model is derived by mapping the problem onto low-rank matrix factorization. The associated approximate message passing algorithm is evaluated on real-world data. Finally, the Bayes optimal denoising mean square error is derived for a restricted class of extensive rank matrix estimation problems.
|
10 |
Harnessing tractability in constraint satisfaction problems / Algorithmes paramétrés pour des problèmes de satisfaction de contraintes presque traitablesCarbonnel, Clément 07 December 2016 (has links)
Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses. / The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.
|
Page generated in 0.16 seconds