Bibliographies thématiques / Problème Max-SAT

Sommaire

Articles de revues
Thèses
Livres
Chapitres de livres
Actes de conférences

Littérature scientifique sur le sujet « Problème Max-SAT »

Auteur : Grafiati

Publié le 4 juin 2021

Mis à jour le 25 mai 2024

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les listes thématiques d’articles de revues, de livres, de thèses, de rapports de conférences et d’autres sources académiques sur le sujet « Problème Max-SAT ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Articles de revues sur le sujet "Problème Max-SAT"

Escoffier, Bruno, and Vangelis Th Paschos. "Differential approximation of min sat, max sat and related problems." European Journal of Operational Research 181, no. 2 (2007): 620–33. http://dx.doi.org/10.1016/j.ejor.2005.04.057.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Bouhmala, Noureddine. "A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems." Scientific World Journal 2014 (2014): 1–11. http://dx.doi.org/10.1155/2014/798323.

Texte intégral

Résumé :

The simplicity of the maximum satisfiability problem (MAX-SAT) combined with its applicability in many areas of artificial intelligence and computing science made it one of the fundamental optimization problems. This NP-complete problem refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weights of satisfied clauses) in a Boolean formula. The Walksat algorithm is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. Most local search algorithms including Walksat rely on the 1-flip neighborhood structure. This paper introduces a variable neighborhood walksat-based algorithm. The neighborhood structure can be combined easily using any local search algorithm. Its effectiveness is compared with existing algorithms using 1-flip neighborhood structure and solvers such as CCLS and Optimax from the eighth MAX-SAT evaluation.

Styles APA, Harvard, Vancouver, ISO, etc.

Argelich, Josep, and Felip Manyà. "Exact Max-SAT solvers for over-constrained problems." Journal of Heuristics 12, no. 4-5 (2006): 375–92. http://dx.doi.org/10.1007/s10732-006-7234-9.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Boughaci, Dalila, Belaïd Benhamou, and Habiba Drias. "Scatter Search and Genetic Algorithms for MAX-SAT Problems." Journal of Mathematical Modelling and Algorithms 7, no. 2 (2008): 101–24. http://dx.doi.org/10.1007/s10852-008-9077-x.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Bertoni, Alberto, Marco Carpentieri, Paola Campadelli, and Giuliano Grossi. "A Genetic Model: Analysis and Application to MAXSAT." Evolutionary Computation 8, no. 3 (2000): 291–309. http://dx.doi.org/10.1162/106365600750078790.

Texte intégral

Résumé :

In this paper, a genetic model based on the operations of recombination and mutation is studied and applied to combinatorial optimization problems. Results are: The equations of the deterministic dynamics in the thermodynamic limit (infinite populations) are derived and, for a sufficiently small mutation rate, the attractors are characterized; A general approximation algorithm for combinatorial optimization problems is designed. The algorithm is applied to the Max Ek-Sat problem, and the quality of the solution is analyzed. It is proved to be optimal for k≥3 with respect to the worst case analysis; for Max E3-Sat the average case performances are experimentally compared with other optimization techniques.

Styles APA, Harvard, Vancouver, ISO, etc.

Kumar, Mohit, Samuel Kolb, Stefano Teso, and Luc De Raedt. "Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (2020): 4493–500. http://dx.doi.org/10.1609/aaai.v34i04.5877.

Texte intégral

Résumé :

Combinatorial optimization problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with a preference function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism. We provide learnability results within the realizable and agnostic settings, as well as hassle, an implementation based on syntax-guided synthesis and showcase its promise on recovering synthetic and benchmark instances from examples.

Styles APA, Harvard, Vancouver, ISO, etc.

Pipatsrisawat, Knot, Akop Palyan, Mark Chavira, Arthur Choi, and Adnan Darwiche. "Solving Weighted Max-SAT Problems in a Reduced Search Space: A Performance Analysis1." Journal on Satisfiability, Boolean Modeling and Computation 4, no. 2-4 (2008): 191–217. http://dx.doi.org/10.3233/sat190044.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Kochenberger, Gary, Fred Glover, Bahram Alidaee, and Karen Lewis. "Using the unconstrained quadratic program to model and solve Max 2-SAT problems." International Journal of Operational Research 1, no. 1/2 (2005): 89. http://dx.doi.org/10.1504/ijor.2005.007435.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Resende, Mauricio G. C., Leonidas S. Pitsoulis, and Panos M. Pardalos. "Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP." Discrete Applied Mathematics 100, no. 1-2 (2000): 95–113. http://dx.doi.org/10.1016/s0166-218x(99)00171-7.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

BONGIOVANNI, GIANCARLO, PIERLUIGI CRESCENZI, and SERGIO DE AGOSTINO. "MAX SAT AND MIN SET COVER APPROXIMATION ALGORITHMS ARE $\mathcal P$-COMPLETE." Parallel Processing Letters 05, no. 02 (1995): 293–98. http://dx.doi.org/10.1142/s0129626495000278.

Texte intégral

Résumé :

We prove that the sequential approximation algorithms for the problems [Formula: see text] and [Formula: see text] proposed in [9] are [Formula: see text]-hard with respect to the logarithmic space reducibility. As a corollary, these two algorithms cannot be implemented efficiently in parallel unless [Formula: see text].

Styles APA, Harvard, Vancouver, ISO, etc.

Plus de sources

Thèses sur le sujet "Problème Max-SAT"

Py, Matthieu. "Inférence et certificats pour le problème de satisfiabilité maximum." Electronic Thesis or Diss., Aix-Marseille, 2021. http://www.theses.fr/2021AIXM0631.

Texte intégral

Résumé :

Dans cette thèse, on s'intéresse au problème de satisfiabilité maximum (Max-SAT), qui consiste, étant donnée une formule propositionnelle sous forme normale conjonctive, à trouver une interprétation des variables de la formule permettant de satisfaire le plus de clauses possible. Le système de preuve le plus utilisé dans Max-SAT est basé sur la règle d'inférence par max-résolution qui est l'adaptation pour Max-SAT de la règle de résolution utilisée pour le problème SAT. La règle de résolution déduit une nouvelle clause à partir de deux clauses, ce qui permet de certifier qu'une formule est insatisfiable en déduisant de nouvelles clauses jusqu'à en déduire une contradiction, représentée par la clause vide (on parle de réfutation par résolution). L'adaptation des réfutations par résolution en réfutations valides pour Max-SAT (appelées max-réfutations) sans en augmenter considérablement la taille est un problème ouvert depuis l'introduction de la max-résolution. On propose ici deux méthodes pour adapter n'importe quelle réfutation par résolution en max-réfutation. Une autre contribution est la construction de certificats qui permettent de démontrer l'optimalité d'une solution pour le problème Max-SAT, générés en utilisant les max-réfutations calculées à partir des réfutations par résolution. Enfin, on s'intéresse à comment inférer, à partir d'une formule initiale, une information donnée (clause ou formule) par des règles d'inférence qui préservent l'équivalence Max-SAT. On propose alors un nouveau système de preuve ainsi qu'un algorithme permettant de construire n'importe quelle inférence de clauses ou de formules, ou de certifier qu'une telle inférence ne peut exister In this thesis, we are interested in the maximum satisfiability problem (Max-SAT), which consists,given a Boolean formula in conjunctive normal form, in finding an assignment of the variables of the formula which allows to satisfy as many clauses as possible. The most widely used Max-SAT proof system is based on the Max-SAT resolution inference rule which is the adaptation for Max-SAT of the resolution rule used for the SAT problem. The resolution rule deduces a new clause from two opposing clauses, enabling to certify that a formula is unsatisfiable by gradually deducing new clauses until deducing a contradiction, represented in the form of an empty clause. The adaptation of such proofs, referred to as resolution refutations, for Max-SAT without considerably increasing its size is an open problem since the introduction of Max-SAT resolution.We propose in this thesis two methods to adapt any resolution resfutation into a valid refutation for Max-SAT, referred to as max-refutation. Another contribution is the construction of certificates to demonstrate the optimality of a solution for the Max-SAT problem. To generate such certificates, we use the max-refutations that we are now able to generate from the resolution refutations. Finally, we are interested in the problem which consists, given an initial formula and a given information (clause or formula), of inferring this information by Max-SAT-equivalence-preserving inference rules. As the max-resolution is incomplete for the inference in Max-SAT, we propose a new proof system as well as an algorithm allowing to infer, if possible, a given clause or formula

Styles APA, Harvard, Vancouver, ISO, etc.

Abramé, André. "Max-résolution et apprentissage pour la résolution du problème de satisfiabilité maximum." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4330/document.

Texte intégral

Résumé :

Cette thèse porte sur la résolution du problème d'optimisation Maximum Satisfiability (Max-SAT). Nous y étudions en particulier les mécanismes liés à la détection et à la transformation des sous-ensembles inconsistants par la règle de la max-résolution. Dans le contexte des solveurs de type séparation et évaluation, nous présentons plusieurs contributions liées au calcul de la borne inférieure. Cela va du schéma d'application de la propagation unitaire utilisé pour détecter les sous-ensembles inconsistants à l'extension des critères d'apprentissage et à l'évaluation de l'impact des transformations par max-résolution sur l'efficacité des solveurs. Nos contributions ont permis l'élaboration d'un nouvel outil de résolution compétitif avec les meilleurs solveurs de l'état de l'art. Elles permettent également de mieux comprendre le fonctionnement des méthodes de type séparation et évaluation et apportent des éléments théoriques pouvant expliquer l'efficacité et les limites des solveurs existants. Cela ouvre de nouvelles perspectives d'amélioration, en particulier sur l'augmentation de l'apprentissage et la prise en compte de la structure interne des instances. Nous présentons également un exemple d'utilisation de la règle de la max-résolution dans un algorithme de recherche local This PhD thesis is about solving the Maximum Satisfiability (Max-SAT) problem. We study the mechanisms related to the detection and transformations of the inconsistent subsets by the max-resolution rule. In the context of the branch and bound (BnB) algorithms, we present several contributions related to the lower bound computation. They range from the study of the unit propagation scheme used to detect inconsistent subsets to the extension of the learning criteria and to the evaluation of the impact of the max-resolution transformations on the BnB solvers efficiency. Thanks to our contributions, we have implemented a new solver which is competitive with the state of art ones. We give insights allowing a better understanding of the behavior of BnB solvers as well as theoretical elements which contribute to explain the efficiency of these solvers and their limits. It opens new development perspectives on the learning mechanisms used by BnB solvers which may lead to a better consideration of the instances structural properties. We also present an example of integration of the max-resolution inference rule in a local search algorithm

Styles APA, Harvard, Vancouver, ISO, etc.

Belaïdouni, Mériéma. "Métaheuristiques et paysages de recherche." Angers, 2001. http://www.theses.fr/2001ANGE0022.

Texte intégral

Résumé :

Les métaheuristiques sont une classe de méthodes qui fournissent des solutions de bonne qualité en temps raisonnable à des problèmes combinatoires réputés difficiles. Il existe de nombreux travaux d'application de ces méthodes mais très peu d'études s'intéressent à leur aspect fondamental. Ainsi la dynamique et le comportement des métaheuristiques restent méconnus. Cette thèse est dédiée à l'étude de quelques questions fondamentales sur les métaheuristiques. Nous avons adopté une méthodologie en trois axes : 1) l'étude des propriétés et mesures des problèmes combinatoires, 2) l'étude des comportements des métaheuristiques, 3) la mise en relation des mesures des problèmes et des comportements de métaheuristiques. Pour valider cette approche nous l'avons appliquée à deux problèmes NP-complets : MAX-CSP et SAT. Nous avons développé pour le premier axe un état de l'art qui réunit un grand nombre de mesures existantes, puis nous avons classé ces mesures. Nous avons ensuite appliqué et analysé les mesures densité d'état (DOS), distance dans un niveau (DDN), distance entre niveaux (DEN), autocorrélation et densité des coûts du processus (DCP). Concernant le deuxième axe nous avons développé la notion de performance qui fait partie des comportements d'une métaheuristique et nous avons proposé un nouveau critère d'évaluation de la performance basé sur la mesure DCP. Enfin, nous avons dans le troisième axe mis en évidence des relations entre comportements et mesures en analysant les conséquences sur les métaheuristiques, des mesures que nous avons étudiées. Ces mises en relation nous permettent de prévoir ou d'expliquer le comportement et la dynamique des métaheuristiques Metaheuristics are a class of methods which are able to provide solutions of good quality in a reasonnable amount of time for difficult combinatorial problems. There exist a large number of applications of these methods but only few studies concern their fondamental aspects. This thesis is devoted to study some fondamental issues of metaheuristics. Three tightly related axis are explored : 1)the study of problems properties and measures, 2)the study of dynamics of metaheuristics, 3)the establishment of the relations between measures of problems and dynamics of metaheuristics. To validate this approach we have apllied it to two NP-complete problems : MAX-CSP and SAT

Styles APA, Harvard, Vancouver, ISO, etc.

Ouzia, Hacène. "Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications." Paris 6, 2008. http://www.theses.fr/2008PA066349.

Texte intégral

Résumé :

Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d’abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d’une relaxation L&P pour qu’elle coïncide avec celle d’une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s’obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d’utiliser des relaxations L&P partielles.

Styles APA, Harvard, Vancouver, ISO, etc.

André, Pascal. "Aspects probabilistes du probleme de la satisfaction d'une formule booleenne, etude des problemes sat, number-sat et max-sat." Paris 6, 1993. http://www.theses.fr/1993PA066681.

Texte intégral

Résumé :

Le probleme sat (existence d'une solution d'un systeme sat) est un probleme np-complet. Le probleme max-sat (nombre maximum de clauses satisfaites d'un systeme sat), bien qu'a priori plus difficile, est egalement un probleme np-complet. Le probleme number-sat (nombre de solutions d'un systeme sat) est plus complexe et appartient a la classe des problemes number-p-complet. Il n'existe donc pas, aujourd'hui, d'algorithme deterministe polynomial capable de resoudre l'un ou l'autre de ces trois problemes. Pourtant, a propos du probleme number-sat, on montre que l'on peut definir des classes de systemes sat pour lesquelles il est possible de calculer, polynomialement par rapport a la taille de ces systemes, l'esperance, ou n'importe quel autre moment, du nombre de solutions. On montre egalement, a propos du probleme max-sat, que l'on peut calculer, pour n'importe quel systeme sat, toujours polynomialement par rapport a la taille du systeme, l'esperance, ou n'importe quel autre moment, du nombre de clauses satisfaites. En revanche, en ce qui concerne le probleme sat, la complexite du calcul de la probabilite d'existence d'une solution d'une classe de systemes sat est toujours un probleme ouvert

Styles APA, Harvard, Vancouver, ISO, etc.

Lardeux, Frédéric. "Approches hybrides pour les problèmes de satisfiabilité (SAT et MAX-SAT)." Angers, 2005. http://www.theses.fr/2005ANGE0024.

Texte intégral

Résumé :

Cette thèse est centrée sur la résolution des problèmes de satisfiabilité SAT et MAX-SAT. Les contributions apportées sont de trois types. Tout d'abord nous avons développé l'algorithme mémétique GASAT pour les problèmes SAT et MAX-SAT hybridant un algorithme tabou et un algorithme génétique. Des outils spécifiques aux problèmes de satisfiabilité y ont été intégrés tels que des mécanismes d'intensification, de diversification et un nouvel opérateur de croisement. Ensuite, nous avons proposé un nouveau cadre de résolution permettant aux méthodes exactes et aux méthodes approchées de manipuler la même représentation de l'espace de recherche. Pour cela, nous avons ajouté une troisième valeur de vérité "indéterminé". Les résultats obtenus par les algorithmes hybrides trivalués montrent l'intérêt de ce cadre de résolution. Enfin, nous nous sommes penchés sur les heuristiques de branchement des algorithmes de Branch and Bound pour le problème MAX-SAT. L'étude que nous présentons montre que ces heuristiques réagissent très différemment en fonction des paramètres initiaux, de la structure de l'instance étudiée et des mécanismes d'amélioration du Branch and Bound. Elle permet d'envisager la création de nouvelles heuristiques spécifiquement dédiées au problème MAX-SAT This thesis deals with the resolution of the satisfiability problems SAT and MAX-SAT. Our contributions are in three types. First, we have developed the memetic algorithm GASAT for the SAT and MAX-SAT problems which hybridies a tabu algorithm and a genetic algorithm. Some specific tools for the satisfiability problems have been included in it such as intensification mechanisms, diversification mechanisms and a new crossover operator. Next, we have proposed a new resolution framework which permits the exact and the approached methods to handle the same representation of the search space. To do this, we have added a third truth value ``undetermined''. The results obtained by the tri-valued hybrid algorithms show the utility of this resolution framework. Finally, we are interested in the branching heuristics for the Branch and Bound algorithms in the MAX-SAT context. Our study shows that these heuristics react in different ways in function of the initial parameters, the structure of the studied instances and the improved mechanisms for Branch and Bound. The findings of this study may lead to the creation of new heuristics specifically dedicated to the MAX-SAT problem

Styles APA, Harvard, Vancouver, ISO, etc.

MORALES, HUERTA MARTHA GUADALUPE 786078, and HUERTA MARTHA GUADALUPE MORALES. "Aproximación de soluciones del problema MAX-SAT usando cómputo cuántico adiabático." Tesis de maestría, Universidad Autónoma del Estado de México, 2018. http://hdl.handle.net/20.500.11799/95499.

Texte intégral

Résumé :

Actualmente, se han propuesto tecnologías cuánticas basadas en el algoritmo de temple cuántico y cómputo cuántico adiabático con aplicaciones a problemas de optimización combinatorios. Diversos estudios teóricos y experimentales se han enfocado en determinar las ventajas y desventajas de resolver clases específicas de problemas tales como detección de fallas en redes de potencia, plegado de proteínas, satisfacción de restricciones, entre otros. En esta tesis se propone una formulación cuántica del problema de máxima satisfactibilidad booleana usando el algoritmo de temple cuántico y cómputo cuántico adiabático. Nuestra formulación consiste en la construcción de una función booleana cuadrática cuya optimización corresponde a la solución del problema de estudio. También, se proponen tres estrategias de mapeo directas para instancias del problema de máxima satisfactibilidad booleana sobre la topología de hardware cuántico de la computadora D-Wave. Para validar nuestra propuesta, realizamos simulaciones computacionales del modelo cuántico para aproximar soluciones del problema de estudio, y las comparamos con resultados obtenidos usando algoritmos clásicos. Los resultados de las simulaciones muestran que el problema de máxima satisfactibilidad booleana puede ser tratado por medios cuánticos con las tecnologías cuánticas actuales. Sin embargo, se tienen que llevar a cabo investigaciones futuras para determinar si el algoritmo de temple cuántico y el cómputo cuántico adiabático, para el problema de estudio, tienen ventajas en términos de complejidad cuando se comparan con los mejores algoritmos en el estado del arte.

Styles APA, Harvard, Vancouver, ISO, etc.

Boughaci, Dalila. "Recherche locale et méthodes évolutives pour les problèmes MAX-SAT et PDG." Aix-Marseille 1, 2008. http://www.theses.fr/2008AIX11064.

Texte intégral

Résumé :

Dans cette thèse, deux problèmes réputés NP-difficiles sont étudiés, à savoir : le problème de satisfiabilité maximale MAX-SAT et le problème de la détermination du gagnant dans les enchères combinatoires PDG. Notre but principal est de contribuer à la résolution de ces deux problèmes par des méthodes évolutives et de recherche locale. Nous proposons, tout d’abord, une nouvelle stratégie de sélection qui se base sur la diversité et la qualité pour choisir une collection d’individus qui vont participer à la phase de reproduction et donner une descendance. Ensuite, nous utilisons un opérateur de combinaison spécifique au problème à étudier pour générer de nouveaux enfants qui sont améliorés par une recherche locale stochastique (SLS). Dans le but de tester et de prouver l’efficacité de nos approches, une étude comparative avec quelques algorithmes de l’état de l’art concernant MAX-SAT et PDG est faite dans la thèse.

Styles APA, Harvard, Vancouver, ISO, etc.

Teixeira, Giovany Frossard. "MULTIPLEX: um procedimento baseado em simulted annealing aplicado ao problema Max-Sat ponderado." Universidade Federal do Espírito Santo, 2006. http://repositorio.ufes.br/handle/10/6354.

Texte intégral

Résumé :

Made available in DSpace on 2016-12-23T14:33:34Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 412800 bytes, checksum: 479ec97937646fdcffeadd81d19f1b7a (MD5) Previous issue date: 2006-06-01 Computar a solução ótima para uma unidade de problema MAX-SAT Ponderado (weighted maximum satisfiability) é difícil mesmo se cada cláusula contiver apenas dois literais. Neste trabalho, será descrita a implementação de uma nova heurística aplicada a instâncias de problema do tipo MAX-SAT Ponderado, mas perfeitamente extensível a outros problemas. Para comparação, serão geradas soluções para uma quantidade significativa de problemas e seus resultados serão comparados com os de outras heurísticas já desenvolvidas para esse tipo de problema, dentre elas as heurísticas consideradas "estado da arte", ou seja, heurísticas que têm obtido os melhores resultados no universo das heurísticas existentes.

Styles APA, Harvard, Vancouver, ISO, etc.

Kolar, Michal. "Statistical Physics and Message Passing Algorithms. Two Case Studies: MAX-K-SAT Problem and Protein Flexibility." Doctoral thesis, SISSA, 2006. http://hdl.handle.net/20.500.11767/4659.

Texte intégral

Résumé :

In the last decades the tl1eory of spin glasses has been developed within the framework of statistical physics. The obtained results showed to be novel not only from the physical point of vie\l\'1 but they have brought also new mathematical techniques and algorithmic approaches. Indeed, the problem of finding ground state of a spin glass is (in general) NP-complete. The methods that were found brought new ideas to the field of Combinatorial Optimization, and on the other side, the similar methods of Combinatorial Optimization, were applied in physical systems. As it happened with the Monte Carlo sampling and the Simulated Annealing, also the novel Cavity Method lead to algorithms that are open to wide use in various fields of research The Cavity Method shows to be equivalent to Bethe Approximation in its most symmetric version, and the derived algorithm is equivalent to the Belief Propagation, an inference method used widely for example in the field of Pattern Recognition. The Cavity Method in a less symmetric situation, when one has to consider correctly the clustering of the configuration space, lead to a novel messagepassing algorithm-the Survey Propagation. The class of Message-Passing algorithms, among which both the Belief Propagation and the Survey Propagation belong, has found its application as Inference Algorithms in many engineering fields. Among others let us :mention the Low-Density Parity-Check Codes, that are widely used as ErrorCorrecting Codes for communication over noisy cha1mels. In the first part of this work we have compared efficiency of the Survey Propagation Algorithm and of standard heuristic algorithms in the case of the random-MAX-K-SAT problem. The results showed that the algorithms perform similarly in the regions where the clustering of configuration space does not appeai~ but that the Survey Propagation finds much better solutions to the optimization problem in the critical region where one has to consider existence of many ergodic components explicitly. The second part of the thesis targets the problem of protein structure and flexibility. In many proteins the mobility of certain regions and rigidity of other regions of their structure is crucial for their function or interaction with other cellular elements. Our simple model tries to point out the flexible regions from the knowledge of native 3D-structure of the protein. The problem is mapped to a spin glass model which is successfully solved by the Believe Propagation algorithm.

Styles APA, Harvard, Vancouver, ISO, etc.

Livres sur le sujet "Problème Max-SAT"

Monahan, Chris. My max score SAT math 1 & 2 subject test: Maximize your score in less time. Sourcebooks, 2011.

Trouver le texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Chapitres de livres sur le sujet "Problème Max-SAT"

Joy, Steve, John Mitchell, and Brian Borchers. "A branch and cut algorithm for MAX-SAT and weighted MAX-SAT." In Satisfiability Problem: Theory and Applications. American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/13.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Escoffier, Bruno, and Vangelis Th Paschos. "Differential Approximation of min sat, max sat and Related Problems." In Computational Science and Its Applications – ICCSA 2005. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11424925_22.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Pardalos, P. M., L. Pitsoulis, and M. G. C. Resende. "A parallel GRASP for MAX-SAT problems." In Applied Parallel Computing Industrial Computation and Optimization. Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-62095-8_62.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Fu, Zhaohui, and Sharad Malik. "On Solving the Partial MAX-SAT Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11814948_25.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Pinto, Pedro C., Thomas A. Runkler, and João M. C. Sousa. "Insect Swarm Algorithms for Dynamic MAX-SAT Problems." In Metaheuristics for Dynamic Optimization. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-30665-5_15.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Resende, Mauricio, Leonidas Pitsoulis, and Panos Pardalos. "Approximate solution of weighted MAX-SAT problems using GRASP." In Satisfiability Problem: Theory and Applications. American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/11.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Battiti, R., and M. Protasi. "Solving MAX-SAT with nonoblivious functions and history-based heuristics." In Satisfiability Problem: Theory and Applications. American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/19.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Drias, Habiba, and Mohamed Khabzaoui. "Scatter Search with Random Walk Strategy for SAT and MAX-W-SAT Problems." In Engineering of Intelligent Systems. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45517-5_5.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Choi, Arthur, Trevor Standley, and Adnan Darwiche. "Approximating Weighted Max-SAT Problems by Compensating for Relaxations." In Principles and Practice of Constraint Programming - CP 2009. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-04244-7_19.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Boughaci, Dalila, and Habiba Drias. "Efficient and Experimental Meta-heuristics for MAX-SAT Problems." In Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11427186_43.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Actes de conférences sur le sujet "Problème Max-SAT"

Py, Matthieu, Mohamed Sami Cherif, and Djamal Habet. "Proofs and Certificates for Max-SAT (Extended Abstract)." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/787.

Texte intégral

Résumé :

In this paper, we present a tool, called MS-Builder, which generates certificates for the Max-SAT problem in the particular form of a sequence of equivalence-preserving transformations. To generate a certificate, MS-Builder iteratively calls a SAT oracle to get a SAT resolution refutation which is handled and adapted into a sound refutation for Max-SAT. In particular, the size of the computed Max-SAT refutation is linear with respect to the size of the initial refutation if it is semi-read-once, tree-like regular, tree-like or semi-tree-like. Additionally, we propose an extendable tool, called MS-Checker, able to verify the validity of any Max-SAT certificate using Max-SAT inference rules.

Styles APA, Harvard, Vancouver, ISO, etc.

Sadeg, Souhila, Habiba Drias, Hafid Aid, and Samir Mazouz. "DNA based algorithms for solving both MAX-SAT and MAX-W-SAT problems." In 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). IEEE, 2010. http://dx.doi.org/10.1109/bicta.2010.5645331.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Ali, H. M., David Mitchell, and Daniel C. Lee. "MAX-SAT problem using evolutionary algorithms." In 2014 IEEE Symposium On Swarm Intelligence (SIS). IEEE, 2014. http://dx.doi.org/10.1109/sis.2014.7011783.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Molnar, Botond, and Maria Ercsey-Ravasz. "Analog dynamics for solving max-SAT problems." In 2014 14th International Workshop on Cellular Nanoscale Networks and their Applications (CNNA). IEEE, 2014. http://dx.doi.org/10.1109/cnna.2014.6888597.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Pinto, Pedro C., Thomas A. Runkler, and Joao M. C. Sousa. "An Ant Algorithm for Static and Dynamic Max-Sat Problems." In 2006 1st Bio-Inspired Models of Network, Information and Computing Systems. IEEE, 2006. http://dx.doi.org/10.1109/bimnics.2006.361793.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Pinto, Pedro C., Thomas A. Runkler, and João M. C. Sousa. "An ant algorithm for static and dynamic MAX-SAT problems." In the 1st international conference. ACM Press, 2006. http://dx.doi.org/10.1145/1315843.1315856.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Ali, Hafiz Munsub, and Daniel C. Lee. "Solving the MAX-SAT problem by binary enhanced fireworks algorithm." In 2016 Sixth International Conference on Innovative Computing Technology (INTECH). IEEE, 2016. http://dx.doi.org/10.1109/intech.2016.7845071.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Ali, Hafiz Munsub, Waleed Ejaz, May Al Taei, and Farkhund Iqbal. "Solving MAX-SAT Problem by Binary Biogeograph-based Optimization Algorithm." In 2019 IEEE 10th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON). IEEE, 2019. http://dx.doi.org/10.1109/iemcon.2019.8936281.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Handa, Hisashi. "Robust Solutions by using Evolutionary Computations on Dynamic Max-Sat Problems." In 2006 SICE-ICASE International Joint Conference. IEEE, 2006. http://dx.doi.org/10.1109/sice.2006.315479.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Boughaci, Dalila, and Habiba Drias. "Solving weighted Max-Sat optimization problems using a Taboo Scatter Search metaheuristic." In the 2004 ACM symposium. ACM Press, 2004. http://dx.doi.org/10.1145/967900.967910.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!