Events

Events folder

Seminar: Hilde Verbeek (CWI) and Bram Bekker (TU Delft), 2 PhD Talks

 

Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)



Speaker: Hilde Verbeek (CWI)

Title: Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

Abstract:
Sparse suffix sorting is the problem of sorting $b=o(n)$ suffixes of a string of length $n$. Efficient sparse suffix sorting algorithms have existed for more than a decade. Despite the multitude of works and their justified claims for applications in text indexing, the existing algorithms have not been employed by practitioners. Arguably this is because there are no simple, direct, and efficient algorithms for sparse suffix array construction. We provide two new algorithms for constructing the sparse suffix and LCP arrays that are simultaneously simple, direct, small, and fast. In particular, our algorithms are: simple in the sense that they can be implemented using only basic data structures; direct in the sense that the output arrays are not a byproduct of constructing the sparse suffix tree or an LCE data structure; fast in the sense that they run in $O(n \log b)$ time, in the worst case, or in $O(n)$ time, when the total number of suffixes with an LCP value greater than $2^{\lfloor \log \frac{n}{b} \rfloor + 1} − 1$ is in $O(b / \log b)$, matching the time of the optimal yet much more complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et al., SODA 2020]; and small in the sense that they can be implemented using only $8b + o(b)$ machine words. Our algorithms are simplified, yet non-trivial, space-efficient adaptations of the Monte Carlo algorithm by I et al. for constructing the sparse suffix tree in $O(n \log b)$ time [STACS 2014]. We also provide proof-of-concept experiments to justify our claims on simplicity and efficiency.

Based on https://arxiv.org/abs/2310.09023.

 

Video:

Slides:

 

 

Speaker: Bram Bekker (TU Delft)

Title: SDP hierarchies for distance-avoiding sets on compact spaces

Abstract:
Witsenhausen's problem asks for the maximum fraction α_n of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. We extended well known optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, to Witsenhausen's problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds known for αn in low dimensions.

Based on https://arxiv.org/abs/2304.05429.

 

Video:

Slides:

 

 

 

Seminar: Stefanie Jegelka (MIT)


Zoom link:
 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

 

Speaker: Stefanie Jegelka (MIT)

Title: Machine Learning for discrete optimization: Graph Neural Networks, generalization under shifts, and loss functions

Abstract:
Graph Neural Networks (GNNs) have become a popular tool for learning algorithmic tasks, in particular related to combinatorial optimization. In this talk, we will focus on the “algorithmic reasoning” task of learning a full algorithm. Instead of competing on empirical benchmarks, we will aim to get a better understanding of the model's behavior and generalization properties, i.e., the performance on hold-out data, which is an important question in learning-supported optimization too.
We will try to understand in particular out-of-distribution generalization in widely used message passing GNNs, with an eye on applications in learning for optimization: what may be an appropriate metric for measuring shift in the data? Under what conditions will a GNN generalize to larger graphs?
In the last part of the talk, we will take a brief look at objective (loss) functions for learning with discrete objects, beyond GNNs. 

This talk is based on joint work with Ching-Yao Chuang, Keyulu Xu, Joshua Robinson, Nikos Karalias, Jingling Li, Mozhi Zhang, Simon S. Du, Kenichi Kawarabayashi and Andreas Loukas.

Video:

 

Slides:

Seminar: Pedro Zattoni Scroccaro (TU Delft) and Luis Vargas (CWI), 2 PhD-talks

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)



Speaker: Pedro Zattoni Scroccaro (TU Delft) 

Title: Learning Drivers’ Preferences: an Inverse Optimization Approach

Abstract:
In Inverse Optimization problems, a learning agent aims to learn how to mimic the behavior of an expert agent, which given an exogenous signal, returns an action. The underlying assumption is that in order to compute its action, the expert agent solves an optimization problem parametric in the exogenous signal. Therefore, given examples of exogenous signals and corresponding expert actions, the goal of the learner is to learn the cost function being optimized by the expert. In this talk, we will present fundamental concepts of Inverse Optimization, novel results, as well as an application on learning to route vehicles like expert human drivers (Amazon Last Mile Routing Research Challenge). Accompanying papers: https://arxiv.org/abs/2305.07730 and https://arxiv.org/abs/2307.07357.

Video:


Slides:
Slides

 

 

 

Speaker: Luis Vargas (CWI)

Title: Complexity Results About the Exactness of Sum-of-Squares Approximations for Polynomial Optimization

Abstract:
A polynomial optimization problem (PoP) asks for minimizing a polynomial function over a semialgebraic set i.e., a set defined by
polynomial inequalities and equations. Polynomial optimization captures many hard problems and it is difficult to solve as expected. The Lasserre sum-of-squares hierarchy is a sequence of tractable approximations for (PoP). Under mild assumptions, this hierarchy is shown to converge asymptotically to the optimal value of (PoP). In this talk, we study the question of whether the Lasserre sum-of-squares hierarchy has finite convergence to the optimal value.  Nie (2012) shows that if the problem has finitely many minimizers and they satisfy the classical optimality conditions, then finite convergence holds. Using this, he shows that finite convergence holds generically. In this talk, we show that 1) testing whether a standard quadratic program has finitely many minimizers is NP-hard. Moreover, 2) testing whether the Lasserre hierarchy of a polynomial optimization problem has finite convergence is NP-hard.

Video:


Slides:
Slides

 

 

Seminar: Leo van Iersel (TU Delft)

Speaker: Leo van Iersel (TU Delft)

Title:

Embedding phylogenetic trees in networks of low treewidth

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2^{O(t^2)}⋅|N| time and space.
 
Slides:

Seminar: Danish Kashaev (CWI) and Arash Pourdamghani (TU Berlin), 2 PhD-talks

Speaker: Danish Kashaev (CWI) and Arash Pourdamghani (TU Berlin) 

Title:

Danish Kashaev: Round and Bipartize for Vertex Cover Approximation

Arash Pourdamghani: SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree

 

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

 

Abstract of "Round and Bipartize for Vertex Cover Approximation" (Danish Kashaev):
The vertex cover problem is a fundamental and widely studied NP-Hard combinatorial optimization problem. It is known that its standard linear programming relaxation is integral for bipartite graphs and half-integral for general graphs. As a consequence, the natural rounding algorithm based on this relaxation computes an optimal solution for bipartite graphs and a 2-approximation for general graphs. This 2-approximation cannot be improved in the worst-case if the unique games conjecture is true.

In this talk, we present a simple rounding algorithm based on the standard relaxation which has additional access to an odd cycle transversal (i.e. a set of vertices whose removal leaves the graph bipartite) and analyze its approximation guarantee. The motivation for studying this setting comes from an interest in interpolating the rounding curve of the standard LP in a beyond the worst-case manner, depending on how close the graph is to being bipartite. A key parameter determining tight bounds on the approximation ratio turns out to be the odd girth of the graph, defined as the length of the shortest odd cycle. We also show optimality of the analysis and discuss algorithmic applications in order to find good odd cycle transversals.

Based on https://arxiv.org/abs/2211.01699.

Video of the talk of Danish Kashaev: 

Slides of the talk of Danish Kashaev:
Slides

 

Abstract of "SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree" (Arash Pourdamghani):
The vision of developing self-adjusting networks is now a reality: programmable optical networking switches are already being used
in big tech companies such as Google and Microsoft. However, theoretical foundations are lagging behind in this area: previous methods have been designed by having fixed and limited networking resources in mind. In this talk, I first describe how we can go from self-adjusting trees to self-adjusting networks, and then focus on the new model that we are proposing that has two key differences from traditional self-adjusting trees: it allows for capacities higher than one per node, and it uses item movements instead of rotation. Given this novel model, I detail how to design a randomized constant competitive algorithm that also allows for greedy local routing. Hence the cost of our algorithm is asymptotically optimal given any input demand while ensuring local adjustments and routing.

Based on https://arxiv.org/pdf/2301.03074.

Video of the talk of Arash Pourdamghani:

Slides of the talk of Arash Pourdamghani:  
Slides

 

Seminar: Anupam Gupta (Carnegie Mellon University)

Speaker: Anupam Gupta (Carnegie Mellon University)

Title:

Two (More) Algorithms for Set Cover

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

In the minimum cost set cover problem, a set system is given as input, and
the goal is to find a collection of sets with minimum cost whose union
covers the universe. This NP-hard problem has long been known to admit
logarithmic approximations. Moreover, the logarithmic guarantee is tight,
unless P=NP. In this talk I will present two new algorithms which also get
logarithmic guarantees. These algorithms came out of attempts to get
refined guarantees for set cover in beyond-worst-case settings.

The talk is based on joint works with Greg Kehne (CMU and Harvard),
Euiwoong Lee (U. Michigan), Roie Levin (CMU and Tel Aviv U), and Jason Li
(CMU and Simons/Berkeley).

Video:
 
Slides:

Intercity Seminar

  • When May 04, 2023 from 02:30 PM to 05:00 PM (Europe/Amsterdam / UTC200)
  • Where Room L017 at CWI
  • Contact Name
  • Add event to calendar iCal

Schedule:

2:30pm - 3:30pm: Distributed, Parallel and Dynamic Graph Algorithms (Yasamin Nazari, Vrije Universiteit Amsterdam)

3:30pm - 4:00pm: Coffee Break

4:00pm - 5:00pm: An approximate solution to a 2,079,471-point traveling salesman problem (William Cook, University of Waterloo)


Registration:

As space is limited, please register using the following google form by Friday, 28 April:
https://forms.gle/n4ZPLzkuFxChPWwz7


Livestream Zoom Link:
 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448) 


Speaker: Yasamin Nazari
(Vrije Universiteit Amsterdam)

Title: Distributed, Parallel and Dynamic Graph Algorithms

Abstract:

In recent years, there has been a growing interest in designing
algorithms in models that capture different aspects of modern computational
systems and big data processing. This talk focuses on graph algorithms in
several such models, such as distributed, dynamic and parallel models.

We will focus on the task of graph distance computation in these models and
introduce several graph theoretic structures that preserve
approximate distances, but tradeoff this approximation factor with size,
query time, or the number of hops on the approximate shortest paths. We
then show how these combinatorial structures can be utilized for
faster distance computation in distributed or dynamic settings.

Finally, we discuss several open problems including possible connections
with combinatorial optimization.
 
Video:
 
Slides
Slides

 


Speaker: William Cook 
(University of Waterloo)

Title: An approximate solution to a 2,079,471-point traveling salesman problem

Abstract:

Together with Keld Helsguan, we have found a TSP tour through the 3D positions
of 2,079,471 stars. We discuss how linear programming allows us to prove the
tour is at most a factor of 0.0000074 longer than an optimal solution. The talk
will focus on the use of GF(2) linear systems to drive the cutting-plane method
towards improved LP relaxations of the TSP.

Video:



Seminar: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e), 2 PhD-talks

Speaker: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e) 

Title:

Harold Nieuwboer: Interior-point methods on manifolds

Lucy Verberk: Stabilization of capacitated matching games

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Interior-point methods on manifolds" (Harold Nieuwboer):
Interior-point methods offer a highly versatile framework for convex
optimization that is effective in theory and practice. A key notion in
their theory is that of a self-concordant barrier. We give a suitable
generalization of self-concordance to Riemannian manifolds and show that
it gives the same structural results and guarantees as in the Euclidean
setting, in particular local quadratic convergence of Newton's method.
We then analyze a short-step path-following method for optimizing
compatible objectives over a convex domain for which one has a
self-concordant barrier, and obtain the standard complexity guarantees
as in the Euclidean setting. We show that on the positive-definite
matrices and other symmetric spaces, the squared distance to a point is
a self-concordant function. Our work is motivated by recent progress on
scaling problems and non-commutative optimization, and we show that
these fit into our framework, yielding algorithms with state-of-the-art
complexity guarantees. Furthermore, we show how to apply our methods to
computing geometric medians on spaces with constant negative curvature.

Joint work with Michael Walter. Based on https://arxiv.org/abs/2303.04771.

Video of the talk of Harold Nieuwboer: 

Slides of the talk of Harold Nieuwboer:

Slides

Abstract of "Stabilization of capacitated matching games" (Lucy Verberk):
An edge-weighted, vertex-capacitated graph G is called stable if the
value of a maximum-weight capacity-matching equals the value of a
maximum-weight fractional capacity-matching. Stable graphs play a key
role in characterizing the existence of stable solutions for popular
combinatorial games that involve the structure of matchings in graphs,
such as network bargaining games and cooperative matching games.

The vertex-stabilizer problem asks to compute a minimum number of
players to block (i.e., vertices of G to remove) in order to ensure
stability for such games. The problem has been shown to be solvable in
polynomial-time, for unit-capacity graphs. This stays true also if we
impose the restriction that the set of players to block must not
intersect with a given specified maximum matching of G.

We investigate these algorithmic problems in the more general setting of
arbitrary capacities. We show that the vertex-stabilizer problem with
the additional restriction of avoiding a given maximum matching remains
polynomial-time solvable. Differently, without this restriction, the
vertex-stabilizer problem becomes NP-hard and even hard to approximate,
in contrast to the unit-capacity case.

Finally, in unit-capacity graphs there is an equivalence between the
stability of a graph, existence of a stable solution for network
bargaining games, and existence of a stable solution for cooperative
matching games. We show that this equivalence does not extend to the
capacitated case.

Joint work with Matthew Gerstbrein and Laura Sanità. Based on
https://arxiv.org/abs/2211.12179.

Video of the talk of Lucy Verberk:

Slides of the talk of Lucy Verberk:  
Slides

 

Seminar: Christopher Hojny (TU/e)

Speaker: Christopher Hojny (TU/e)

Title:

Relaxation Complexity: Algorithmic Possibilities and Limitations

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Let X be the integer points contained in a polytope. The relaxation
complexity rc(X) is the smallest number of facets of any polyhedron P
such that the integer points in P coincide with X. It is a useful tool
to investigate the existence of compact linear descriptions of X. In
particular, it provides the minimum number of inequalities needed in any
integer programming formulation of X. Moreover, when restricting the
polyhedra P to be rational, rc_Q(X) denotes the corresponding rational
relaxation complexity of X.

In this presentation, I discuss several algorithmic aspects of finding
the relaxation complexity. First, a natural question is whether rc(X) is
actually computable. While this question is notoriously open in general,
I present an algorithm that finds rc(X) in dimension 2. Second, rc_Q(X)
is an upper bound on rc(X). A natural idea is thus to provide computable
lower bounds on rc(X) and computable upper bounds on rc_Q(X). If these
bounds match, rc(X) and rc_Q(X) have been found. I show that we can
indeed find a matching upper bound on rc_Q(X), whereas I discuss why
finding a matching lower bound for rc(X) seems to be more challenging.
Finally, the previously sketched idea only allows to compute rc(X) and
rc_Q(X) if both quantities coincide. I conclude this presentation by a
brief outline that rc(X) can be strictly smaller than rc_Q(X).

Video:


Slides
Slides

Seminar: Jannik Matuschke (KU Leuven)

Speaker: Jannik Matuschke (KU Leuven)

Title:

Decomposition of Probability Marginals for Security Games in Abstract Networks

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Consider a set system on a finite ground set E, where each set P in the
system is equipped with a required hitting probability r(P) and each
element e of E has a probability marginal p(e). We study the question
whether the marginals can be decomposed into a distribution over all
subsets of E such that the resulting random set intersects each set P from
the system with probability at least r(P). A simple necessary condition is
that for every set P in the system, the sum of the marginals of elements in
P is at least r(P).

Extending a result by Dahan, Amin, and Jaillet (Mathematics of Operations
Research 47:457-484, 2022) motivated by a security game in a directed
acyclic graph, we show that the aforementioned necessary condition is is
also sufficient in the following two settings: (i) the set system fulfills
a max-flow/min-cut property and the requirements are affine; (ii) the set
system is an abstract network and the requirements fulfill a weak
conservation law. We provide algorithms for the computation of the
corresponding decompositions and, in some cases, simple explicit
descriptions of these decompositions. As a subroutine, we also devise a
combinatorial algorithm for computing shortest paths in abstract networks,
answering an open question by McCormick (SODA 1996). A consequence of our
results is that equilibria for the security game studied by Dahan et al.
(2022) and similar games involving randomized surveillance strategies can
be computed efficiently, even when the underlying digraph contains cycles.

Video:


Slides
Slides

Seminar: Jack Mayo (University of Amsterdam) and Isja Mannens (Utrecht University), 2 PhD talks

Speaker: Jack Mayo (Universiteit van Amsterdam) and Isja Mannens (Universiteit Utrecht), 2 PhD talks

Title:

Jack Mayo: Scale-free Unconstrained Online Learning for Curved Losses

Isja Mannens: The parameterized complexity of the Tutte polynomial

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Scale-free Unconstrained Online Learning for Curved Losses" (Jack Mayo):
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm U of the comparator and the maximum norm G of the gradients. In full generality, matching upper and lower bounds are known which show that this comes at the unavoidable cost of an additive GU^3, which is not needed when either G or U is known in advance. Surprisingly, recent results by Kempka et al. (2019) show that no such price for adaptivity is needed in the specific case of 1-Lipschitz losses like the hinge loss. We follow up on this observation by showing that there is in fact never a price to pay for adaptivity if we specialise to any of the other common supervised online learning losses: our results cover log loss, (linear and non-parametric) logistic regression, square loss prediction, and (linear and non-parametric) least-squares regression. We also fill in several gaps in the literature by providing matching lower bounds with an e!
 xplicit dependence on U. In all cases we obtain scale-free algorithms, which are suitably invariant under rescaling of the data. Our general goal is to establish achievable rates without concern for computational efficiency, but for linear logistic regression we also provide an adaptive method that is as efficient as the recent non-adaptive algorithm by Agarwal et al. (2021).

Video of the talk of Jack Mayo:

Slides of the talk of Jack Mayo:  
Slides

Abstract of "The parameterized complexity of the Tutte polynomial" (Isja Mannens):
The Tutte polynomial has been widely studied in various areas of mathematics and theoretical computer science. One of these areas is computational complexity. A classic result is that of Jaeger, Vertigan and Welsh, who give a complete dichotomy for the complexity of evaluating the Tutte polynomial at a given point. With recent developments in the field of parameterized complexity in mind, one might ask what such a dichotomy would look like with respect to certain graph parameters.
In this talk we will discuss unpublished work that seeks to answer this question for the parameters of treewidth, pathwidth and cutwidth. We will discuss parallels with the techniques of Jaeger, Vertigan and Welsh and how they can be adapted to this setting. Using this approach, in conjunction with existing hardness results, we find asymptotically tight bounds for all points on so called special curves H_q, for any integer valued q.
In addition, we will discuss a novel rank-based algorithm for the problem of counting forests, a specific evaluation of the Tutte polynomial. This algorithm runs in O(64^tw) time which results in a surprising asymmetry in the complexity of computing the Tutte polynomial, along the lines 'y=1' and 'x=1'. The former can be reduced to counting forests, while the latter is not solvable in O(ctw^{o(ctw)}) time under ETH.

Video of the talk of Isja Mannens: 

Slides of the talk of Isja Mannens:
Slides

Seminar: Carla Groenland (Utrecht University)

Speaker: Carla Groenland (Utrecht University)

Title:

List Colouring Trees in Logspace

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

A List Colouring instance consists of a graph and for each vertex v in the graph, a list L(v) of colours that it may be coloured with. I will explain some ideas behind our algorithm that decides whether an n-vertex tree admits a list colouring using O(log n) bits of work tape. I will also outline some exciting new parameterized complexity classes that can be described via List Colouring on other classes of graphs (XNLP, XALP, …) via graph width measures (pathwidth, treewidth, …).
This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.

Video:


Slides

Slides

Dutch Day of Optimization

  • When Oct 13, 2022 (Europe/Amsterdam / UTC200)
  • Where Amsterdam Science Park Congress Center, Science Park 125, 1098 XG Amsterdam
  • Contact Name
  • Web Visit external website
  • Add event to calendar iCal

On Thursday October 13, the Dutch Day of Optimization will take place; see this webpage

The Dutch Day on Optimization is the yearly in-person event related to the Dutch Seminar on Optimization. The main purpose of the event is to bring together the Dutch Optimization community across the areas of operations research, computer science and discrete mathematics. The event will highlight the research of both national and international speakers. The lectures will take place in the Turing Room in the Amsterdam Science Park Congress Center.

Seminar: Jesse van Rhijn (Universiteit Twente) and Sander Borst (CWI), 2 PhD talks

Speaker: Jesse van Rhijn (Universiteit Twente) and Sander Borst (Centrum Wiskunde & Informatica)

Title:

Jesse van Rhijn: Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP

Sander Borst: Selection in explorable heaps

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP" (Jesse van Rhijn):
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Hajek explores members of the solution set which are in expectation far from the global optimum. We obtain a lower bound on the expected length of the final tour obtained by SA on these random instances. In addition, we also obtain an upper bound on the expected value of its variance. These bounds assume that the Markov chain that describes SA is stationary, a situation that does not truly hold in practice. Hence, we also formulate conditions under which the bounds extend to the nonstationary case. These bounds are obtained by comparing the tour length distribution to a related distribution. We furthermore provide numerical evidence for a stochastic dominance relation that appears to exist between these two distributions, and formulate a conjecture in this direction. If proved, this conjecture implies that SA stays far from the global optimum with high probability when executed for any sub-exponential number of iterations. This would show that SA requires at least exponentially many iterations to reach a global optimum with nonvanishing probability.

Video of the talk of Jesse van Rhijn:

Slides of the talk of Jesse van Rhijn:  
Slides

Abstract of "Selection in explorable heaps" (Sander Borst):
Explorable heap selection is the problem of selecting the nth smallest value in a binary heap, where the values can only be accessed by traversing the binary tree. In this setting we want to minimize the distance traveled in the tree. The problem is related to the node selection problem for the branch-and-bound algorithm.
The problem was originally proposed by Karp, Saks and Widgerson (FOCS '86), who also proposed algorithms for this problem. Recently we found a new algorithm, that improves on the running time. In this talk I will explain the problem, our new algorithm and the connection between the problem and branch-and-bound.

Video of the talk of Sander Borst: 

Slides of the talk of Sander Borst:
Slides

Seminar: Ilker Birbil (Universiteit van Amsterdam)

Speaker: Ilker Birbil (Universiteit van Amsterdam)

Title:

Counterfactual Explanations Using Optimization With Constraint Learning

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Counterfactual explanations embody one of the many interpretability techniques that receive increasing attention from the machine learning community. Their potential to make model predictions more sensible to the user is considered to be invaluable. To increase their adoption in practice, several criteria that counterfactual explanations should adhere to have been put forward in the literature. We propose counterfactual explanations using optimization with constraint learning, a generic and flexible approach that addresses all these criteria and allows room for further extensions. Specifically, we discuss how we can leverage an optimization with constraint learning framework for the generation of counterfactual explanations, and how components of this framework readily map to the criteria. We also propose new novel modeling approaches to address data manifold closeness and diversity, which are two key criteria for practical counterfactual explanations. We test our approaches on several datasets and present our results in a case study. Compared to a current state-of-the-art method, our modeling approach has shown an overall superior performance in terms of several evaluation metrics proposed in related work while allowing more room for flexibility.

Video:


Slides

Slides

Seminar: Vera Traub (ETH Zürich)

Speaker: Vera Traub (ETH Zürich)

Title:

Better-Than-2 Approximations for Weighted Tree Augmentation and Forest Augmentation

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. In the first part of this talk we present the first algorithm that improves on the longstanding approximation ratio of 2 for WTAP.

In the second part of the talk we show how this algorithm can be used to obtain the first better-than-2 approximation algorithm for the Forest Augmentation Problem. In this problem we want to choose a minimum number of edges, among a given set of options, that we can add to a graph G to make it 2-edge connected. In contrast to the Tree Augmentation Problem, we do not require the given graph G to be connected.

This talk is based on joint works with Fabrizio Grandoni, Afrouz Jabal Ameli, and Rico Zenklusen.

Video:

Slides

Slides

Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks

  • When May 24, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
  • Add event to calendar iCal

Speaker: Jasper van Doornmalen (TU/e) and Daniel Brosch (Tilburg University)

Title:

Jasper van Doornmalen: Symmetry handling in binary programs through propagation

Daniel Brosch : The Symmetries of Flag-Algebras

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Symmetry handling in binary programs through propagation" (Jasper van Doornmalen):
Symmetries of binary programs are known to dramatically slow down branch-and-bound procedures. A classical approach to handle permutation symmetries is to enforce that only one representative of equivalent (symmetric) solutions can be computed. In classical integer programming literature, among others, this is established by introducing symmetry handling constraints. This way, solutions that are not lexicographically maximal among the permuted solutions are cut off.

We present a propagation-based symmetry handling technique. Given a set of fixed variables (e.g., due to branching decisions), this technique identifies further variables that can be fixed to ensure that only lexicographically maximal solutions are computed. We present efficient algorithms to find such additional symmetry-based variable fixings for arbitrary sets of permutations and cyclic groups. In particular, for cyclic groups, we show that all possible fixings can be found in polynomial time even if the cyclic group has exponential order.

Our methods are implemented as a plugin in the academic integer programming solver SCIP, and we discuss the effectiveness of these methods on various symmetrical instances.

Video of the talk of Jasper van Doornmalen:

Slides of the talk of Jasper van Doornmalen:  
Slides

Abstract of "The Symmetries of Flag-Algebras" (Daniel Brosch):
Flag-Algebras, first introduced by Razborov in 2007, remain one of the most powerful tools in extremal combinatorics.  Recently a connection to polynomial optimization was discovered: We can recover Flag-Sums-of-Squares hierarchies by partially exploiting the symmetries of a polynomial optimization hierarchy. We continue from there and fully exploit the symmetries in this polynomial setting for two different hierarchies, one focusing on a low number of edges, and another focusing on a low number of vertices of appearing Flags. For the first, due to the high initial dimension of the hierarchy, a novel algorithm was needed to decompose modules of the symmetric group into irreducible submodules. We apply the reduced hierarchies to obtain outer approximations of graph-profiles, which model various open problems from extremal combinatorics.

Video of the talk of Daniel Brosch:

Slides of the talk of Daniel Brosch:
Link to Daniel's slides on his webpage

 

Seminar: Krzysztof Postek (TU Delft)

Speaker: Krzysztof Postek (TU Delft) 

Title:

An Adaptive Robust Optimization Model for Parallel Machine Scheduling

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Real-life project or machine scheduling involves: (i) limited information about the exact task durations, and (ii) an opportunity to reschedule each time a task completed its processing and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic, yet the existing literature does not consider the possibility to adjust decisions as more information about the tasks' durations is revealed. This is despite that re-optimizing the schedule is a standard practice.

We develop an approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted, allowing an arbitrary set of scenarios for the task lengths' realizations. We demonstrate that this can lead to better here-and-now decisions. In a recent work, we develop an exact MILP formulation of this problem for discrete sets of scenarios, which, to best of our knowledge, is the first one in which so-called nonanticipativity constraints are formulated exactly.

Joint work with Shimrit Shtern (Technion), Izack Cohen (Bar Ilan University), Izak de Heer (TU Delft).

Video:

Slides
Slides

Seminar: Esteban Gabory (CWI) + Donato Maragno (UvA), 2 PhD talks

  • When Mar 31, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
  • Add event to calendar iCal

Speaker: Esteban Gabory (CWI) + Donato Maragno (UvA)

Title:

Esteban Gabory: On Strings Having the Same Length-k Substrings

Donato Maragno : Mixed-Integer Optimization with Constraint Learning

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "On Strings Having the Same Length-k Substrings" (Esteban Gabory):

Let Substr_k(T) denote the set of length-k substrings of a given string T for a given integer k>0. We study the following basic string problem, called Shortest equivalent string: Given a set S_k of n length-k strings and an integer z>0, find a shortest string T such that Substr_k(T)=S_k. The Shortest equivalent string problem arises naturally as an encoding problem in many real-world applications; e.g., in data privacy, in data compression, and in bioinformatics. We answer this problem by showing that it is equivalent to finding a shortest walk that crosses every edge of a graph, and we give an algorithm for the latter problem.
 

Video of the talk of Esteban Gabory:
Slides of the talk of Esteban Gabory:  
Slides

Abstract of "Mixed-Integer Optimization with Constraint Learning" (Donato Maragno):

We establish a broad methodological foundation for mixed-integer optimization with learned constraints. We propose an end-to-end pipeline for data-driven decision making in which constraints and objectives are directly learned from data using machine learning, and the trained models are embedded in an optimization formulation. We exploit the mixed-integer optimization-representability of many machine learning methods, including linear models, decision trees, ensembles, and multi-layer perceptrons. The consideration of multiple methods allows us to capture various underlying relationships between decisions, contextual variables, and outcomes. We also characterize a decision trust region using the convex hull of the observations, to ensure credible recommendations and avoid extrapolation. We efficiently incorporate this representation using column generation and clustering. In combination with domain-driven constraints and objective terms, the embedded models and trust region define a mixed-integer optimization problem for prescription generation. We implement this framework as a Python package (OptiCL) for practitioners. We demonstrate the method in both chemotherapy optimization and World Food Programme planning. The case studies illustrate the benefit of the framework in generating high-quality prescriptions, the value added by the trust region, the incorporation of multiple machine learning methods, and the inclusion of multiple learned constraints.

Joint work with: Holly Wiberg, Dimitris Bertsimas, S. Ilker Birbil, Dick den Hertog, Adejuyigbe Fajemisin

Paper:
https://arxiv.org/abs/2111.04469
Code:
https://github.com/hwiberg/OptiCL
 

Video of the talk of Donato Maragno:
Slides of the talk of Donato Maragno:  
Slides

Seminar: Friedrich Eisenbrand (EPFL Lausanne), International speaker

  • When Mar 03, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
  • Add event to calendar iCal

Speaker: Friedrich Eisenbrand (EPFL Lausanne) 

Title:

Algorithms for Integer Programming

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract:

Integer programming is a very versatile discrete optimisation problem with many applications in science and engineering. From the viewpoint of algorithms and complexity, it is an active area of research that offers interesting and visible open problems.  In this talk, I will survey some recent results on the complexity of integer programming. These include the general integer programming problem in standard form with small coefficients. Here field of parameterised complexity has developed tools to provide lower bounds on the complexity of IP based on the exponential time hypothesis (ETH). The goal of this talk is to give an overview on recent progress and open problems in this area.


Video
:

Slides
Slides