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 20 of 22 for “"MaxSAT"”.
-
Solving MAXSAT by Decoupling Optimization and Satisfaction
… modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in …
-
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 …
-
Formal specifications for cyber-physical systems
… explores solving for the maximum satisfiability (MaxSAT) of MLTL specifications. Given a set of specifications, MaxSAT solves for the subset of the largest cardinality that is simultaneously satisfiable. MaxSAT is important for feature prioritization and cost analysis while designing systems that …
-
Reusing Work and Avoiding Redundant Work in Propositional Logic Solvers
… in the performance of mutliple complete MaxSAT solvers. The next main technique addresses the redundancy that occurs every time a SAT solver backtracks and continues its redescent down the search tree, where it will reconstruct most of the same assignment trail again. In order to address …
-
Effectively Encoding SAT and Other Intractable Problems into Ising Models for Quantum Computing
… optimization problem. Problems such as SAT and MaxSAT need to be encoded to make use of quantum annealers. Encoding SAT and MaxSAT problems while respecting the constraints and limitations of current hardware is a difficult task. This thesis presents an approach to encoding SAT and MaxSAT …
-
Optimal Planning with Learned Neural Network Transition Models
… and Weighted Partial Maximum Satisfiability (WP-MaxSAT), respectively. For the MILP model, we investigate different preprocessing methodologies based on reachability, network sparsification and potential functions to speed up the experimental runtime performance of the underlying MILP solver. In …
-
Railway Timetable Optimization
… for the Maximum Satisfiability Problem (MaxSAT). In the literature, it has been proposed to encode different NP-complete problems that occur in railway timetabling in MaxSAT. In numerical experiments, we prove that our algorithms are competitive to state-of-the-art MaxSAT solvers. …
-
Exploits in Concurrency for Boolean Satisfiability
… on generalizations of Satisfiability such as MaxSAT, and Satisfiability Modulo Theories (SMT). Much of the advancement in SAT solver performance has been in the realm of improved sequential solvers with advanced conflict resolution, learning mechanisms, and sophisticated heuristics. There have …
-
Mining Attributed DTE Policies
… mining is then implemented by a reduction to MaxSAT. We devised an efficient MaxSAT encoding known as the separator-based encoding. Using both real-world and synthetic datasets, we demonstrated empirically that our approach offers a robust generalization performance across datasets of various …
-
Certifying Correctness for Combinatorial Algorithms : by Using Pseudo-Boolean Reasoning
… graph problems and maximum satisfiability(MaxSAT), for which efficient proof logging is out of reach forstate-of-the-art techniques.This work develops a new proof system building on the cutting planesproof system and operating on pseudo-Boolean constraints (0-1 linearinequalities). We …
-
Integrating Probabilistic Reasoning with Constraint Satisfaction
… optimization–-as represented here by the SAT and MaxSAT problems. Further, for MaxSAT we present an equivalent transformation” process that normalizes the weights in constraint optimization problems, in order to encourage prunings of the search tree during branch-and-bound search. To control such …
-
Domain-Based Policies: Policy Mining and Active Learning Frameworks
… We further develop Maximum Satisfiability (MaxSAT) encodings for policy reconstruction. Second, we address scalability and noise. In the clean setting, we recast DBPM as graph coloring and build a GPU accelerated pipeline that achieves substantial speedups over MaxSAT baselines in our …
-
Pseudo-Boolean Constraint Encodings for Conjunctive Normal Form and their Applications
… is also the foundation of the presented weighted MaxSAT solver optimax, the PBO solver pbsolver and the WBO, PBO and weighted MaxSAT solver npSolver.
-
Satisfiability and Optimization in Periodic Traffic Flow Problems
… usage of several techniques like SAT solving and MaxSAT to calculate and optimize the corresponding instances will be presented accordingly. Computational results for real-world scenarios suggest the practical impact and give promising perspectives for further scientific research.
-
Securing access control using machine learning and formal methods
… which utilizes Graph Neural Networks and MaxSAT to automatically fix privilege escalations in cloud access control misconfigurations. Evaluation on synthetic and real-world benchmarks demonstrates that all three techniques show promising effectiveness and efficiency compared to existing …
-
Effective qubit mapping, routing and scheduling for trapped-ion quantum computers
… evaluates MALT, a comprehensive extension of a MaxSAT based QMR technique by Molavi et. al. MALT generates efficient swap insertion and tape movement schedule for shuttling based architectures, beating the SOTA heuristic for all configurations and benchmarks. The thesis also addresses the issues …
-
Probabilistic Techniques For Constraint Satisfaction Problems
… counting (#SAT), and maximum satisfiability (MaxSAT) problems.
-
Solving Hybrid Boolean Constraints by Fourier Expansions and Continuous Optimization
… of a new line of research on Boolean SAT and MaxSAT.
-
Discovering and harnessing structures in solving application satisfiability instances
… to outperform CCLS, winners of several recent MAXSAT competitions. The other structural property we study is subproblem constrainedness. We observe that, on some application SAT instance classes, the original problem can be partitioned into several subproblems, where each subproblems is highly …
-
Understanding and Improving SAT Solvers via Proof Complexity and Reinforcement Learning
… The resulting SDCL solver, enhanced with MaxSAT techniques and conflict analysis, outperforms existing solvers on combinatorial benchmarks, particularly demonstrating superior efficacy on Mutilated Chess Board (MCB) problems.
Page 1 of 2