Welcome!
Group seminars occur regularly on Fridays. There is also a Google calendar with the schedule.
Seminars of 2020
On the diameter and the circuit-diameter of polytopes
Speaker: Laura Sanita (TU Eindhoven)
When and Where: Wednesday, 16/12/2020, at 16:00, Zoom, via link
Abstract:
The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices of P, when one is allowed to walk on the edges (1-dimensional faces) of P. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex method for solving Linear Programs.
A generalized notion of diameter, recently introduced in the literature, is that of circuit-diameter, defined as the maximum length of a shortest path between two vertices of P, where the path can use all edge directions (called circuits) that can arise by translating some of the facets of P.
In this talk, I will discuss some algorithmic and complexity results related to the diameter and the circuit-diameter of polytopes, highlighting important open questions.
Local maxima for the Gaussian mass of lattices
Speaker: Antonia Thiemeyer (Cologne)
When and Where: Wednesday, 2/12/2020, at 14:00, Zoom, via link
Machine Learning for Combinatorial Optimization
Speaker: Lara Scavuzzo (TU Delft)
When and Where: Friday, 27/11/2020, at 11:00, Zoom, via link
Abstract:
Within optimization solvers, such as Mixed Integer Programming (MIP) solvers, a large number of algorithmic choices have to be made. In many cases, there is little mathematical understanding on how to approach these decision-making problems. At the same time, these choices have a great impact on the speed of the solution process. For this reason, there is an interest in better decision strategies.
In this talk, we will discuss recent work in a growing line of research: incorporating Machine Learning (ML) techniques into the algorithmic design process. Starting with an overview of the progress in this field and the remaining challenges, we will focus on ML for MIP solvers, finishing with a deep dive into learning to branch in the context of the Branch & Bound algorithm.
Decoding Criteria for Noisy Channels with Offset Mismatch
Speaker: Renfei Bu (TU Delft)
When and Where: Friday, 20/11/2020, at 11:30, Zoom, via link
Abstract:
All real systems that work with digitally represented data, such as CD players, TV, fax machines, internet, satellites, mobiles, require to use error-correcting coding techniques because all real channels are, to some extent, noisy. Besides the noise, an unknown offset mismatch is another nuisance in many communication and storage systems. In this talk, I will introduce basics of coding theory, what decoding criteria are possible to use, and an example of the maximum likelihood decoding criterion for channels with uniform noise and signal-dependent offset.
Cap sets and related problems in combinatorics
Speaker: Josse van Dobben de Bruyn (TU Delft)
When and Where: Friday, 20/11/2020, at 11:00, Zoom, via link
Abstract:
In this talk, I will discuss the cap set problem and a number of closely related problems in combinatorics. The cap set problem was unexpectedly solved in 2016 by Ellengberg and Gijswijt (independently), using a ground-breaking new technique developed by Croot, Lev and Pach earlier that same year. This was a major breakthrough, and led to a flurry of research on related problems. However, many of these related problems remain to be solved.
Sum-of-squares hierarchies for binary polynomial optimization
Speaker: Lucas Slot (CWI)
When and Where: Wednesday, 18/11/2020, at 14:00, Zoom, via link
Flow-based Routing Model of Heterogeneous Vehicles in Mixed Autonomous and Non-autonomous Zone in Urban Areas
Speaker: Qiaochu Fan (TU Delft)
When and Where: Friday, 13/11/2020, at 11:30, Zoom, via link
Abstract:
The era of intelligence transportation is coming. Nonetheless, the transition to an intelligent system will be a gradual process. On the one hand, some zones in the city may be dedicated as autonomous zone with a fully intelligent traffic facility allowing only autonomous vehicles. On the other hand, autonomous and conventional vehicles are both allowed to drive in the remains zone of the network. In this paper, we consider a situation where AVs are deployed by a taxi operating company to serve door-to-door travel requests. Facing this transition period, a flow-based vehicle routing model is developed to determine the optimal fleet size of autonomous and conventional taxis as a function of the gradually increasing coverage of the automated vehicles-only area. Traffic congestion is considered as a dynamically varying travel time with the vehicle flows. In this paper, two service regimes of the company are tested: User Preference Mode (UPM) and System Profit Mode (SPM). The developed model formulations are applied to a case study. The results give insight into the performance of the heterogeneous taxi system on a hybrid network. Strategies are presented on how to adjust the fleet size of autonomous and conventional taxis to get the best system profit while satisfying the mobility demand. The SPM can bring more profit to the operating company by reducing the detour and relocation distance of taxis compared to the UPM.
Studying 1-avoiding sets on the ball
Speaker: Guillermo Fernández Castro (TU Delft)
When and Where: Friday, 13/11/2020, at 11:00, Zoom, via link
Abstract:
How large can a subset of the unit ball be when no two points in the set can be separated by a distance of 1? This question has yet to be answered, and there are no good upper bounds. One promising approach would consist in searching for upper bounds using techniques from semidefinite optimization. In particular, our strategy is based on the Lovász theta number, originally defined in order to bound the independence number of a finite graph. In this talk I will introduce the problem of 1-avoiding sets on the ball, how it relates to colorings of Euclidean space, and how the theta number provides us with a strategy to solve it.
On cherry-picking and network containment
Speaker: Yuki Murakami (TU Delft)
When and Where: Friday, 6/11/2020, at 11:30, Zoom, via link
Abstract:
Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks, to distinguish different networks, and to see when one network is contained in another. In this talk, we introduce cherry-picking networks, a class of networks that can be reduced by a sequence of two graph operations. We show that some networks are uniquely determined by the sequences that reduce them -- we call these the reconstructible cherry-picking networks, and further show that given two cherry-picking networks within the same reconstructible class, one is contained in the other if a sequence for the latter network reduces the former network. By restricting our scope to tree-child networks, we show that the converse of the above statement holds, thereby showing that Network Containment, the problem of checking whether a network is contained in another, can be solved in linear time for tree-child networks. Lastly, we provide a linear time algorithm for deciding whether two tree-child networks are isomorphic.
An exact method for the Resource Constrained Project Scheduling Problem with a flexible Project Structure
Speaker: Tom van der Beek (TU Delft)
When and Where: Friday, 6/11/2020, at 11:00, Zoom, via link
Abstract:
Traditional shipbuilding often involves one-off building and engineering. This means that each ship is individually designed and built, which ensures that each ship can be fully tailored to the customers wishes. However, this process also leads to a high duration of the engineering and production process. Since ship availability can be the bottleneck in various projects, a decrease in makespan (time between ordering a ship and receiving it) is desired. One proposed method is modular shipbuilding, which divides the ship into pre-engineered modules. These modules have different ways of being produced and each method might fit in differently with the rest of the project. This complicates the project scheduling problem. Where in the traditional scheduling problem the question is: 'When to execute each activity?', in this problem the question 'Which activities to execute?' is added. This results in the resource constrained project scheduling problem with a flexible project structure. Currently, we work on an exact method for this problem. This method identifies sets of activities for which at least one has to be executed and sets of activities for which at most one can be executed. Based on these sets, cutting planes are created and a variable reduction method is proposed to speed up the solving process.
Directed Graph Burning
Speaker: Remie Janssen (TU Delft)
When and Where: Friday, 30/10/2020, at 11:30, Zoom, via link
Abstract:
Graph burning is a recent model of social contagion---the spread of information through a social network---introduced by Bonato, Janssen (not me!), and Roshanbin. The model is formulated in a graph theoretical setting, where each node represents a social actor, and the edges represent information channels between actors. For example, nodes may represent users in an online social network so that the edges are friend relations. Graph burning is a discrete process on graphs, where in each step information is shared to all neighbours (i.e., all neighbours of currently burned nodes are burned), and an additional user is chosen to spread the information to (i.e., this node is burned, irrespective of its neighbours). Typical questions for this model are: What is the maximal number of steps needed to burn all nodes in a graph of certain size/type--- in other words, how fast can we spread information to all nodes? And, what is the computational complexity of determining the minimal number of steps needed to burn a given graph? In the original setting, the graphs were undirected, so the interactions were always bi-directional. Of course, information may also flow in a single direction, such as in online networks where users follow other users but not necessarily vice versa. To incorporate these asymmetrical interactions, I have introduced directed graph burning, and I have partly answered the questions about bounds and complexity for directed graph burning problems. In this talk, I will give the proof ideas for these bounds and complexity results.
Reinforcement Learning for the Pick-up & Delivery Problem
Speaker: Jacopo Pierotti (TU Delft)
When and Where: Friday, 30/10/2020, at 11:00, Zoom, via link
Abstract:
The pick-up and delivery problem is an NP-hard problem where a set of vehicles aims to visit clients' pick up and delivery nodes at minimum cost. Reinforcement learning has proven to be an outstanding method for finding good solutions in a short time (after training). In this seminar, I will explain how we intend to combine the two.
Introduction to the universal optimality of the \(E_8\) and Leech lattices
Speaker: Andreas Spomer (U. Cologne)
When and Where: Wednesday, 7/10/2020, at 16:00, Zoom, via link
Abstract:
In the article "Universal optimality of the E8 and Leech lattices and interpolation formulas" by Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko and Maryna Viazovska the authors showed that the \(E_8\) root lattice and the Leech lattice minimize the energy for every completely monotonic potential function of squared distance. This implies that the lattices are optimal configurations for many different optimization problems. In my talk I want to present the underlying strategy used to prove this result. We will take a look at the linear programming bound for periodical configurations and the resulting interpolation formula.
Algebraic geometric codes
Speaker: Willem de Muinck Keizer (U. Bonn)
When and Where: Thursday, 10/9/2020, at 16:00, Zoom, via link
Abstract:
During transmission of data, errors may occur. It is the goal of coding theory to find efficient ways of encoding data such that errors may be detected, or even corrected. Since at least 1952, it has been known that the asymptotic parameters of codes may be bounded from below by the Gilbert-Varshamov (GV) bound. In 1977 Goppa introduced algebraic geometric codes by associating a code to certain divisors on a curve over a finite field. Not long thereafter in 1982 Tsfasman, Vlăduţ and Zink (TVZ) employed these algebraic geometric codes to produce a ground-breaking example of a sequence of codes with better asymptotic parameters than the GV-bound. The main goal of the talk will be to understand Goppa’s construction of algebraic geometric codes and to see the interplay between geometry and coding theory. The required material from coding theory and algebraic geometry will be introduced or motivated and no prerequisites in either area are assumed. If time allows, the result of TVZ will be discussed in more detail.
Maritime Inventory Routing using Constraint Programming
Speaker: Jacco Teitsma (TU Delft)
When and Where: Friday, 4/9/2020, at 11:00, Zoom, via link
Abstract:
The maritime inventory routing problem (MIRP) concerns finding an optimal routing schedule for oil-distributing ships, with the additional constraints that the minimum and maximum inventory levels at the delivery ports should not be violated. Usually, this problem can be formulated as a Mixed Integer Program (MIP) and can be solved using MIP techniques. An alternative approach is to use Constraint Programming (CP). CP utilizes the structure of a problem given by its constraints in order to reduce the search space. For this reason, CP might be useful for problems with high complexity, such as the MIRP. The primary goal of this thesis is to compare the performance of the solution approaches that are based on MIP and CP.
The application of machine learning in phylogenetics
Speaker: Bryan Versendaal (TU Delft)
When and Where: Friday, 10/7/2020, at 11:00, Zoom, via link
Abstract:
Phylogenetics is the study of evolutionary networks and trees. Many of the algorithms that are used with in the branch of mathematics hold a form of random choice. For example, the algorithm to find a maximum agreement forest between two graphs makes random branching choices. With the right data, machine learning can be used to take away the randomness in some of the algorithms by making the learner decide on what to branch. Machine learning can be used to decrease the runtime of the algorithms, which are in many cases fixed parameter tractable. In this presentation I will show some of the results that I have found so far by implementing machine learning into the current algorithms. The problems that will be discussed are the hybridization number and some early results on the tail move problem.
Solving a non-permutation hybrid flow shop with parallel batching and setup times, applied to a CSD
Speaker: Guusje Scheijen (TU Delft)
When and Where: Friday, 3/7/2020, at 11:00, Zoom, via link
Abstract:
Optimizing the logistics of goods and pharmaceuticals within a hospital can lead to a significant reduction in costs. One of the logistic processes that can be optimized is the sterilization of the reusable instruments used in the operating rooms (OR). This process takes place at the Central Sterilization Department (CSD) and consists of two main steps executed by batch processing machines with a setup time prior to each step. The setup at each stage is executed manually by employees. The machines at a CSD are renewed every 10 years, which provides an opportunity to determine the needed resources. In this thesis, the costs to sterilize all instruments are minimized, while always satisfying the demand of the OR, given the fact that there could be severe consequences if a surgery has to be rescheduled or cancelled due to missing instruments. Costs include: acquiring machines, machine batch costs, maintenance costs, and staff costs depending on the opening hours. To solve these strategic questions, a scheduling problem has to be solved. The optimal number of resources can only be determined when the makespan for that number of resources and jobs is known as well. The process can be modelled as a two-stage flow shop with parallel batching and sequence independent setup times. However, to obtain a more compact formulation, the process is also modelled as a four-stage flow shop with parallel batching at two stages. As the described problem is NP-hard, meta-heuristics can be used solve to the problem. Especially hybrid algorithms are often mentioned in recent literature covering different variants of hybrid flow shop problems. The results can be used to determine guidelines for renewing a CSD and help make strategic decisions regarding the number of machines, opening hours and employee numbers.
Incorporating flexible track use in the SAT model of the Dutch railway timetabling problem
Speaker: Maaike Vollebergh (TU Delft)
When and Where: Friday, 26/6/2020, at 11:00, Zoom, via link
Abstract:
The construction of cyclic railway timetables is an important task for Netherlands Railways (NS). This construction can be formulated as a Periodic Event Scheduling Problem (PESP). The most powerful technique for solving cyclic railway timetabling problems is constraint programming, especially via SAT solvers when PESP instances are encoded as SAT instances. SAT solvers can determine the feasibility of problem instances of NS quickly and reliably. However, in previous implementations the problem specification must explicitly indicate the track use within the stations and on four-track sections. As a result, the solver also reports infeasibility if a small adjustment of the track allocation could lead to a feasible timetable. In this graduation project, carried out at NS, flexible track use is incorporated in the SAT formulation.
In this talk, the PESP model for the construction of cyclic railway timetables is discussed, as well as its conversion to SAT. Furthermore, the method to incorporate multiple route options for each train in the SAT formulation and its implementation are presented.
BEP student seminar
Speaker: BEP Students (see below)
When and Where: Wednesday, 24/6/2020, at 14:00, Zoom, via link
Abstract:
In this seminar our Bachelor's students will talk about their projects:
- Guus van Hemert: Codes for Noisy Channels with Unknown Offset.
- Manuela Hooghwerff: Optimization Algorithms for Improving the Efficiency of a Tandem Solar Cell.
- Sarah Jansen: Optimization of entanglement distillation protocols via group theoretical tools.
Clique-free pseudorandom graphs
Speaker: Anurag Bishnoi
When and Where: Friday, 29/5/2020, at 14:00, Zoom, via link
Abstract:
One of the outstanding open problems in the theory of pseudorandom graphs is to show the existence of \(K_s\)-free \((n, d, \lambda)\)-graphs, for any fixed \(s > 3\), with \(\lambda = O(\sqrt{d})\) and the highest possible edge density of \(d/n = \Theta(n^{-1/(2s - 3)})\). By an \((n, d, \lambda)\)-graph we mean a \(d\)-regular graph on \(n\) vertices whose second largest eigenvalue in absolute terms is at most \(\lambda\). For \(s = 3\), there is a famous construction of Alon from 1994 that provides such a family of triangle free graphs, while for all \(s \geq 4\) the problem remains open. The best known construction for larger values of \(s\) is due to Alon and Krivelevich from 1997 that has edge density \(\Theta(n^{-1/(s - 2)})\).
Recently, Mubayi and Verstraete showed that the existence of such graphs would determine the right exponent of \(t\) in the off-diagonal Ramsey number \(R(s, t)\) (\(s\) fixed and \(t \rightarrow \infty\)), which has been open for decades. In fact, a construction with edge density \(\Omega(n^{-1/(s + \epsilon)})\), for any \(\epsilon > 0\), would already imply an improvement in the best known lower bounds on \(R(s, t)\) that were proved by Bohman and Keevash using probabilistic methods.
In this talk I will present a construction of \(K_s\)-free \((n, d, \lambda)\)-graphs with \(\lambda = O(\sqrt{d})\) and edge density \(\Theta(n^{-1/(s - 1)})\), thus providing the best known \(K_s\)-free optimal pseudorandom graphs for all \(s \geq 5\). The construction uses the theory of quadratic forms over finite fields. I will also discuss possible approaches to further improvements using finite geometry.
(Joint work with Ferdinand Ihringer and Valentina Pepe.)
On the real-time aspect of Dynamic Time Slot Management
Speaker: Quiten Cederhout (TU Delft)
When and Where: Friday, 21/2/2020, at 16:00, Turing room
Abstract:
Attended home delivery is the practice in which a company, often a retailer, delivers products to the home of their customers. It is called ‘attended’ because the customers need to be at home at the time of delivery. As retailers want to provide good customer service, a system using so-called time slots became popular, mainly within internet shopping. The idea is that when a customer places an order they receive a list of time slots from the retailer, which are very strict time windows. The customer then picks the time slot in which they want the delivery to be made. For the retailer it is important that all the accepted orders fit in a feasible routing schedule. To ensure this they make use of a system, commonly referred to as Dynamic Time Slot Management (DTSM).
This presentation is the mid-term of my master’s thesis. I will explain what DTSM entails and what research has been done in this area. Furthermore, I will discuss my research topic, which is about the real-time aspect of DTSM. The real-time aspect brings some problems that are often ignored in theory. My goal is to explore possible solutions which can be used in a practical setting.
Adjustable robust optimization to solve multistage optimization problems under uncertainty
Speaker: Frans de Ruiter (Eindhoven CQM)
When and Where: Friday, 14/2/2020, at 16:00, Hilbert room
Abstract:
Robust optimization has become an important paradigm to deal with optimization under uncertainty. In this talk we introduce adjustable robust optimization, which is an extension that deals with multistage problems. We further outline new primal and dual approaches to this seemingly intractable problem. In the primal approach we explain how decision rules can be used to compute solutions of high quality. A dual approach then exploits various aspects that lead to new model formulations. Although these formulations are equivalent to the original models, they have a different structure which allows us to solve problems more efficiently using linear decision rules. Motivated by a real world, huge scale, pickup and delivery problem we highlight the benefits of adjustable robust optimization.
Recursive Inspection Games
Speaker: Bernhard von Stengel (LSE)
When and Where: Friday, 17/1/2020, at 16:00, Hilbert room
Abstract:
We consider a sequential inspection game where an inspector uses a limited number of inspections over a larger number of stages to detect an illegal act of an inspectee. Compared with earlier models, we allow varying "rewards" to the inspectee for successful illegal acts. As one possible example, the inspectee may target a certain amount of stealing nuclear material that he accummulates over several stages, where the stage where he completes that target of stolen material gives him the highest reward. The players' information about the game is important in how to solve it, in particular since the inspector does not know what the inspectee does in an uninspected time period. Under reasonable assumptions for the payoffs, the inspector's strategy is independent of the number of successful illegal actions, so that a recursive description of the game can be used even though this assumes a fully informed inspector. We give an explicit solution for the optimal randomized strategies in this game, and describe how the inspector can induce legal behaviour (as long as inspections remain) by committing to his strategy.
Short bio: Bernhard von Stengel is professor of mathematics at the London School of Economics. His professional degrees are in mathematics and in computer science. He is interested in the geometry and computation of Nash equilibria and other mathematical questions of game theory and operations research.