Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 17 of 17 for “"MAX-SAT"”.
-
Optimizing Vehicle Usage Using CSP, SAT and MAX-SAT
… from AI: Constraint Programing (CP), Boolean Satisfiability (SAT), and Maximum Satisfiability (MAX-SAT). We then use solvers to find optimal solutions to this problem. We show which of these solvers is more efficient when finding optimal solutions. For this purpose, we create a test suite of …
-
Structure in combinatorial optimization and its effect on heuristic performance
… or greater rate with the instance size. The maximum boolean satisfiability (MAX-SAT) is one such problem that has many important theoretical and practical applications. Due to the exponential growth of the search space, sufficiently large instances of MAX-SAT are intractable for complete …
-
In pursuit of industrial like MAXSAT with reduced MAX-3SAT random generation
In the modern landscape of MAXSAT, there are two broad classifications of problems: Random MAX-3SAT and Industrial SAT. Random MAX-3SAT problems by randomly sampling variables with a uniform probability and randomly assigning signs to the variable, one clause at a time. Industrial MAX-SAT consists …
-
Exploring Constraint Satisfiability Techniques in Formal Verification
… widespread demands for efficient Propositional Satisfiability (SAT) solvers and its derivatives in Electronic Design Automation applications, methods to boost the performance of the SAT solver are highly desired. This dissertation aims to enhance the performance of SAT and related SAT solving …
-
A General Pluggable Type Inference Framework and its use for Data-flow Analysis
… type constraint by encoding the constraint as a Max-SAT problem and in the LogiQL language. The system takes advantage of existing Max-SAT solvers and LogicBlox to solve the corresponding forms, and gets the concrete pluggable type qualifiers for program expressions. Type Constraint Solver …
-
Kvantově inspirované optimalizační algoritmy
… pravidel pro celulární automaty a problém MAX-SAT. Poslední část obsahuje modifikace simulovaného kvantového žíhání, srovnání se základní variantou a s běžnými optimalizačními algoritmy následované vyhodnocením tohoto srovnání.
-
Clustering solutions: a novel approach to solving NP-complete problems
… thesis, we introduce a novel approach to solving MAX-SAT problems. This algorithm clusters good solutions, and restarts the search from the closest feasible configuration to the centroid of each cluster. We call this method Clustered-Landscape Guided Hopping (CLGH). In addition, where clustering …
-
Synthesis of reactive controllers for reconfigurable networked systems
… for designing a reactive controller that satisfies those specifications. The first approach encodes the specifications in linear temporal logic (LTL) while the second one treats the specifications as clauses in a maximum satisfiability (Max-SAT) setting. To benchmark the schemes, a scaled …
-
Parameter optimisation for search heuristics via a barrier tree Markov model
… cost, over binary perception, spin-glass and Max-SAT problems. The predictions of the model are found to be consistently over-optimistic; we discuss reasons for this and suggest some possible refinements to the model.</p> <p>A population-based variant of simulated annealing is briefly …
-
Analysis of the fitness landscape for the class of combinatorial optimisation problems
… for a group of well known combinatorial optimisation problems is studied in this research and the similarities and the differences between their landscapes are pointed out. In this research we target the analysis of the fitness landscape for MAX-SAT, Graph-Colouring, Travelling Salesman and …
-
Quantum Search Algorithms for Constraint Satisfaction and Optimization Problems Using Grover's Search and Quantum Walk Algorithms with Advanced Oracle Design
… variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building …
-
A step toward constant time local search for optimizing pseudo Boolean functions
… class of hard optimization problems, such as MAX-SAT and MAX-CUT. Since these problems are NP-Hard, researchers and practitioners rely on incomplete solvers, such as Stochastic Local Search (SLS), for large problems. Best-Improvement Local Search (BILS) is a common form of SLS, which always …
-
Adversarial Attacks and Defences For Image Retrieval Systems
… objective function to enable efficient optimisation. In addition, we design a dimension-wise surrogate Hamming distance function to reduce perturbations further. Experiments show that our framework achieves the same attack performance with much less perturbation cost than the existing works. …
-
Application of Logic Synthesis Toward the Inference and Control of Gene Regulatory Networks
… In the first technique, we present Boolean Satisfiability (SAT) based approaches to infer the predictor (logical support) of each gene that regulates melanoma, using gene expression data from patients who are suffering from the disease. From the output of such a tool, biologists can …
-
Constraint Solving for Diagnosing Concurrency Bugs
… problems. By leveraging the power of constraint satisfiability (SAT) solvers and a bounded model checker, we perform a semantic analysis of the sequential computation as well as the thread interactions. The analysis is ideally suited for handling software with small to medium code size but …
-
Dataless Neural Networks for Boolean Satisfiability and Network Optimization
… space subject to constraints, with the goal of satisfying an objective function. They arise in operations research, scheduling, resource allocation, circuit design, and many other fields. Many problems in combinatorial optimization (including satisfiability and network design) are NP-hard. …