Towards the unification of the Core-Guided and Hitting Set Maximum Satisfiability approaches

Core-guided solvers and Implicit Hitting Set (IHS) solvers have become ubiquitous within the field of Maximum Satisfiability (MaxSAT). While both types of solvers iteratively increase the solution cost until a satisfiable solution is found, the manner in which this relaxation is performed leads to the belief that these techniques are wholly...

Pattern QUBOs: Algorithmic Construction of 3SAT-to-QUBO Transformations

One way of solving 3sat instances on a quantum computer is to transform the 3sat instances into instances of Quadratic Unconstrained Binary Optimizations (QUBOs), which can be used as an input for the QAOA algorithm on quantum gate systems or as an input for quantum annealers. This mapping is performed by a 3sat-to-QUBO transformation....

Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study

To solve 3sat instances on quantum annealers they need to be transformed to an instance of Quadratic Unconstrained Binary Optimization (QUBO). When there are multiple transformations available, the question arises whether different transformations lead to differences in the obtained solution quality. Thus, in this paper we conduct an...

A MaxSAT Approach to Solving Frequency Conflicts within Cyclic Train Timetables

ILP-based solvers that intake a line planning, an infrastructure and a set of constraints and then output a cyclic train timetable have been researched extensively in the world of trains. However, these types of solvers are not able to automatically output a timetable when the problem gets overconstrained and no feasible solution exists.<br/><br...

Cyclists Station Choice: Investigating railway station choice for cyclists including perceived social safety and comfort factors

Investigating station choice is important for possibly solving various capacity issues such as bicycle parking. Current literature is often restricted to dissatisfier parameters such as travel time, presence of transfer and travel costs. In order to fully understand station choice, this research includes factors regarding perceived safety and...

Algorithmic QUBO formulations for k-SAT and hamiltonian cycles

Quadratic Unconstrained Binary Optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for k-SAT and Hamiltonian Cycles...

Solving Cluster Editing Using MaxSAT-based Techniques

Clustering is a well-studied problem and several algorithms have been developed to find these clusterings under certain constraints. This work will show the applicability of propositional logic (MaxSAT) based approaches to a specific version of correlation clustering called cluster editing. This is the problem of finding the minimum number of...

Formal Synthesis of Optimal Neural Network Controllers

Stability, safety and optimality are often sought-after properties in the field of controller synthesis. In the last century, linear control theory has matured to a level where scalable algorithms are widely available that are able to synthesize controllers with stability and optimality guarantee. However, the synthesis of safe controllers...

The cities we need: Towards an urbanism guided by human needs satisfaction

This article proposes moving beyond the tyranny of economic imperatives towards a human needs-based framework to assess cities and envision their development. Existing calls for such a transition lack a foundation able to capture the various dimensions of human life in cities, which can be provided by the concept of human needs. We ask whether...

Unsatisfiable core learning for Chuffed: Improving the performance of Chuffed, a Lazy-Clause-Generation solver, by using machine learning to predict unsatisfiable cores

Solving propositional satisfiability (SAT) and constraint programming (CP) instances has been a fundamental part of a wide range of modern applications. For this reason a lot of research went into improving the efficiency of modern SAT and CP solvers. Recently much of this research has gone into exploring the possibilities of integrating machine...

Deciding the existence of a cherry-picking sequence is hard on two trees

Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and...

Minimally Unsatisfiable Subformulae

Minimal unsatis?ability is a topic in the ?eld of satis?ability (SAT). Minimally unsatis?able subformulae (MUSes) are minimal subsets of an unsatis?able formula that are unsatis?able. They can therefore be seen as causes of unsatis?ability. With recent improvements in SAT solving, extracting MUSes has also become faster. Lately increasingly more...

Concurrent Cube-and-Conquer

Recent work introduced the cube-and-conquer technique to solve hard SAT instances. It combines the two dominant SAT solving techniques: lookahead and conflict-driven clause learning (CDCL). First, it partitions the search space into so called cubes using a lookahead solver. Each cube is tackled by a conflict-driven clause learning solver....

SDP-based Max-2-Sat Decomposition

The Max-Sat problem has been intensively studied during the past few decades. Semi-definite programming based approximation algorithms provide good approximation ratios and polynomial runtime solutions to this problem. Unfortunately the high degree of their polynomial runtime prevents their application to problems with a large number of...

MiniMerge: Symmetry-Free Learning in Combinatorial Problems

We present a new method to break symmetry in graph coloring problems, which can be applied in many classes of combinatorial problems. While most alternative techniques add symmetry breaking predicates in a pre-processing step, we developed a learning scheme that translates each encountered conflict into one conflict clause which covers...

SmArT solving: Tools and techniques for satisfiability solvers

The satisfiability problem (Sat) lies at the core of the complexity theory. This is a decision problem: Not the solution itself, but whether or not a solution exists given a specified set of requirements is the central question. Over the years, the satisfiability problem has taken center stage as a means of effective representation to tackle...