Searched for: subject%3A%22satisfiability%22
(1 - 16 of 16)
document
Marijnissen, Imko (author)
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...
master thesis 2023
document
Zielinski, Sebastian (author), Gabor, Thomas (author), Nüßlein, Jonas (author), Linnhoff-Popien, Claudia (author), Stein, Jonas (author), Feld, S. (author)
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...
conference paper 2023
document
Zielinski, Sebastian (author), Nüßlein, Jonas (author), Stein, Jonas (author), Gabor, Thomas (author), Linnhoff-Popien, Claudia (author), Feld, S. (author)
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....
journal article 2023
document
Veldkamp, Susan (author)
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...
master thesis 2022
document
Barneveld, Anne (author)
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...
master thesis 2022
document
Nüßlein, Jonas (author), Gabor, Thomas (author), Linnhoff-Popien, Claudia (author), Feld, S. (author)
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...
conference paper 2022
document
Marijnissen, Imko (author)
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...
bachelor thesis 2021
document
Klein Schiphorst, Jonathan (author)
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...
master thesis 2021
document
Viseu Cardoso, Rodrigo (author), Sobhani, A. (author), Meijers, E.J. (author)
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...
journal article 2021
document
van Driel, R.A. (author)
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...
master thesis 2020
document
Döcker, Janosch (author), van Iersel, L.J.J. (author), Kelk, Steven (author), Linz, Simone (author)
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...
journal article 2019
document
Mijnders, S. (author)
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...
master thesis 2012
document
Van der Tak, P. (author)
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....
master thesis 2012
document
Lotgering, T.F. (author)
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...
master thesis 2012
document
Schaafsma, B.J. (author)
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...
master thesis 2009
document
Heule, M.J.H. (author)
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...
doctoral thesis 2008
Searched for: subject%3A%22satisfiability%22
(1 - 16 of 16)