Description
Leader of the group Networks and Optimization: Guido Schäfer.
By combining techniques from mathematics and computer science, we develop algorithmic methods to tackle complex optimization problems. Our research provides efficient solutions to some of the world’s most challenging problems, for example in planning, scheduling and routing.
Vacancies
Postdoc in the research project "Approximation Algorithms, Quantum Information and Semidefinite Optimization"
The research project “Approximation algorithms, quantum information and semidefinite optimization” aims to explore the limits of efficient computation within classical and quantum computing, using semidefinite optimization as a main unifying tool. The position involves research into the mathematical and computer science aspects of approximation algorithms for discrete optimization, quantum entanglement in communication, and complexity of fundamental problems in classical and quantum computing. More information about the project can be found at this website.
Postdoc on the subject of Network Games with Combinatorial Structures
The goal of this project is to study the computation and inefficiency of equilibria in strategic games on networks. One key aspect is to identify combinatorial structures that allow for the efficient computation of equilibria with provable inefficiency guarantees. Another key aspect is to investigate the potential of exploiting combinatorial structures to develop coordination mechanisms that reduce the inefficiency caused by selfish behavior.
PhD Student on the subject of High Dimensional Geometric Algorithms
The student will conduct research on the subject of High Dimensional Geometric Algorithms, present the fruits of this research at top conferences and publish them in quality peerreviewed journals of the field, culminating in a PhD thesis to be defended in public.
News
Monique Laurent elected as Fellow of SIAM
CWI researcher Monique Laurent is elected as a Fellow of the international Society for Industrial and Applied Mathematics – SIAM. This prestigious Fellowship honours SIAM members who have made outstanding contributions to these fields. Laurent, who is a member of the management team of CWI and a professor at Tilburg University, receives the fellowship for her contributions to discrete and polynomial optimization and revealing interactions between them.
Rubicon grants for David de Laat and Alessandro Zocca
CWI researchers David de Laat and Alessandro Zocca both received an NWO Rubicon grant. De Laat will study new techniques to compute optimal packings at MIT for one year, and Zocca will study renewables and uncertainty in future power systems at Caltech for two years. NWO granted these subsidies to 22 young, highly promising research talents to gain international research experience at foreign top institutes.
Better ranking for big data using seriation solution
The recent availability of large data sets leads to the challenge of identifying patterns and structures in them. These patterns can be deployed to improve the user experience
Quantum entanglement can make communications more efficient
Entanglement – a quantum mechanical correlation between particles that can exist even over long distances – might be used for future ways of communication.
Events
N&O Lecture: Dion Gijswijt (Delft)
 20160609T11:00:00+02:00
 20160609T12:00:00+02:00
N&O Lecture: Dion Gijswijt (Delft)
Start: 20160609 11:00:00+02:00 End: 20160609 12:00:00+02:00
Everyons who is interested is welcome to attend the lecture of Dion Gijswijt, with the title 'Asymptotic upper bounds on progressionfree sets in Z_p^n'.
Abstract:
We show that any subset of Z_p^n (p an odd prime) without 3term arithmetic progression
has size O(p^{cn}), where c := 1 − 1/(18 log p) < 1. In particular, we find an upper bound of
O(2.84^n) on the maximum size of an affine cap in GF(3)^n.
N&O Lecture: Gustavo Angulo (Pontificia Universidad Católica de Chile)
 20160608T09:00:00+02:00
 20160608T10:00:00+02:00
N&O Lecture: Gustavo Angulo (Pontificia Universidad Católica de Chile)
Start: 20160608 09:00:00+02:00 End: 20160608 10:00:00+02:00
Everyone who is interested is welcome to attend the lecture of Gustavo Angulo, entitled 'On a class of Stochastic Programs with Exponentially many Scenarios'.
Abstract:
In stochastic programming, it is usually assumed that the random data of
the problem follows a known distribution P. When P is either continuous or
finite with a large number of atoms, sampling methods can be used to
approximate the true problem with a model involving a reasonable number of
scenarios. But what happens when P is ``easy'' to describe and still
involves an enormous number of possible outcomes? A natural question to ask
is whether we can solve the true problem without relying on sampling.
In this work, we propose a model where scenarios are affinely parametrized
by the vertices or integral vectors within a given polytope Q. For
instance, with Q being the ndimensional unit cube, a vertex is a binary
vector that might represent the availability of a set of resources in a
particular scenario. Given that in general the number of vertices is
exponential with respect to the size of the description of Q, a natural
integer programming formulation that includes binary variables to choose
which scenarios are satisfied is simply impractical. For this reason, we
present a formulation that implicitly discards the k worst scenarios for a
given vector x without including variables for each scenario, leading to a
mixedbinary program of moderate size. We also study a model where the
average cost of the k worst scenarios is considered, for which we present a
compact linear formulation. These models can be interpreted in the context
of VaR and CVaRconstrained problems, respectively, exhibiting similar
relationships. A key tool we exploit is a dynamic program to optimize a
linear function over a set of integral matrices with lexicographically
ordered rows, which might be of independent interest.
This is joint work with Mathieu Van Vyve.
N&O lecture: Aleksandar Nikolov (Toronto)
 20160511T09:00:00+02:00
 20160511T10:00:00+02:00
N&O lecture: Aleksandar Nikolov (Toronto)
Start: 20160511 09:00:00+02:00 End: 20160511 10:00:00+02:00
If you are interested you are most welcome to attend this N&O lecture. The title is: Maximizing Determinants under Partition Constraints
Abstract: Given a positive semidefinte matrix L whose columns and rows are indexed by a set U, and a partition matroid M=(U,I), we study the problem of selecting a basis B of M such that the determinant of submatrix of L, restricted to rows and columns of B, is maximized. This type of problem appears in diverse areas including determinantal point processes in machine learning, experimental design, geographical placement problem, discrepancy theory and computational geometry. Our main result is to give a geometric concave program for the problem which approximates the optimum value within a factor of exp(r + o(r)), where r denotes the rank of the partition matroid M.
We bound the integrality gap of the geometric concave program by giving a polynomial time randomized rounding algorithm. To analyze the rounding algorithm, we relate the solution of our algorithm as well the objective value of the relaxation to a certain stable polynomial. To prove the approximation guarantee, we utilize a general inequality about stable polynomials proved by Gurvits in the context of estimating the permanent of a doubly stochastic matrix.
Joint work with Mohit Singh
Members of Networks and Optimization
Publications

Laurent, M, & Tanigawa, S.I. (2017). Perfect elimination orderings for symmetric matrices.

de Klerk, E, Lasserre, J.B, Laurent, M, & Sun, Z. (2017). Boundconstrained polynomial optimization using only elementary calculations. Mathematics of Operations Research.

de Klerk, E, & Laurent, M. (2017). Comparison of Lasserre's measurebased bounds for polynomial optimization to bounds obtained by simulated annealing.

de Klerk, E, Laurent, M, Sun, Z, & Vera, J.C. (2017). On the convergence rate of grid search for polynomial optimization over the simplex. Optimization Letters, 11(3), 597–608. doi:10.1007/s1159001610237

de Klerk, E, Laurent, M, & Sun, Z. (2017). Convergence analysis for Lasserre’s measurebased hierarchy of upper bounds for polynomial optimization. Mathematical Programming, 162(1), 363–392. doi:10.1007/s1010701610431

Gribling, S.J, de Laat, D, & Laurent, M. (2017). Matrices with high completely positive semidefinite rank. Linear Algebra and Its Applications, 513, 122–148. doi:10.1016/j.laa.2016.10.015

Burgdorf, S, Laurent, M, & Piovesan, T. (2017). On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. Electronic Journal of Linear Algebra, 32, 15–40. doi:10.13001/10813810.3201

Dadush, D.N, & Regev, O. (2016). Towards Strong Reverse MinkowskiType Inequalities for Lattices. In Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 447–456). doi:10.1109/FOCS.2016.55

Seminaroti, M. (2016, December 2). Combinatorial algorithms for the seriation problem.

Apt, K.R, de Keijzer, B, Rahn, M.M, Schäfer, G, & Simon, S.E. (2016). Coordination games on graphs. International Journal of Game Theory. doi:10.1007/s0018201605608
Current Projects

New Frontiers in Lattice Algorithms and Design

Optimalisatie van planningsvraagstukken in de touringcarsector

Verbeteren van de efficiency en prestatie van logistieke processen in de binnevaart

Wiskundecluster DIAMANT / Tenure Track positie Daniel Dadush

AQSOApproximation Algorithms, Quantum Information and Semidefinite Optimization

CoMGACombining Machine Learning and Gametheoretic Approaches for Cluster Analysis

ITSLOGReal Time Verkeersdata voor Goederenvervoer (ITSLOG)

NetworksNetworks (eerste fase)

SocialACTSocietal Impact Games
Partners

CTVrede

Rovecom BV

Stanford University

Radboud Universiteit

Technische Universiteit Eindhoven

Universiteit Leiden

Universiteit van Amsterdam

Universiteit van Amsterdam