document

Optimal decision tree using dynamic programming: for the algorithm selection problem

Zeng, Henwei (author)

Several algorithms can often be used to solve a complex problem, such as the SAT problem or the graph coloring problem. Those algorithms differ in terms of speed based on the size or other features of the problem. Some algorithms perform much faster on a small size while others perform noticeably better on a larger instance. The optimization...

bachelor thesis 2023

document

Robustness of optimal randomized decision trees with dynamic programming

Götz, Valentijn (author)

Decision tree learning is widely done heuristically, but advances in the field of optimal decision trees have made them a more prominent subject of research. However, current methods for optimal decision trees tend to overlook the metric of robustness. Our research wants to find out whether the robustness of optimal decision trees can be...

bachelor thesis 2023

document

Cost-sensitive optimal decision trees dealing with delays

Butzelaar, Sven (author)

Machine learning can be used to classify patients in a hospital. Here, the classifier has to minimize the cost of misclassifying the patient and minimize the costs of the tests. Unfortunately, obtaining features may be costly, e.g., taking blood tests or doing an x-ray scan. Furthermore, it is possible that acquiring those test results may take...

bachelor thesis 2023

document

Solving the Colored Multi-Agent Path Finding with Waypoints Problem using SAT

van Dijk, Jeroen (author)

The Multi-Agent Path Finding (MAPF) problem is the problem of planning paths for multiple agents without any collisions. There are also many variants such as the waypoint variant, where each agent also has a set of waypoints it must visit before reaching its goal. The colored variant, in which the agents are grouped into teams and each team has...

master thesis 2022

document

Enumeration of Minimal Separators with Special Properties

Nardi Dei Da Filicaia Dotti, Andrea (author)

In this paper we give a historical and theoretical background to minimal triangulation and its relation to minimal separators.<br/>We introduce a new type of minimal separators, the minimal meta separator, which its size is a lower bound for the treewidth problem, its fill-in is a lower bound for the minimum fill-in problem and can be used for...

master thesis 2022

document

SAT-based optimisation for the resource-constrained project scheduling problem with time-dependent resource capacities and requests

Pleunes, Jelle (author)

In this paper, a variant of the resource-constrained project scheduling problem is discussed. This variant introduces time-dependence for resource capacities and requests, making the problem a more realistic model for many practical applications such as production scheduling and medical research project planning. The main aim of this paper is to...

bachelor thesis 2022

document

Exploring Heuristic Methods for the Resource-Constrained Project Scheduling Problem with Logical Constraints

Schoenmaker, Melle (author)

This paper presents the use of a heuristic solution method to improve the process of creating a conjunctive normal form (CNF) encoding of and finding optimal solutions to instances of the resource-constrained project scheduling problem with logical constraints (RCPSP-Log).<br/><br/>The RCPSP is an optimisation problem consisting of a set of...

bachelor thesis 2022

document

Resource-constraint project scheduling with task preemption and setup times by Boolean satisfiability encoding and satisfiability (SAT) solver

Vermeulen, Jasper (author)

Scheduling has been subject to much research. The resource-constrained project scheduling problem (RCPSP) is no exception. With the multiple different variations and additions to the standard definition that are possible, many exact, heuristic and meta-heuristic approaches have been proposed. One of those variations is allowing tasks in the...

bachelor thesis 2022

document

Heuristic Augmentation of SAT Solvers for MRCPSP

Miguel Teixeira de Mendonça, João (author)

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an NP-hard scheduling problem that concerns activities with several execution modes connected by precedence relations. Precedence relations define a partial ordering in which activities must be processed. The execution mode of an activity defines its processing time and...

bachelor thesis 2022

document

Domain-specific heuristic augmentation of SAT solvers on prize-collecting job scheduling problem

Dashtevski, Filip (author)

We study the prize-collecting job scheduling problem with one common and multiple secondary resources, where the target is to collect the biggest score possible by constructing a feasible schedule with given constraints of jobs and resources. Many scheduling configurations, where a single asset can be used by all jobs separately and a set of...

bachelor thesis 2022

document

Towards Generic Solving, Generation, and Rating Methods for Strategy-Solvable Pen and Paper Puzzles

Dijcks, Isha (author)

Pen and paper puzzles are a fun pastime to test your logical reasoning skills, with Sudoku being the most popular of these puzzles.<br/>While the problem of solving these puzzles is usually in NP-Complete, generating them is more difficult, depending on the type of puzzle.<br/>When generating puzzles for humans, we have to keep in mind how they...

master thesis 2022

document

Cooperative multi-agent multi-target catching

Waij, Sander (author)

Multi-agent multi-target catching is the act of multiple agents trying to catch multiple moving targets. The exact algorithms created for such chases are generally targets that are actively trying to get as far as possible, while the agents try to prevent that. However, these algorithms can get much more efficient whenever targets also want to...

master thesis 2022

document

Incrementally encoding cardinality and pseudo-boolean constraints in SAT

Langerak, Jens (author)

Satisfiability solvers have been shown to be a powerful tool for solving constraint problems. These problems often contain pseudo-boolean and cardinality constraints. These constraints can either be encoded into SAT or handled by extending the solver with special propagators. Which method will perform better is often not known in advance. It has...

master thesis 2021

document

Reinforcement learning for order distribution in self-organizing logistics

de Vries, Yorick (author)

With the increasing global demand for logistics, supply chains have grown a lot in volume over the last decades. To be able to operate effectively within the capacity constraints of the carriers, proper collaboration and optimization of order allocation is required. Van Berkel Logistics facilitates the transport of containers by trucks from sea...

master thesis 2021

document

Exact Machine Learning: Improving Space and Speed of MaxSAT Solvers for Correlation Clustering

Marchal, Maxim (author)

Clustering is an important unsupervised learning task, with many applications in machine learning, computer vision, formal program verification and finance. Heuristic approaches such as local search are an excellent strategy for estimating the optimal solution, but they run the danger of getting stuck in local optima. Furthermore, it is non...

master thesis 2021

document

Exploiting multi-core parallelism on optimal decision trees

Patandin, Ayush (author)

This paper presents a study that discusses how multi-threading can be used to improve the runtime performance of constructing optimal classification trees. Decision trees are popular for solving classification or regression problems in machine learning. Heuristic methods are used to build decision tree algorithms that produce models of high...

bachelor thesis 2021

document

Improving Existing Optimal Decision Trees Algorithmsby Redefining Their Binarisation Strategy

Wolska, Ola (author)

Optimal decision trees are not easily improvable in terms of accuracy. However, improving the pre-processing of underlying dataset can be the answer to creating more accurate decision trees. In this paper, multiple methods of binarising datasets are considered and the resulting decision trees compared. The binarisation is divided into two stages...

bachelor thesis 2021

document

Devising Multivariate Splits for Optimal Decision Trees

Mălan, Abel (author)

Decision trees are often desirable for classification/regression tasks thanks to their human-friendly models. Unfortunately, the construction of decision trees is a hard problem which usually implies having to rely on imperfect heuristic methods. Advancements in algorithmics and hardware processing power have rendered globally optimal trees...

bachelor thesis 2021

document

Developing efficient heuristic approaches to cluster editing, inspired by other clustering problems

Zoumis, Angelos (author)

Cluster editing attempts to find the minimum number of edge additions and removals on an undirected graph, that will transform the graph to one consisting of only disconnected cliques. In this paper, we propose three heuristic approaches to this problem, based on algorithms used to solve different clustering problems. The algorithms were based...

bachelor thesis 2021

document

Solving Cluster Editing Using MaxSAT-based Techniques

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