- document
-
Tudor, Iarina (author)This paper provides a novel method of solving the resource-constrained project scheduling problem (RCPSP) with logical constraints (RCPSP-log) using satisfiability (SAT) solving and integrating variable selection heuristics. The extension provides two additional precedences: OR constraints and bidirectional (BI) relations, making it possible to...bachelor thesis 2023
- document
-
Lenssen, Tijs (author)The Variable State Independent Decaying Sum (VSIDS) heuristic is one of the most effective variable selection heuristics for Conflict-Driven Clause-Learning (CDCL) SAT solvers. It works by keeping track of the activity values for each variable, which get bumped and decayed based on conflict analysis. These activity values usually start out...bachelor thesis 2023
- document
-
Huisman, Tim (author)Survival analysis revolves around studying and predicting the time it takes for a particular event to occur. In clinical trials on terminal illnesses, this is usually the time from the diagnosis of a patient until their death. Estimating the odds of survival of a new patient can be done by analyzing survival data from past patients in similar...bachelor thesis 2023
- document
-
Bentert, Matthias (author), Schestag, J. (author), Sommer, Frank (author)We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set...conference paper 2023
- document
-
Garvardt, Jaroslav (author), Renken, Malte (author), Schestag, J. (author), Weller, Mathias (author)We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex ν is in a prescribed list λ(ν). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem...conference paper 2023
- document
-
Kooij, Robert (author), Achterberg, M.A. (author)The effective graph resistance, also known as the Kirchhoff index, is metric that is used to quantify the robustness of a network. We show that the optimisation problem of minimizing the effective graph resistance of a graph by adding a fixed number of links, is NP-hard.journal article 2023
- document
-
van Iersel, L.J.J. (author), Jones, M.E.L. (author), Julien, E.A.T. (author), Murakami, Yukihiro (author)Phylogenetic networks are used to represent the evolutionary history of species. Recently, the new class of orchard networks was introduced, which were later shown to be interpretable as trees with additional horizontal arcs. This makes the network class ideal for capturing evolutionary histories that involve horizontal gene transfers. Here,...conference paper 2023
- document
-
Bai, X. (author), Fielbaum, Andres (author), Kronmüller, M. (author), Knödler, L. (author), Alonso-Mora, J. (author)This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a...journal article 2023
- document
-
Kordyl, Agata (author)The Multi-Level Bin Packing problem is a generalisation of the widely-known NP-hard Bin Packing problem. This work aims to investigate approaching this problem, as well as a version including Class Constraints, through integer programming. By modelling the problems in two ways: standard, and with a network flow approach. The studying of the...bachelor thesis 2022
- document
-
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
-
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
-
Bulteau, Laurent (author), Jones, M.E.L. (author), Niedermeier, Rolf (author), Tantau, Till (author)In the NP-hard Longest Common Subsequence problem (LCS), given a set of strings, the task is to find a string that can be obtained from every input string using as few deletions as possible. LCS is one of the most fundamental string problems with numerous applications in various areas, having gained a lot of attention in the algorithms and...conference paper 2022
- document
-
Simon, Alexandre (author)Interval graphs play an important role in graph theory and have intensively been studied for over sixty years due to their wide range of applications and because most NP-hard problems on general graphs become solvable in linear time on interval graphs. However, the class of interval graphs is restricted and does not even contain a cycle of...master thesis 2021
- document
-
Rhebergen, Damiaan (author)The Cluster Editing problem asks to transform a graph into a union of disjoint cliques in the minimum number of edge additions and deletions. The Cluster Deletion problem has the same goal, but allows edge deletions only. Recently, a connection between Cluster Editing on diamond-free graphs and Cluster Deletion was established. In this paper we...bachelor thesis 2021
- document
-
Keetch, Blaine (author), van Gennip, Y. (author)The Max-Cut problem is a well known combinatorial optimization problem. In this paper we describe a fast approximation method. Given a graph G, we want to find a cut whose size is maximal among all possible cuts. A cut is a partition of the vertex set of G into two disjoint subsets. For an unweighted graph, the size of the cut is the number...journal article 2019
- 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
-
Kelk, Steven (author), Pardi, Fabio (author), Scornavacca, Celine (author), van Iersel, L.J.J. (author)Phylogenetic networks are often constructed by merging multiple conflicting phylogenetic signals into a directed acyclic graph. It is interesting to explore whether a network constructed in this way induces biologically-relevant phylogenetic signals that were not present in the input. Here we show that, given a multiple alignment A for a set...journal article 2018
- document
-
Van Alphen, M.N. (author)In logistics, minimizing the resource expenses can be done by minimizing the total number of hours that each truck driver has to work. This sum of working hours is referred to as the total schedule duration for all truck drivers. Minimizing this total schedule duration is the main goal in the optimization problem that we consider. The considered...master thesis 2016
- document
-
Doole, M.M. (author)This thesis investigates the concept of fuel-reduction via formation flight of long-haul commercial aircraft on a network-wide scale, particularly addressing the issue of combinatorial complexity in global formation routing and allocation. A multi-stage formation flight planning (MS-FFLIP) tool is proposed as a computationally tractable approach...master thesis 2016
- document
-
Huber, K.T. (author), Van Iersel, L.J.J. (author), Moulton, V. (author), Scornavacca, C. (author), Wu, T. (author)Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets...journal article 2015