DMO Seminar Archives

14 December 2023 14:00 till 15:00

[DMO] Esther Julien: Neur2RO: Neural two-stage robust optimization

Robust optimization provides a mathematical framework for modeling and computing solutions to decision-making problems under worst-case uncertainty. In this talk I will present recent work in two-stage robust optimization (2RO) problems, wherein first-stage and second-stage decisions are made before and after uncertainty is realized. This results in a nested min-max-min optimization problem, which generally means that we are dealing with computationally challenging problems, especially in case of integer decisions. Together with my co-authors, we propose Neur2RO, an efficient machine learning-based algorithm. We learn to estimate the value function of the second-stage problem via a neural network architecture designed to construct an easy-to-solve surrogate optimization problem. Our computational experiments on two 2RO benchmarks demonstrate that we can find near-optimal solutions among different sizes of instances, often within orders of magnitude less computing time.
In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question leads to having to look at combinatorial objects such as set systems and Kneser graphs, and is connected to several open problems in those areas.
This is joint work with Xinyi Xu.

23 November 2023 14:00 till 15:00

[DMO] Lara Scavuzzo Montaña : Lattice reformulations for Integer Programming

Integer Programs (IP) play a pivotal role in addressing complex optimization problems with discrete decision variables. IPs are typically solved with the branch-and-bound algorithm using single-variable disjunctions. In contrast, all algorithms for IP that offer theoretical guarantees use a non-binary search tree with general disjunctions based on lattice structure. These algorithms are not used in practice because such disjunctions are expensive to compute and challenging to implement. However, some lessons can be drawn. In this presentation, we will discuss algorithms for IP using that point of view. In particular, we will discuss lattice reformulations for IP, which can be re-interpreted as heuristic methods to obtain general disjunctions in the original space.

17 November 2023 14:00 till 15:00

[DMO] Carla Groenland: Graph reconstruction from small cards

The graph reconstruction conjecture states that each graph G on at least 3 vertices can be reconstructed from the multiset of all induced subgraphs on n-1 vertices. Although this conjecture is notoriously difficult, it is easy to reconstruct some information about the graph, e.g. the degree sequence of G and whether G is connected. We study a set-up with smaller induced subgraphs ('small cards'). Using a theorem about the number of positive real roots of a complex polynomial, we show the induced subgraphs on 0.9n vertices determine whether an n-vertex graph is connected and we also develop counting techniques to reconstruct trees from subgraphs of size about 8n/9.
This is based on joint work with Tom Johnston, Alex Scott and Jane Tan.

27 October 2023 14:00 till 15:00

[DMO] Norbert Zeh: An FPT Algorithm for Scanwidth

We show that the scanwidth of a directed acyclic graph can be computed in O(f(k) * poly(n)) time, where k is the scanwidth. The scanwidth is yet another width measure of graphs, one that has been shown to be useful in phylogenetics; as an example, the tree containment problem can be solved efficiently when parameterized by the scanwidth of the network given as part of the input. Recently, Holtgrefe presented an O(n^f(k)) algorithm to compute the scanwidth of a DAG, leaving open the question whether there exists an algorithm with FPT running time (O(f(k) * poly(n))). Over the last two weeks, Holtgrefe, van Iersel, Jones, and I developed such an algorithm, borrowing ideas from similar algorithms for treewidth, pathwidth, and cutwidth. This talk reviews what scanwidth is and describes our algorithm.

27 June 2023 11:00 till 15:00

[DMO] Bram Bekker: Semidefinite programming bounds for distance-avoiding set problems on the sphere

Witsenhausen’s problem asks for the set with largest area on the n-dimensional unit sphere such that no two points in this set are orthogonal. Distance-avoiding set problems are a broader class of of problems, where we want to find maximal subsets of the unit sphere that avoid a given set of inner products. By exposing these problems as maximal independent set problems on an infinite graph, we can use semidefinite programming to obtain upper bounds. We developed hierarchies of strengthenings of the Lovász theta-number to obtain the best upper bounds known. A result of theoretical significance is the proof that these hierarchies all converge to exactly the independence number of the graph.

23 June 2023 14:00 till 15:00

[DMO] Bram Bekker: Semidefinite programming bounds for distance-avoiding set problems on the sphere

Witsenhausen’s problem asks for the set with largest area on the n-dimensional unit sphere such that no two points in this set are orthogonal. Distance-avoiding set problems are a broader class of of problems, where we want to find maximal subsets of the unit sphere that avoid a given set of inner products. By exposing these problems as maximal independent set problems on an infinite graph, we can use semidefinite programming to obtain upper bounds. We developed hierarchies of strengthenings of the Lovász theta-number to obtain the best upper bounds known. A result of theoretical significance is the proof that these hierarchies all converge to exactly the independence number of the graph.

26 May 2023 15:00 till 16:00

[DMO] Random colourings of trees with constant down degree: David de Boer

03 May 2023 14:00 till 15:00

[DMO] Ferdinand Ihringer : Some methods for modifying strongly regular graphs

A graph is called strongly regular with parameters (v, k, \lambda, \mu) if it has v vertices, each vertex has degree k, two adjacent vertices have precisely \lambda common neighbors, and two nonadjacent vertices have precisely \mu common neighbors. We will discuss a few ways of modifying a strongly regular graph such that one obtains more strongly regular graphs with the same parameters.

17 April 2023 14:30 till 15:30

[DMO] David Conlon: Sumset estimates in higher dimensions

We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset A of d-dimensional space and a linear transformation L, how large is the sumset A + LA?

05 April 2023 14:00 till 15:00

[DMO] Siv Sørensen: Topology reconstruction using time series data in telecommunication networks

We consider Hybrid fiber-coaxial (HFC) networks in which data is transmitted from a root node to a set of customers using a series of splitters and coaxial cable lines that make up a general (non-binary) tree. The physical locations of the components in a HFC network are always known but frequently the cabling is not. This makes cable faults difficult to locate and resolve. In this study we consider time series data received by customer modems, to reconstruct the topology of HFC networks. We assume that the data can be translated into a series of events, and that two customers sharing many connections in the network will observe many similar events. This approach allows us to use maximum parsimony to minimize the total number of character-state changes in a tree based on observations in the leaf nodes. Furthermore, we assume that nodes located physically close to each other have a larger probability of being connected. Hence, our objective is a weighted sum of data distance and physical distance. A variable-neighborhood search heuristic is presented for minimizing the combined distance. Furthermore, three greedy heuristics are proposed for finding an initial solution. Computational results are reported for both real-life and synthetic customer data with various degrees of background noise, showing that we are able to reconstruct the topology with a very high precision.

22 March 2023 14:00 till 15:00

[DMO] Barbara Terhal & Maarten Stroeks: Fermionic Optimization

A basic problem in physics is to determine the lowest eigenvalue, or `ground state energy', of a many-body Hamiltonian. For fermionic Hamiltonians, modeling electrons in solids or chemistry, this problem is the minimization of a low-degree polynomial in non-commutative Majorana variables (forming a Clifford algebra). Since determining the lowest eigenvalue is a (QMA)-hard problem, it has been of interest to upper and lower bound the eigenvalue by optimizing over simple classes of states resp. relaxing the problem to a SDP.

We prove that for sparse fermionic Hamiltonians the upperbound over so-called Gaussian fermionic states, a well-known efficiently described class of quantum states, achieves a constant approximation ratio, meaning that the scaling with the number of variables is the same as for the true lowest eigenvalue. This is in contrast to recent work showing that for a class of random dense fermionic Hamiltonians, with high probability, there is no constant approximation ratio. We discuss some further results and open questions in this area.

References: 1. Herasymenko, Stroeks, Helsen, Terhal, https://arxiv.org/abs/2211.16518 ; 2. Hastings, O'Donnell, https://dl.acm.org/doi/10.1145/3519935.3519960

15 March 2023 14:00 till 15:00

[DMO] Christopher Hojny: A Unified Framework for Symmetry Handling

Handling symmetries in optimization problems is essential for devising efficient solution methods. In this presentation, I present a general framework that captures many of the already existing symmetry handling methods (SHMs). While these SHMs are mostly discussed independently from each other, our framework allows to apply different SHMs simultaneously and thus outperforming their individual effect. Moreover, most existing SHMs only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art SHMs implemented in the solver SCIP. This is joint work with Jasper van Doornmalen.

08 March 2023 14:00 till 15:00

[DMO] Nils Van de Berg: Using slice rank for lower bounds on fast matrix multiplication

The exponent of matrix multiplication is an open problem in theoretical computer science. Since the initial development by Strassen it has been known that the complexity of multiplying two n by n matrices is somewhere between O(n^2) and O(n^3). Advances on the upper bound have brought the exponent down to 2.372. It is widely conjectured that the complexity is O(n^2) and indeed no better lower bounds have been found. However development of upper bounds has focussed on certain methods and it is possible to find lower bounds on these methods. In 2019 Alman showed that a general type of method could not obtain a better bound than 2.168. For this he used the slice rank, a notion defined by Tao based on work by Ellenberg and Gijswijt. For my master thesis I have studied his paper and the slice rank. I wish to present the ideas in this paper and some of my small own advancements.

03 March 2023 14:00 till 15:00

[DMO] Giulia Montagna: Equiangular lines with a fixed angle

A set of lines through the origin in R^d is called equiangular when any two lines from the set share the same angle. Let N_α(d) denote the maximum number of lines through the origin in R^d with pairwise common angle arccos α. A few years ago Jiang, Tidor, Yao, Zhang and Zhao solved the problem of determining N_α(d) in large enough dimensions. Their result is as follows. Let k denote the minimum number of vertices in a graph whose adjacency matrix has spectral radius exactly (1−α)/(2α). If k exists, then N_α(d) = ⌊k(d-1)/(k-1)⌋ for all sufficiently large d. Otherwise, N_α(d) = d + o(d). In this talk I will present the proof of this result.

17 February 2023 14:00 till 15:00

[DMO] Davi Castro-Silva: Noisy decoding and equidistribution of polynomial maps

A problem from theoretical computer science posed by Buhrman asks to show that a certain class of circuits (NC0[+]) is bad at decoding error-correcting codes under random noise. (This would be in contrast with an analogous class of quantum circuits.) These circuits can be modeled by constant-degree polynomial maps, which turns out to make the problem amenable to a structure-versus-randomness analysis based on a new notion of rank for polynomial maps.

In this talk I will aim to discuss a solution to Buhrman's problem along these lines as well as connections with other notions of rank for polynomials and tensors.

Based on joint work with Jop Briët.

Share this page: