Welcome!
Group seminars occur regularly on Fridays. There is also a Google calendar with the schedule.
Seminars of 2019
Optimizing the investment planning of Multi Energy Systems: Solution methods for a Generalized Multi-Commodity Multi-Period Network Design Problem
Speaker: Noortje Bonenkamp (TU Delft)
When and Where: Friday, 13/12/2019, at 16:00, Hilbert room
Abstract:
Even though interactions between energy infrastructures have always taken place and are increasing, they are considered and operated almost independently. In this thesis, so-called Multi Energy Systems are studied, where multiple energy carriers interact with each other at different levels through for example conversion- or storage units. By optimizing these interactions, the long-term planning of the energy infrastructure can be optimized. In this thesis, a graph-theoretic modeling framework for this long-term planning is created by developing a network flow model. A Generalized Multi-Commodity Multi-Period Network Design Model is proposed, where investment costs should be minimized. The complexity of the problem and the large number of variables and constraints result in excessive computing times and large optimality gaps. Heuristic methods will be applied to the optimization problem and to some of its variations in order to approximate good solutions.
Efficient Computation of the Deuring Correspondence
Speaker: Alexander Krigsman (CWI)
When and Where: Friday, 29/11/2019, at 16:00, Hilbert room
Abstract:
In 2018, Galbraith et al. proposed an identification scheme for supersingular isogeny cryptology which relies on the explicit computation of what is known as the Deuring correspondence. In this talk we discuss the following problem: Given a supersingular elliptic curve isogeny \(\varphi : E \to E^\prime\), efficiently compute the kernel ideal of \(\varphi\). We also discuss the inverse problem: Given a left \(\mathrm{End}(E)\)-ideal \(I\), efficiently compute an isogeny \(E \to E^\prime\) with kernel ideal \(I\). Furthermore, we improve on the algorithms of Galbraith et al. by computing elliptic curve arithmetic in a quadratic twist of \(E\) when it is more efficient to do so.
Integrality Gap Instances and Combinatorial Structure of Gilmore-Gomory LP for Bin Packing
Speaker: Yash Patel (University of Bonn)
When and Where: Friday, 22/11/2019, at 16:00, Hilbert room
Abstract:
Bin packing has been the cornerstone of approximation algorithms and has been extensively studied since the early 1970s. Up to date, the best approximation algorithm has an additive error of \(O(\log n)\) due to Hoberg et al. [2017]. However, in practice, computational simulations have shown that the bin packing instances have small integrality gap, 1.1 being the largest due to Kartak et al. [2018]. In the first part of this talk, we address the difference between lower bounds on solution quality of Gilmore-Gomory LP in theory and practice. More specifically, we give proof on bounds of the integrality gap for certain non-trivial class of bin packing instances and show experimental results about a proposed construction mechanism for generating instances with large gaps.
Goemans et al. [2014] and Jansen et al. [2017] prove the polynomiality of bin packing problem with fixed number of different item types whose running time is \(O(\log \Delta)^{2^{O(n)}}\), where \(\Delta\) is an upper bound on each absolute value of input. A natural question arises from these works: to what extent better structural results about the optimal solutions can be proved, in the setting where only approximate solutions are of interest? More specifically, what would be the running time for bin packing problem if we were to design an algorithm with an additive error of one. In this spirit, we give an overview of an \(\mathsf{OPT} + 1\) polynomial time approximation algorithm which was derived by studying the structure of underlying integer polytope induced by Gilmore-Gomory LP.
Lubin-Tate theory
Speaker: Guillermo Fernández Castro
When and Where: Friday, 15/11/2019, at 16:00, Hilbert room
Abstract:
In number theory, class field theory is the study of number fields---extensions of the field of rational numbers---and their Abelian extensions. Arising from Gauss's law of quadratic reciprocity, it was fully developed in the first half of the 20th century, and adapted to local fields. However, the cohomological methods that became standard for proving the central statements lacked expliciteness. This was remedied in the 1960s, when Lubin and Tate introduced a novel approach to the theory based on formal groups. The aim of this talk is to give an introductory exposition of the theory as it was formulated by Lubin and Tate. This was the topic of the Master's thesis written by the speaker.
Exact semidefinite programming bounds for packing problems
Speaker: David de Laat (TU Delft)
When and Where: Friday, 8/11/2019, at 16:00, Hilbert room
Abstract:
To solve semidefinite programs we use interior point solvers that work with (high precision) floating point numbers. This means that the output of the solver consists of floating point data. In this talk I will explain our heuristic to round the output of a semidefinite programming solver to a rational solution. We use this to prove that some optimal packing configurations are unique. I will also explain our extension of this algorithm to quadratic fields and explain where we can apply this.
An FPT algorithm for temporal hybridization
Speaker: Sander Borst (TU Delft)
When and Where: Friday, 1/11/2019, at 16:00, Lipkenszaal, LB01.150
Abstract:
An important problem in biology is the reconstruction of a hybridization network that represents the evolutionary history of species. Mathematically this corresponds to finding a minimum hybridization network that displays a set of phylogenetic trees, which is a NP-complete problem.
In my thesis I looked at a problem variant called temporal hybridization that adds biological meaningful restrictions to the problem. This lead to the development of a new faster FPT algorithm for this problem. In this presentation I will describe the problem and the workings of the algorithm.
On the Sybil-proofness of Accounting Mechanisms in Distributed Systems
Speaker: Alexander Stannat (TU Delft)
When and Where: Friday, 25/10/2019, at 16:00, Hilbert room
Abstract:
One of the most prevalent problems in distributed systems is that of organising cooperation among multiple processors in a network. A particular example of distributed systems are P2P file-sharing networks, in which agents distribute files by up- and downloading data to one another. Agents that are interested in a particular file will query a node holding the file and the holder of the file will expend some bandwidth to supply the querying node. The problem is that there is an obvious incentive to consume data, while there is a clear disincentive to share files with other nodes. This leads to the pervasive problem known as the tragedy of the commons, in which the interests of individuals are misaligned with the interests of the collective.
In this thesis we investigate mechanisms of indirect reciprocity, called accounting mechanisms, which are functions by which agents evaluate the cooperativeness of their peers. Based on this information, nodes can decide wether or not to interact with another node and consequently cooperation is incentivised. In particular, we focus on the effects fake accounts and false reports about previous interactions have on the values returned by accounting mechanisms. We analyse and improve upon existing theoretical frameworks in the problem of sybil attacks, providing a framework for the classification of malicious actors and additionally analyse some theoretical requirements accounting mechanisms should satisfy in order to be resistant to sybil attacks that threaten to compromise an entire network.
Quantum Coin Flipping Lower Bounds using Semidefinite Optimization
Speaker: Roy van Houte (TU Delft)
When and Where: Friday, 27/9/2019, at 16:00, van der Poelzaal LB 01.220
Abstract:
Coin flipping is a cryptographic primitive in which two parties want to establish a fair random bit by using a communication channel. Both parties want to choose a protocol that limits the possibility of a cheater to enforce a chosen outcome (called the bias). Using classical information channels, it is possible to limit a cheaters influence only with complexity assumptions.
However, using quantum channels, we do not necessarily need these assumptions. The optimal cheating strategy for a given protocol is then given by the solution of a semidefinite program on Hermitian matrices. Using two primal dual-pairs, we derive a lower bound on the bias. This allows for extensions which form the scope of the graduation thesis.
The Constrained-degree percolation model
Speaker: Bernardo N.B. de Lima (Federal University of Minas Gerais, Belo Horizonte, Brazil)
When and Where: Thursday, 19/9/2019, at 16:00, Room Chip (EWI)
Abstract:
In the Constrained-degree percolation model on a graph \((V,E)\) there are a sequence, \((U_e)_{e\in E}\), of i.i.d. random variables with distribution \(U[0,1]\) and a positive integer \(k\). Each bond \(e\) tries to open at time \(U_e\), it succeeds if both its end-vertices would have degrees at most \(k-1\). We prove a phase transition theorem for this model on the square lattice \(\mathbb{L}^2\), as well on the d-ary regular tree. We also prove that on the square lattice the infinite cluster is unique in the supercritical phase. Joint work with R. Sanchis, D. dos Santos, V. Sidoravicius and R. Teodoro.
Formal verification of upper bounds of translative packing densities of solids with tetrahedral symmetry
Speaker: Ike Mulder (TU Delft)
When and Where: Friday, 21/6/2019, at 15:00, Van Katwijkzaal HB03.230 (Building 36)
Abstract:
Packing problems are about filling the space with copies of a certain object. The famous Kepler conjecture asserts that the cannonball packing of spheres is the most efficient packing achievable, and was recently formally proven by Hales. A paper by Dostert, Guzman, Oliveira Filho and Vallentin proved new upper bounds of translative packing densities of various Archimedean solids. However, their results rely heavily on complex computer calculations to ensure they satisfy the conditions of a theorem. Our aim is to formally verify these conditions using proof assistant Coq. The various obstacles of this formal verification will be discussed in the presentation.
Transforming quantum circuits to comply with nearest neighbor constraints while having minimal impact on circuit length
Speaker: Jesse Mulderij (TU Delft)
When and Where: Friday, 14/6/2019, at 16:00, Hilbert room
Abstract:
Analogous to classical computing, quantum computing uses quantum bits (also known as qubits), -gates and -circuits as its building blocks. Quantum computations are done in the form of a quantum circuits, where operations are applied on information stored in an array of qubits by the use of a cascade of quantum gates. There are, however, some physical limitations that restrict the size and architectural freedom in designing quantum circuits. The most notable of the limitations include the coherence times of qubits, nearest neighbor constraints and the need for error correction. The problem discussed in this talk addresses the former two of the limitations.
The coherence times of qubits puts a constraint on the length of a circuit after which the information stored in the qubits is lost. Due to the nearest neighbor limitation, gates can only act on pairs of adjacent qubits. The positions of two adjacent qubits can be swapped, making use of the so called SWAP gate, but adding these increases the circuit length. We take a look at exact solution methods to the problem of Nearest Neighborhood Compliance (NNC), where the qubits are physically in a one dimensional array. In NNC, a minimal number of SWAP gates is added to a quantum circuit in order to make it compliant with the nearest neighborhood constraints.
MIP Modelling Made Manageable
Speaker: Mark Wallace (Monash University)
When and Where: Friday, 24/5/2019, at 16:00, Hilbert room
Abstract:
Can a user write a good MIP model without understanding linearization? Modelling languages such as AMPL and AIMMS are being extended to support more features, with the goal of making MIP modelling easier. A big step is the incorporation of predicates, such a “cycle” which encapsulate MIP sub-models.
This talk explores the impact of such predicates in the MiniZinc modelling language (www.minizinc.org) when it is used as a MIP front-end. It reports on the performance of the resulting models, and the features of MiniZinc that make this possible.
A geometric proof of Kadison's anti-lattice theorem
Speaker: Josse van Dobben de Bruyn (TU Delft)
When and Where: Friday, 10/5/2019, at 16:00, Hilbert room
Abstract:
In 1951, Sherman proved that a \(C^*\)-algebra is commutative if and only if it is lattice ordered. This led Kadison to ask under which circumstances two Hermitian operators \(A\) and \(B\) have a supremum (or infimum) under the positive semidefinite order. His so-called anti-lattice theorem shows that this is only the case if \(A\) and \(B\) are comparable, in which case the supremum (infimum) is simply the largest (smallest) of the two. Kadison concludes that the space of Hermitian operators cannot be further away from a lattice (an "anti-lattice"). The original proof relies on the tools of operator theory, and does not relate to the geometry of the underlying Hilbert space. In this talk, we show that the space of Hermitian operators still has a quasi-lattice structure, and outline a new geometric proof of the anti-lattice theorem. We restrict our attention to the finite-dimensional case, allowing us to exhibit the most important geometric ideas without dealing with the subtleties of infinite-dimensional Hilbert space theory.
Solving conic optimization problems using MOSEK
Speaker: Erling D. Andersen (MOSEK)
When and Where: Friday, 5/4/2019, at 16:00, Hilbert room
Abstract:
Convex optimization problems are an exciting class of problems because they can in most cases be solved efficiently in theory and practice.
Now any convex optimization problem can be expressed as a conic optimization problem i.e. to minimize a linear function subject to a set of linear equalities intersected with a convex cone. Furthermore, the amazing fact is that almost all practical convex optimization problems can be expressed in conic form using only five cone types. This fact makes it possible to build very general yet reliable and efficient software for solving conic optimization problems.
Therefore, this presentation will begin with an introduction to conic optimization and illustrate the usage of conic optimization in various applications. This is followed by an introduction to MOSEK a state-of-the-art software package for conic optimization. Some details about the algorithm and numerical linear algebra employed inside MOSEK may be discussed if time permits. Finally, benchmark results will be presented that illustrates large scale sparse conic optimization problems can be solved efficiently.
A simulation based approach to synchromodal container transport
Speaker: Wouter de Koning (TU Delft)
When and Where: Friday, 22/3/2019, at 16:00, Hilbert room
Abstract:
The challenge faced by a Dutch logistic service provider (LSP) is the transportation of containers from the Eastern part of the country to the Port of Rotterdam and vice versa. Every day, multiple barges depart from the single inland terminal in the East to different deep-sea terminals within the Port of Rotterdam. The region (the Port of Rotterdam) is far away from the origin (the single inland terminal), but locations within the region are close to each other. That is why the long-haul trip from the origin to the region is the most challenging one. Moreover, the terminals within the region are controlled by other agents in the network. When the pick-up or delivery terminal becomes known, the LSP has to make a call towards that terminal in order to request for a specific date and time. After a delay of approximately half-a-day the requested appointment is confirmed, but might deviate from the requested one, which means that decisions has to be made based on uncertain information.
The problem of routing vehicles and scheduling containers can be modelled as a multi-commodity network design problem on a time-space graph. In addition, the uncertainty in the data caused by the requested appointments is a special characteristic in this problem. To deal with this uncertainty, a simulation based approach is proposed. Due to the increasing computational time for larger instances, a heuristic needs to be formulated that makes it possible to run several simulations within feasible time. The goal is to obtain a model that could serve as a decision support system (DSS) for the LSP.
Optimising the sourcing strategy for a company which relies on the backhauls of third party logistic providers for transportation gives rise to a complex problem.
Speaker: Thijs Seppen (TU Delft)
When and Where: Friday, 8/3/2019, at 16:00, Hilbert room
Abstract:
The problem is an extension of the Transportation Problem, adding product, time and size dimensions. Moreover, there is uncertainty in the number of trucks that are available for transporting freight from a supplier to a customer. This uncertainty can lead to under deliveries of customer demand, and bought product which cannot be picked up. These risks in the sourcing strategy are modelled as penalties which are subtracted from the expected profit.
We define a mixed integer programming model with the objective to maximise the expected profit. The model produces a truck schedule with corresponding contracts to buy at the suppliers. The real life instances that need to be solved on a daily basis, yield (tens of) millions of variables to optimize. As the solution is needed within hours, using a global approach (CPLEX solver) to obtain an exact solution is undesirable, due to the computing time needed. Therefore, a local search heuristic for this problem needs to be formulated. Thoughts about an initial solution and neighbourhood function are posed.