Relevant bibliographies by topics / Max-SAT Problem

Academic literature on the topic 'Max-SAT Problem'

Author: Grafiati
Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Max-SAT Problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Max-SAT Problem"

1

Chieu, H. L., and W. S. Lee. "Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem." Journal of Artificial Intelligence Research 36 (October 30, 2009): 229–66. http://dx.doi.org/10.1613/jair.2808.

Full text
Abstract:
The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances.
APA, Harvard, Vancouver, ISO, and other styles
2

Abu Doush, Iyad, Amal Lutfi Quran, Mohammed Azmi Al-Betar, and Mohammed A. Awadallah. "MAX-SAT Problem using Hybrid Harmony Search Algorithm." Journal of Intelligent Systems 27, no. 4 (October 25, 2018): 643–58. http://dx.doi.org/10.1515/jisys-2016-0129.

Full text
Abstract:
Abstract Maximum Satisfiability problem is an optimization variant of the Satisfiability problem (SAT) denoted as MAX-SAT. The aim of this problem is to find Boolean variable assignment that maximizes the number of satisfied clauses in the Boolean formula. In case the number of variables per clause is equal or greater than three, then this problem is considered NP-complete. Hence, many researchers have developed techniques to deal with MAX-SAT. In this paper, we investigate the impact of different hybrid versions of binary harmony search (HS) algorithm on solving MAX 3-SAT problem. Therefore, we propose two novel hybrid binary HS algorithms. The first hybridizes Flip heuristic with HS, and the second uses Tabu search combined with Flip heuristic. Furthermore, a distinguished feature of our proposed approaches is using an objective function that is updated dynamically based on the stepwise adaptation of weights (SAW) mechanism to evaluate the MAX-SAT solution using the proposed hybrid versions. The performance of the proposed approaches is evaluated over standard MAX-SAT benchmarks, and the results are compared with six evolutionary algorithms and three stochastic local search algorithms. The obtained results are competitive and show that the proposed novel approaches are effective.
APA, Harvard, Vancouver, ISO, and other styles
3

Py, Matthieu, Mohamed Sami Cherif, and Djamal Habet. "Proofs and Certificates for Max-SAT." Journal of Artificial Intelligence Research 75 (December 8, 2022): 1373–400. http://dx.doi.org/10.1613/jair.1.13811.

Full text
Abstract:
Current Max-SAT solvers are able to efficiently compute the optimal value of an input instance but they do not provide any certificate of its validity. 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, we prove that 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. Both tools are evaluated on the unweighted and weighted benchmark instances of the 2020 Max-SAT Evaluation.
APA, Harvard, Vancouver, ISO, and other styles
4

Li, C. M., F. Manya, and J. Planes. "New Inference Rules for Max-SAT." Journal of Artificial Intelligence Research 30 (October 23, 2007): 321–59. http://dx.doi.org/10.1613/jair.2215.

Full text
Abstract:
Exact Max-SAT solvers, compared with SAT solvers, apply little inference at each node of the proof tree. Commonly used SAT inference rules like unit propagation produce a simplified formula that preserves satisfiability but, unfortunately, solving the Max-SAT problem for the simplified formula is not equivalent to solving it for the original formula. In this paper, we define a number of original inference rules that, besides being applied efficiently, transform Max-SAT instances into equivalent Max-SAT instances which are easier to solve. The soundness of the rules, that can be seen as refinements of unit resolution adapted to Max-SAT, are proved in a novel and simple way via an integer programming transformation. With the aim of finding out how powerful the inference rules are in practice, we have developed a new Max-SAT solver, called MaxSatz, which incorporates those rules, and performed an experimental investigation. The results provide empirical evidence that MaxSatz is very competitive, at least, on random Max-2SAT, random Max-3SAT, Max-Cut, and Graph 3-coloring instances, as well as on the benchmarks from the Max-SAT Evaluation 2006.
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

Wang, Xiaofeng, and Jiulei Jiang. "Warning Propagation Algorithm for the MAX-3-SAT Problem." IEEE Transactions on Emerging Topics in Computing 7, no. 4 (October 1, 2019): 578–84. http://dx.doi.org/10.1109/tetc.2017.2736504.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
8

Alasow, Abdirahman, Peter Jin, and Marek Perkowski. "Quantum Algorithm for Variant Maximum Satisfiability." Entropy 24, no. 11 (November 5, 2022): 1615. http://dx.doi.org/10.3390/e24111615.

Full text
Abstract:
In this paper, we proposed a novel quantum algorithm for the maximum satisfiability problem. Satisfiability (SAT) is to find the set of assignment values of input variables for the given Boolean function that evaluates this function as TRUE or prove that such satisfying values do not exist. For a POS SAT problem, we proposed a novel quantum algorithm for the maximum satisfiability (MAX-SAT), which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with information on how far the given Boolean function is from the SAT satisfaction. We used Grover’s algorithm with a new block called quantum counter in the oracle circuit. The proposed circuit can be adapted for various forms of satisfiability expressions and several satisfiability-like problems. Using the quantum counter and mirrors for SAT terms reduces the need for ancilla qubits and realizes a large Toffoli gate that is then not needed. Our circuit reduces the number of ancilla qubits for the terms T of the Boolean function from T of ancilla qubits to ≈⌈log2⁡T⌉+1. We analyzed and compared the quantum cost of the traditional oracle design with our design which gives a low quantum cost.
APA, Harvard, Vancouver, ISO, and other styles
9

Gallo, G., C. Gentile, D. Pretolani, and G. Rago. "Max Horn SAT and the minimum cut problem in directed hypergraphs." Mathematical Programming 80, no. 2 (January 1998): 213–37. http://dx.doi.org/10.1007/bf01581727.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Zhu, Wenxing, and Yuanhui Yan. "Solving the weighted MAX-SAT problem using the dynamic convexized method." Optimization Letters 8, no. 1 (November 8, 2012): 359–74. http://dx.doi.org/10.1007/s11590-012-0583-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Max-SAT Problem"

1

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.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
2

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
7

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
8

Αραβαντινού, Άννα. "Πιθανοτική ικανοποιησιμότητα : πολυπλοκότητα και υπολογιστικές προσεγγίσεις." Thesis, 2015. http://hdl.handle.net/10889/8631.

Full text
Abstract:
Στην εργασία αυτή ασχοληθήκαμε με το πρόβλημα της Πιθανοτικής Ικανοποιησιμότητας. Παρουσιάσαμε ανάλυση της πολυπλοκότητας του προβλήματος και το επιλύσαμε με την βοήθεια του λογισμικού πακέτου CPLEX. Περιγράψαμε προσεγγιστικούς αλγόριθμους για το πρόβλημα της Μέγιστης Ικανοποιησιμότητας που χρησιμοποιείται στην διαδικασία της Column Generation. Τέλος, πριγράψαμε το αντίστροφο πρόβλημα των συχνών στοιχειοσυνόλων και την σχέση του με το πρόβλημα της Μέγιστης Ικανοποιησιμότητας.
This thesis is about the problem of probabilistic satisfiability. We describe its computational complexity, we solve the problem using CPLEX, we discribe some approximations on Maximum Satisfiability. Finally, we describe the connection between the problem of Probabilistic Satisfiability and the inverse frequent itemset mining.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Max-SAT Problem"

1

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Max-SAT Problem"

1

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, 519–36. Providence, Rhode Island: American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ochoa, Gabriela, Francisco Chicano, and Marco Tomassini. "Global Landscape Structure and the Random MAX-SAT Phase Transition." In Parallel Problem Solving from Nature – PPSN XVI, 125–38. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-58115-2_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Pankratov, Denis, and Allan Borodin. "On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem." In Theory and Applications of Satisfiability Testing – SAT 2010, 223–36. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14186-7_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Sadeg, Souhila, Habiba Drias, Ouassim Ait El Hara, and Ania Kaci. "ABSO: Advanced Bee Swarm Optimization Metaheuristic and Application to Weighted MAX-SAT Problem." In Brain Informatics, 226–37. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-23605-1_24.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Benatchba, Karima, Lotfi Admane, and Mouloud Koudil. "Using Bees to Solve a Data-Mining Problem Expressed as a Max-Sat One." In Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, 212–20. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11499305_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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, 575–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/3-540-62095-8_62.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Max-SAT Problem"

1

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/787.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Khadilkar, Harshad. "Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT." In 2022 Eighth Indian Control Conference (ICC). IEEE, 2022. http://dx.doi.org/10.1109/icc56513.2022.10093678.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Grimaldi, Andrea, Eleonora Raimondo, Anna Giordano, Kerem Y. Çamsarı, and Giovanni Finocchio. "A Comparison of Energy Minimization Algorithms for Solving Max-Sat Problem with Probabilistic Ising Machines." In 2023 IEEE 23rd International Conference on Nanotechnology (NANO). IEEE, 2023. http://dx.doi.org/10.1109/nano58406.2023.10231311.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Tönshoff, Jan, Berke Kisin, Jakob Lindner, and Martin Grohe. "One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/476.

Full text
Abstract:
We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search heuristic for any Constraint Satisfaction Problem (CSP). Our architecture can be trained unsupervised with policy gradient descent to generate problem specific heuristics for any CSP in a purely data driven manner. The approach is based on a novel graph representation for CSPs that is both generic and compact and enables us to process every possible CSP instance with one GNN, regardless of constraint arity, relations or domain size. Unlike previous RL-based methods, we operate on a global search action space and allow our GNN to modify any number of variables in every step of the stochastic search. This enables our method to properly leverage the inherent parallelism of GNNs. We perform a thorough empirical evaluation where we learn heuristics for well known and important CSPs, both decision and optimisation problems, from random data, including graph coloring, MAXCUT, and MAX-k-SAT, and the general RB model. Our approach significantly outperforms prior end-2-end approaches for neural combinatorial optimization. It can compete with conventional heuristics and solvers on test instances that are several orders of magnitude larger and structurally more complex than those seen during training.
APA, Harvard, Vancouver, ISO, and other styles
8

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Max-SAT Problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography