Log in

Relevant bibliographies by topics / Max-SAT Problem / Journal articles

To see the other types of publications on this topic, follow the link: Max-SAT Problem.

Journal articles on the topic 'Max-SAT Problem'

Author: Grafiati

Published: 25 May 2024

Last updated: 31 July 2025

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

Select a source type:

Consult the top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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 ov

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 (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,

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 resp

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 refinem

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 s

APA, Harvard, Vancouver, ISO, and other styles

6

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.

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 anal

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Das, Rhiddhi Prasad, Anuruddha Paul, Junali Jasmine Jena, Bibhuti Bhusan Dash, Utpal Chandra De, and Mahendra Kumar Gourisaria. "Hybrid Binary SGO-GA for solving MAX-SAT problem." Procedia Computer Science 252 (2025): 944–53. https://doi.org/10.1016/j.procs.2025.01.055.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Kuhlmann, Isabelle, Anna Gessler, Vivien Laszlo, and Matthias Thimm. "Comparison of SAT-Based and ASP-Based Algorithms for Inconsistency Measurement." Journal of Artificial Intelligence Research 82 (February 4, 2025): 563–685. https://doi.org/10.1613/jair.1.16888.

Full text

Abstract:

We present algorithms based on satisfiability problem (SAT) solving, as well as answer set programming (ASP), for solving the problem of determining inconsistency degrees in propositional knowledge bases. We consider six different inconsistency measures whose respective decision problems lie on the first level of the polynomial hierarchy. Namely, these are the contension, forgetting-based, hitting set, max-distance, sum-distance, and hit-distance inconsistency measures. In an extensive experimental analysis, we compare the SAT-based and ASP-based approaches with each other, as well as with a s

APA, Harvard, Vancouver, ISO, and other styles

10

Alasow, Abdirahman, Peter Jin, and Marek Perkowski. "Quantum Algorithm for Variant Maximum Satisfiability." Entropy 24, no. 11 (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

APA, Harvard, Vancouver, ISO, and other styles

11

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 (1998): 213–37. http://dx.doi.org/10.1007/bf01581727.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Adelshin, A. V., and A. K. Kuchin. "ANALYSIS OF L-STRUCTURE OF POLYHEDRON IN THE PARTIAL MAX SAT PROBLEM." Prikladnaya diskretnaya matematika, no. 38 (December 1, 2017): 110–18. http://dx.doi.org/10.17223/20710410/38/9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

WOCJAN, PAWEL, and THOMAS BETH. "THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP." International Journal of Quantum Information 01, no. 03 (2003): 349–57. http://dx.doi.org/10.1142/s021974990300022x.

Full text

Abstract:

We show that the NP-complete problems max cut and independent set can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. The 5-local Hamiltonian problem was the first problem to be shown to be complete for the quantum complexity class QMA — the quantum analog of NP. Subsequently, it was shown that 3-locality is already sufficient for QMA-completeness. It is still not known whether the 2-local Hamiltonian problem is QMA-complete. Therefore it is interesting to determine what problems can be reduced to the 2-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulate

APA, Harvard, Vancouver, ISO, and other styles

15

Omelchenko, Oleksii, and Andrei A. Bulatov. "Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (2022): 3804–12. http://dx.doi.org/10.1609/aaai.v36i4.20295.

Full text

Abstract:

MAX k-SAT is one of the archetypal NP-hard problems. Its variation called random MAX k-SAT problem was introduced in order to understand how hard it is to solve instances of the problem on average. The most common model to sample random instances is the uniform model, which has received a large amount of attention. However, the uniform model often fails to capture important structural properties we observe in the real-world instances. To address these limitations, a more general (in a certain sense) model has been proposed, the configuration model, which is able to produce instances with an ar

APA, Harvard, Vancouver, ISO, and other styles

16

Ma, Shaohan, and Dongmin Liang. "A polynomial-time algorithm for reducing the number of variables in MAX SAT problem." Science in China Series E: Technological Sciences 40, no. 3 (1997): 301–11. http://dx.doi.org/10.1007/bf02916605.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Hastings, M. B. "A Short Path Quantum Algorithm for Exact Optimization." Quantum 2 (July 26, 2018): 78. http://dx.doi.org/10.22331/q-2018-07-26-78.

Full text

Abstract:

We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree D; this problem is called weighted MAX-ED-LIN2. We require that the optimal solution be unique for odd D and doubly degenerate for even D; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still expo

APA, Harvard, Vancouver, ISO, and other styles

18

Sawaya, Nicolas PD, Daniel Marti-Dafcik, Yang Ho, et al. "HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware." Quantum 8 (December 11, 2024): 1559. https://doi.org/10.22331/q-2024-12-11-1559.

Full text

Abstract:

In order to characterize and benchmark computational hardware, software, and algorithms, it is essential to have many problem instances on-hand. This is no less true for quantum computation, where a large collection of real-world problem instances would allow for benchmarking studies that in turn help to improve both algorithms and hardware designs. To this end, here we present a large dataset of qubit-based quantum Hamiltonians. The dataset, called HamLib (for Hamiltonian Library), is freely available online and contains problem sizes ranging from 2 to 1000 qubits. HamLib includes problem ins

APA, Harvard, Vancouver, ISO, and other styles

19

Xu, Zhenxing, Kun He, and Chu-Min Li. "An iterative Path-Breaking approach with mutation and restart strategies for the MAX-SAT problem." Computers & Operations Research 104 (April 2019): 49–58. http://dx.doi.org/10.1016/j.cor.2018.12.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Palubeckis, Gintaras. "A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem." Applied Mathematics and Computation 215, no. 3 (2009): 1106–17. http://dx.doi.org/10.1016/j.amc.2009.06.043.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Dlask, Tomáš, and Tomáš Werner. "Using Constraint Propagation to Bound Linear Programs." Journal of Artificial Intelligence Research 80 (June 15, 2024): 665–718. http://dx.doi.org/10.1613/jair.1.15604.

Full text

Abstract:

We present an approach to compute bounds on the optimal value of linear programs based on constraint propagation. Given a feasible dual solution, we apply constraint propagation to the complementary slackness conditions and, if propagation succeeds to prove these conditions infeasible, the infeasibility certificate (in the sense of Farkas’ lemma) is reconstructed from the propagation history. This certificate is a dual-improving direction, which allows us to improve the bound. As constraint propagation need not always detect infeasibility of a linear inequality system, the method is not guaran

APA, Harvard, Vancouver, ISO, and other styles

22

Chicano, Francisco, Andrew M. Sutton, L. Darrell Whitley, and Enrique Alba. "Fitness Probability Distribution of Bit-Flip Mutation." Evolutionary Computation 23, no. 2 (2015): 217–48. http://dx.doi.org/10.1162/evco_a_00130.

Full text

Abstract:

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We

APA, Harvard, Vancouver, ISO, and other styles

23

Munawar, Asim, Mohamed Wahib, Masaharu Munetomo, and Kiyoshi Akama. "Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework." Genetic Programming and Evolvable Machines 10, no. 4 (2009): 391–415. http://dx.doi.org/10.1007/s10710-009-9091-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Grégoire, Éric, and Jean-Marie Lagniez. "RCL: An A. I. Tool for Computing Maximal Consensuses." International Journal on Artificial Intelligence Tools 25, no. 04 (2016): 1650026. http://dx.doi.org/10.1142/s0218213016500263.

Full text

Abstract:

RCL is an original Artificial Intelligence tool for computing maximal consensuses among conflicting agents in the Boolean logic framework. It extracts one maximal set of information that does not conflict with any of the agents, taking all possible deductions into account. This form of consensus can go far beyond what is actually shared by all agents. It might be endorsed by every agent since it does not conflict with any of them. Several types of preference criteria can be selected and iterated in order to orient the computation towards some preferred consensuses. From a computational point o

APA, Harvard, Vancouver, ISO, and other styles

25

Fielder, Catherine E., Yao-Yuan Mao, Jeffrey A. Newman, Andrew R. Zentner, and Timothy C. Licquia. "Predictably missing satellites: subhalo abundances in Milky Way-like haloes." Monthly Notices of the Royal Astronomical Society 486, no. 4 (2019): 4545–68. http://dx.doi.org/10.1093/mnras/stz1098.

Full text

Abstract:

ABSTRACT On small scales there have been a number of claims of discrepancies between the standard cold dark matter (CDM) model and observations. The ‘missing satellites problem’ infamously describes the overabundance of subhaloes from CDM simulations compared to the number of satellites observed in the Milky Way. A variety of solutions to this discrepancy have been proposed; however, the impact of the specific properties of the Milky Way halo relative to the typical halo of its mass has yet to be explored. Motivated by recent studies that identified ways in which the Milky Way is atypical, we

APA, Harvard, Vancouver, ISO, and other styles

26

DOVIER, AGOSTINO. "Preface." Theory and Practice of Logic Programming 17, no. 4 (2017): 359–64. http://dx.doi.org/10.1017/s1471068417000199.

Full text

Abstract:

Magic squares, chess-like problems, cryptarithmetic puzzles, and similar classes of problems have been extensively used to challenge human reasoning capabilities. Lo Shu magic square can be traced back to 650 B.C., the eight-queens problem was proposed in 1848 by the chess player Max Bazzel TWO × TWO = THREE puzzle appeared in Strand Magazine in 1924. These puzzles are nowadays widely used in constraint programming courses. The first programming language provided with constraint modelling primitives (Sketchpad) has been proposed by the Turing award winner Ivan Sutherland in his PhD thesis (196

APA, Harvard, Vancouver, ISO, and other styles

27

Sahai, Tuhin, Anurag Mishra, Jose Miguel Pasini, and Susmit Jha. "Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (2020): 1627–35. http://dx.doi.org/10.1609/aaai.v34i02.5524.

Full text

Abstract:

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even whe

APA, Harvard, Vancouver, ISO, and other styles

28

Alkasem, Haifa Hamad, and Mohamed El Bachir Menai. "A Stochastic Local Search Algorithm for the Partial Max-SAT Problem Based on Adaptive Tuning and Variable Depth Neighborhood Search." IEEE Access 9 (2021): 49806–43. http://dx.doi.org/10.1109/access.2021.3068824.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Francès, Guillem, Blai Bonet, and Hector Geffner. "Learning General Planning Policies from Small Examples Without Supervision." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 13 (2021): 11801–8. http://dx.doi.org/10.1609/aaai.v35i13.17402.

Full text

Abstract:

Generalized planning is concerned with the computation of general policies that solve multiple instances of a planning domain all at once. It has been recently shown that these policies can be computed in two steps: first, a suitable abstraction in the form of a qualitative numerical planning problem (QNP) is learned from sample plans, then the general policies are obtained from the learned QNP using a planner. In this work, we introduce an alternative approach for computing more expressive general policies which does not require sample plans or a QNP planner. The new formulation is very simpl

APA, Harvard, Vancouver, ISO, and other styles

30

Traversa, Fabio L., Pietro Cicotti, Forrest Sheldon, and Massimiliano Di Ventra. "Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems." Complexity 2018 (July 3, 2018): 1–13. http://dx.doi.org/10.1155/2018/7982851.

Full text

Abstract:

Optimization problems pervade essentially every scientific discipline and industry. A common form requires identifying a solution satisfying the maximum number among a set of many conflicting constraints. Often, these problems are particularly difficult to solve, requiring resources that grow exponentially with the size of the problem. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the c

APA, Harvard, Vancouver, ISO, and other styles

31

Petrović, Tijana, Danijela Tadić, Dragan Marinković, Goran Đurić, and Nikola Komatina. "Developing a New Approach for Assessing and Improving Business Excellence: Integrating Fuzzy Analytic Hierarchical Process and Constraint Programming Model." Symmetry 17, no. 4 (2025): 607. https://doi.org/10.3390/sym17040607.

Full text

Abstract:

This study introduces a novel two-stage model for assessing and enhancing business excellence based on the EFQM framework. The Fuzzy Analytic Hierarchy Process (FAHP) is used in the first stage to calculate the weight vectors of criteria and sub-criteria, incorporating uncertainty through triangular fuzzy numbers (TFNs). In the second stage, the OR-Tools CP-SAT solver is used to solve the selection and improvement of sub-criteria as a multidimensional knapsack problem with mixed min/max constraints. In this way, a new and enhanced model for evaluating business excellence is presented—one that

APA, Harvard, Vancouver, ISO, and other styles

32

Zhuo, Hankz Hankui, Qiang Yang, Rong Pan, and Lei Li. "Cross-Domain Action-Model Acquisition for Planning via Web Search." Proceedings of the International Conference on Automated Planning and Scheduling 21 (March 22, 2011): 298–305. http://dx.doi.org/10.1609/icaps.v21i1.13449.

Full text

Abstract:

Applying learning techniques to acquire action models is an area of intense research interest. Most previous works in this area have assumed that there is a significant amount of training data available in a planning domain of interest, which we call target domain, where action models are to be learned. However, it is often difficult to acquire sufficient training data to ensure that the learned action models are of high quality. In this paper, we develop a novel approach to learning action models with limited training data in the target domain by transferring knowledge from related auxiliary

APA, Harvard, Vancouver, ISO, and other styles

33

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Maciejewski, Filip B., Flavio Baccari, Zoltán Zimborás, and Michał Oszmaniec. "Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm." Quantum 5 (June 1, 2021): 464. http://dx.doi.org/10.22331/q-2021-06-01-464.

Full text

Abstract:

Measurement noise is one of the main sources of errors in currently available quantum devices based on superconducting qubits. At the same time, the complexity of its characterization and mitigation often exhibits exponential scaling with the system size. In this work, we introduce a correlated measurement noise model that can be efficiently described and characterized, and which admits effective noise-mitigation on the level of marginal probability distributions. Noise mitigation can be performed up to some error for which we derive upper bounds. Characterization of the model is done efficien

APA, Harvard, Vancouver, ISO, and other styles

36

Cade, Chris, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. "Quantifying Grover speed-ups beyond asymptotic analysis." Quantum 7 (October 10, 2023): 1133. http://dx.doi.org/10.22331/q-2023-10-10-1133.

Full text

Abstract:

Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation w

APA, Harvard, Vancouver, ISO, and other styles

37

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

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.

Full text

Abstract:

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 learnab

APA, Harvard, Vancouver, ISO, and other styles

39

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

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.

Full text

Abstract:

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].

APA, Harvard, Vancouver, ISO, and other styles

43

Layeb, Abdesslem, and Djamel-Eddine Saidouni. "A Hybrid Quantum Genetic Algorithm and Local Search based DPLL for Max 3-SAT Problems." Applied Mathematics & Information Sciences 8, no. 1 (2014): 77–87. http://dx.doi.org/10.12785/amis/080109.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Gregory, Peter, Derek Long, Maria Fox, and J. Christopher Beck. "Planning Modulo Theories: Extending the Planning Paradigm." Proceedings of the International Conference on Automated Planning and Scheduling 22 (May 14, 2012): 65–73. http://dx.doi.org/10.1609/icaps.v22i1.13505.

Full text

Abstract:

Considerable effort has been spent extending the scope of planning beyond propositional domains to include, for example, time and numbers. Each extension has been designed as a separate specific semantic enrichment of the underlying planning model, with its own syntax and customised integration into a planning algorithm. Inspired by work on SAT Modulo Theories (SMT) in the SAT community, we develop a modelling language and planner that treat arbitrary first order theories as parameters. We call the approach Planning Modulo Theories (PMT). We introduce a modular language to represent PMT proble

APA, Harvard, Vancouver, ISO, and other styles

45

Russell, Richard, and Sean Holden. "Handling Goal Utility Dependencies in a Satisfiability Framework." Proceedings of the International Conference on Automated Planning and Scheduling 20 (May 25, 2021): 145–52. http://dx.doi.org/10.1609/icaps.v20i1.13401.

Full text

Abstract:

Goal utility dependencies arise when the utility of achieving a goal depends on the other goals that are achieved with it. This complicates the planning procedure because achieving a new goal can potentially alter the utilities of all the other goals currently achieved. In this paper, we present an encoding procedure that enables general-purpose Max-SAT solvers to be used to solve planning problems with goal utility dependencies. We compare this approach to one using integer programming via an empirical evaluation using benchmark problems from past international planning competitions. Our resu

APA, Harvard, Vancouver, ISO, and other styles

46

Alidaee, Bahram, Gary Kochenberger, and Haibo Wang. "Theorems Supporting r-flip Search for Pseudo-Boolean Optimization." International Journal of Applied Metaheuristic Computing 1, no. 1 (2010): 93–109. http://dx.doi.org/10.4018/jamc.2010102605.

Full text

Abstract:

Modern metaheuristic methodologies rely on well defined neighborhood structures and efficient means for evaluating potential moves within these structures. Move mechanisms range in complexity from simple 1-flip procedures where binary variables are “flipped” one at a time, to more expensive, but more powerful, r-flip approaches where “r” variables are simultaneously flipped. These multi-exchange neighborhood search strategies have proven to be effective approaches for solving a variety of combinatorial optimization problems. In this paper, we present a series of theorems based on partial deriv

APA, Harvard, Vancouver, ISO, and other styles

47

Sinjorgo, Lennart, and Renata Sotirov. "On Solving MAX-SAT Using Sum of Squares." INFORMS Journal on Computing, November 7, 2023. http://dx.doi.org/10.1287/ijoc.2023.0036.

Full text

Abstract:

We consider semidefinite programming (SDP) approaches for solving the maximum satisfiability (MAX-SAT) problem and weighted partial MAX-SAT. It is widely known that SDP is well-suited to approximate (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiability problems by being competitive with some of the best solvers in the yearly MAX-SAT competition. Our solver combines sum of squares (SOS)–based SDP bounds and an efficient parser within a branch-and-bound scheme. On the theoretical side, we propose a family of semidefinite feasibility problems and show that a member of thi

APA, Harvard, Vancouver, ISO, and other styles

48

Fong, Robert Simon, Yanming Song, and Alexander Yosifov. "Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems." New Journal of Physics, January 3, 2025. https://doi.org/10.1088/1367-2630/ada572.

Full text

Abstract:

Abstract Boolean satisfiability (SAT) is a propositional logic problem of determining whether an assignment of variables satisfies a Boolean formula. Many combinatorial optimization problems can be formulated in Boolean SAT logic -- either as k-SAT decision problems or Max k-SAT optimization problems, with conflict-driven (CDCL) solvers being the most prominent. Despite their ability to handle large instances, CDCL-based solvers have fundamental scalability limitations. In light of this, we propose recently-developed quadratic unconstrained binary optimization (QUBO) solvers as an alternative

APA, Harvard, Vancouver, ISO, and other styles

49

Fremont, Daniel, Markus Rabe, and Sanjit Seshia. "Maximum Model Counting." Proceedings of the AAAI Conference on Artificial Intelligence 31, no. 1 (2017). http://dx.doi.org/10.1609/aaai.v31i1.11138.

Full text

Abstract:

We introduce the problem Max#SAT, an extension of model counting (#SAT). Given a formula over sets of variables X, Y, and Z, the Max#SAT problem is to maximize over the variables X the number of assignments to Y that can be extended to a solution with some assignment to Z. We demonstrate that Max#SAT has applications in many areas, showing how it can be used to solve problems in probabilistic inference (marginal MAP), planning, program synthesis, and quantitative information flow analysis. We also give an algorithm which by making only polynomially many calls to an NP oracle can approximate th

APA, Harvard, Vancouver, ISO, and other styles

50

Bannach, Max, Malte Skambath, and Till Tantau. "On the Parallel Parameterized Complexity of MaxSAT Variants." Journal of Artificial Intelligence Research 78 (November 19, 2023). http://dx.doi.org/10.1613/jair.1.14748.

Full text

Abstract:

In the maximum satisfiability problem (max-sat) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versions of max-sat and provide the first constant-time algorithms parameterized either by the solution size or by the allowed excess relative to some guarantee. For the dual parameterized version where the parameter is the number of clauses we are allowed to leave unsatisfied, we present the first parallel algorithm for max-2sat (known as almost-2sat).

APA, Harvard, Vancouver, ISO, and other styles

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!