Acceder

Bibliografías temáticas / Max-SAT Problem / Artículos de revistas

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Max-SAT Problem.

Artículos de revistas sobre el tema "Max-SAT Problem"

Autor: Grafiati

Publicado: 25 de mayo de 2024

Última modificación: 31 de julio de 2025

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 50 mejores artículos de revistas para su investigación sobre el tema "Max-SAT Problem".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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,

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!