Welcome!
Group seminars occur regularly on Fridays. There is also a Google calendar with the schedule.
Seminars of 2021
Hyperplane coverings with multiplicities
Speaker: Simona Boyadzhiyska (FU Berlin)
When and Where: Friday, 19/11/2021, at 15:30, Colloquiumzaal, VMB
Abstract:
A well-known result of Alon and Füredi states that \(n\) hyperplanes are needed to cover all nonzero points of \(\mathbb{F}_2^n\) while avoiding the origin. In this talk, we will generalize this result to the setting where the points of \(\mathbb{F}_2^n \setminus \{ \vec{0} \}\) must be covered at least \(k\) times, while the origin can be covered by at most \(k-1\) hyperplanes. Exploiting a connection to coding theory, and using combinatorial and probabilistic arguments, we will provide tight bounds in certain ranges of the parameters \(n\) and \(k\).
This is joint work with Anurag Bishnoi, Shagnik Das, and Tamás Mészáros.
Erdos-Ko-Rado Theorems
Speaker: Jozefien D'haeseleer (University of Gent)
When and Where: Friday, 12/11/2021, at 15:30, Snijderszaal, EWI
Abstract:
One of the classical problems in extremal set theory is to determine the size of the largest families of pairwise non-disjoint subsets in a given set. Erdos, Ko and Rado investigated this problem and classified the largest examples of these families. In the last decades, this problem, originated in set theory, was generalized to many other structures such as graphs and projective spaces. In this presentation I will give an overview of the known Erdos-Ko-Rado theorems in set theory, graph theory and projective geometry. In this last setting I will also give a classification result.
Finding fitting heuristics for the Road Network Upgrading Problem (a project for the World Bank)
Speaker: Britt van Veggel (TU Delft)
When and Where: Friday, 2/7/2021, at 14:00, Zoom, via link
Abstract:
In developing nations, important links in the infrastructure network are often dirt or gravel roads. These roads can be at a high risk of becoming inaccessible during rainy season. Due to this, many households may lose access to any healthcare facility. The UN Sustainability Development Goals aim to increase access to healthcare facilities within a 5km traveling distance for as many people as possible, as any travel distance above this threshold decreases survivability chances immensely. Therefore, for this thesis project, we try to find the links that can best be upgraded to be all-seasons accessible, such that as many households as possible are able to access a healthcare facility within 5km traveling distance, provided a certain budget. We apply a case study to the country of Timor-Leste.
So far, the flooding risks have been modelled, the households that lose accessibility due to these at-risk roads have been identified, and two MIP models have been implemented (in Gurobi) which can (often) solve the problem on a healthcare facility level (meaning, 1 healthcare facility, with all households and roads within a 5km birdseye view) . One model is inspired by the models of Magnanti & Wong, but is computationally very heavy as it optimizes over a very large set of variables. The other model (that is not really inspired upon any existing model) optimizes over a set of possible paths. So far, this model has been quite successful in cases with few roads, but it fails to solve the problem for areas with a large amount of infrastructure. The problem so far seems to be that there are no efficient methods to generate (relevant) paths.
For this seminar, I would like to discuss how to generate these paths more efficiently (by only generating k relevant ones per household, for example), how to tackle the problem on a regional or national level (some ideas exist, but the golden egg has not yet hatched), and whether there are any other possible models or adjustments to the current models possible.
Some problems and results on order types
Speaker: Yoshiharu Kohayakawa (University of Sao Paulo)
When and Where: Wednesday, 9/6/2021, at 14:00, Zoom, via link
Abstract:
A
A solver for clustered low-rank SDPs arising from multivariate polynomial matrix programs
Speaker: Nando Leijenhorst (TU Delft)
When and Where: Wednesday, 26/5/2021, at 15:00, Zoom, via link
Abstract:
It is common to formulate polynomial constraints as semidefinite program (SDP) constraints through coefficient matching: two polynomials are equal if and only if they have equal coefficients when expressed in the same basis. Another approach is to use sampling: polynomials in one variable of degree d are equal if and only if they evaluate to the same value on d+1 distinct points. This can be extended to multivariate polynomials. The advantage of this is that it leads to low rank constraint matrices, which can be exploited in an SDP solver.
In this talk, I will introduce a primal-dual interior point method specialized to this type of SDPs: clustered low-rank SDPs. We will see how polynomial constraints, and more generally polynomial matrix constraints, can be rewritten to clusters of SDP constraints with low rank constraint matrices.
We will shortly consider two problems to which the solver can be applied: bounding the maximum density of sphere packings and of spherical cap packings. The first problem is mainly used to provide a speed comparison between several arbitrary precision SDP solvers. The second example shows some directions for further research.
From Data to Decisions: A Distributionally Robust Approach
Speaker: Peyman Esfahani (TU Delft)
When and Where: Wednesday, 12/5/2021, at 14:00, Zoom, via link
Abstract:
A broad spectrum of applications can be viewed as decision-making problems in uncertain and dynamic environments. This class of problems is naturally formulated in an optimization framework whose exact solution is often intractable. In this seminar, we consider tractable randomized (data-driven) counterparts of these programs and discuss a probabilistic bridge between the proposed random solutions and the original ones from both feasibility and performance perspectives. A particular focus will be given to a decision-making procedure known as distributionally robust optimization.
Learning based hardware-centric quantum circuit compilation
Speaker: Merel Schalkers (TU Delft)
When and Where: Friday, 30/4/2021, at 14:00, Zoom, via link
Abstract:
Large fault-tolerant universal gate quantum computers will provide a major speed-up to a variety of common computational problems. While such computers are years away, we currently have noisy intermediate scale quantum (NISQ) computers at our disposal. In this talk we present two quantum machine learning approaches that can be used to find quantum circuits suitable for specific NISQ devices. We present one gradient-based and one non-gradient based machine learning approach to optimize the created quantum circuits to best mimick the behaviour of a given function up to measurement.
In doing this we make sure that the created quantum circuits obey the restrictions of the chosen hardware. These approaches can be used to find circuits perfectly suited for specific NISQ devices, which enables the user to make optimal use of quantum technology in the near future. We present the results of applying both machine learning approaches to two different function types and compare their performance.
Unit distance graphs induced by convex sets
Speaker: Remie Janssen (TU Delft)
When and Where: Friday, 26/3/2021, at 14:00, Zoom, via link
Abstract:
Unit distance graphs are graphs whose nodes are elements of a metric space, and there is an edge between two nodes if they are at distance 1 from each other. Typically, these graphs are studied for their chromatic number, such as in the Hadwiger-Nelson problem, which asks for the chromatic number of the plane. Instead of the chromatic number, in this presentation, we consider the connectedness of unit distance graphs. In particular, we study unit distance graphs \(G^1[X]\) where the nodes are elements of a closed convex subset \(X\) of Euclidean space. The connectedness of these graphs has a simple geometric characterization: \(G^1[X]\) is connected precisely when the radius of the minimum enclosing ball of \(X\) is 0, or it is at least 1 and \(X\) contains at least 3 affinely indepenedent points. In this presentation, I will go through this proof which explicitly builds a path between any two nodes of such a graph.
A Multi-Agent Path Finding approach to Railway Maintenance Operations
Speaker: Jesse Mulderij (TU Delft)
When and Where: Friday, 19/3/2021, at 14:00, Zoom, via link
Abstract:
Apart from its public transportation tasks during the daytime, the Dutch Railways (NS) also have to maintain their fleet of trains. After completing their transportations tasks, trains are routed to a shunting yard where they are cleaned, parked, receive regular maintenance checks and are sometimes repaired. The resulting planning problem is called the Train Unit Shunting and Servicing (TUSS) problem. There is a question that arises from a business strategic point of of view: what is the capacity of a shunting yard? How many train units can it service during a night? I attempt to answer this question in my research. To do so, I model the TUSS problem as an instance of Multi-Agent Path Finding such that a relaxation of the original problem is obtained. When we solve this with an exact algorithm and conclude that there is no feasible solution, an upper bound on the capacity of the shunting yard at hand is obtained. During this talk I will discuss the problem domain, the model and the Branch-and-Cut-and-Price solution method that is used.
Optimizing the Multi Depot Vehicle Scheduling Problem with Time Windows for Picnic
Speaker: Franka van Dijken (TU Delft)
When and Where: Friday, 26/2/2021, at 14:00, Zoom, via link
Abstract:
The problem: I am graduating at Picnic Technologies, an online grocery store. The goal of my thesis is to develop an optimization algorithm that schedules the shipments (trucks delivering goods from one distribution center to the other) as efficiently as possible, given certain feasibility constraints. The input of the algorithm is a list of shipments with a start and end location, an earliest start time, latest start time, earliest end time and latest end time. The output of the algorithm should be a feasible truck and driver planning. A truck planning is a set of trucks that each have a feasible sequence of shipments with fixed start times assigned to them. A driver planning takes into account particular driver restrictions, like a maximal day duration. The mathematical optimization problem that resembles Picnic's problem is the Multi Depot Vehicle Scheduling Problem with Time Windows (MDVSPTW). The algorithm should have a computation time of approximately 10 minutes.
What I did: I translated the problem to a minimum cost flow problem and solved the ILP with Gurobi. After tweaking the parameters, the computation time can be reduced to 20 seconds. However, I am not able to guarantee a short computation time with this method and therefore this algorithm is not applicable for daily use at Picnic. In order to solve this, I decided that I want to spend the time left of my internship on developing a heuristic that provides a "good" solution within a short amount of time. I implemented a first simple local search heuristic, that checks whether the solution improves when swapping two shipments assigned to different trucks.
I would like to discuss some details of the performance of the optimization algorithm, and on the further ideas I have on the heuristics. I very much welcome your input.
Bi-objective special education needs bus routing problem
Speaker: Jacopo Pierotti (TU Delft)
When and Where: Friday, 15/1/2021, at 11:00, Zoom, via link
Abstract:
Dedicated schools for special education needs (SEN) students often offer to transport students from their homes to school due to health and safety considerations. This ride potentially has a negative impact; in fact, some of the students may express a tendency for aggressive behaviour because of a stressful commute. Hence, when designing busses routes, it is important to ensure that every student boards a bus with fellow students they are familiar with. On one hand, SEN students transportation is a very expensive service due to the need for dedicated busses, drivers and attendants (specialized staff). On the other hand, familiarity with the attendants and fellow students is a very important issue because it provides stability, re-assurance and a feeling of safety and security, which in turn contributes to the minimization of any negative impact whilst on-route. In this seminar, I will talk about how to simultaneously consider minimizing routing costs as well as maximizing the familiarity of the students.
Adjustable Robust Machine Scheduling
Speaker: Krzysztof Postek (TU Delft)
When and Where: Wednesday, 13/1/2021, at 14:00, Zoom, via link
Abstract:
Realistic machine scheduling involves two features: (i) task durations may not be known in advance, (ii) after processing some tasks, the scheduler has the possibility to reschedule the remaining tasks. However, existing literature does not consider decision adaptations as more information is revealed. This is despite of the fact that re-optimizing the schedule every time new information is available is a standard practice. One of the reasons for this omission are the fundamental mathematical difficulties when modelling later-stage decisions as adaptive to the new information.
In this paper, we show that taking into account later-stage adjustments into account already at the beginning of the planning horizon can lead to better here-and-now scheduling decisions. In order to do so, we model the problem using mixed integer linear programming, minimizing the worst-case makespan. Numerical study shows that adjustable scheduling leads to solutions with better and more stable makespan realizations across different duration scenarios.