Description
Leader of the group Networks and Optimization: Guido Schäfer.
In today’s society, complex systems surround us. From transport and traffic, to behavioral economics and operations management, realworld applications often demand that we identify simple, optimal solutions among a huge set of possibilities. Our research group Networks and Optimization (N&O) does fundamental research to tackle such challenging optimization problems.
We develop algorithmic methods to solve complex optimization problems efficiently. Our research provides efficient algorithms to some of the most challenging problems, for example, in planning, scheduling and routing. To come up with the best optimization algorithms, we combine and extend techniques from different disciplines in mathematics and computer science.
N&O covers a broad spectrum of optimization aspects. Our expertise ranges from discrete to continuous optimization and applies to centralized and decentralized settings. We focus on both problemspecific methods and universal toolkits to solve different types of optimization problems. The key in our investigations is to understand and exploit combinatorial structures, such as graphs, networks, lattices and matroids. Our research is of high scientific impact and contributes to various fields.
In several cooperations with industry partners, the algorithmic techniques that we develop in our group have proven useful to solve complex realworld problems. We are always interested in new algorithmic challenges arising in realworld applications and are open to new cooperations.
Watch our group video to get a glimpse of our activities.
Vacancies
PhD students on the subject of Towards a Quantitative Theory of Integer Programming
Centrum Wiskunde & Informatica (CWI) has a vacancy in the Networks & Optimization research group for two talented PhD students, on the subject of Towards a Quantitative Theory of Integer Programming.
Postdoc on the subject of Towards a Quantitative Theory of Integer Programming
Centrum Wiskunde & Informatica (CWI) has a vacancy in the Networks & Optimization research group for a talented Postdoc, on the subject of Towards a Quantitative Theory of Integer Programming.
News
CWI researchers in research consortium Gravity programme
Six research consortia in which prominent scientists from various Dutch universities work together are receiving a combined sum of 153 million euros for longterm and largescale research.
Conditions for optimal solutions to semidefinite problems found
Most optimization problems in reallife are hard to solve optimally. However, for practical purposes it is usually sufficient to settle for nearoptimal solutions that can be found quickly. Fast and more accurate approximations can be computed using semidefinite programming, a novel powerful optimization tool
Connection between graph theory and algebra deepened
PhD student Guus Regts from Centrum Wiskunde & Informatica (CWI) investigated mathematical connections between graph theory and algebra.
Current events
N&O seminar: Christopher Hojny (TU Darmstadt)
 20190327T11:00:00+01:00
 20190327T12:00:00+01:00
N&O seminar: Christopher Hojny (TU Darmstadt)
Start: 20190327 11:00:00+01:00 End: 20190327 12:00:00+01:00
Everyone is welcome to attend the public lecture of Christopher Hojny (TU Darmstadt) withe the title 'Strong IP Formulations Need Large Coefficients'.
Abstract:
The development of practically wellbehaving integer programming formulations is an important aspect of solving linear optimization
problems over a set of binary points. In practice, one is often interested in strong integer formulations with additional properties,
e.g., bounded coefficients to avoid numerical instabilities.
To measure the strength of an integer formulation, I introduce the concept of 1/lambdarelaxations. 1/lambdarelaxations generalize
classical integer formulations to refinements of the integer lattice by a factor of 1/lambda. After pointing out how 1/lambdarelaxations arise naturally for the stable set problem, I present a lower bound on the size of coefficients in any 1/lambdarelaxation of a binary set. Using this bound, I show, among others, that strong integer formulations of the stable set problem need, in general, coefficients that grow linearly in the size of the underlying graph. For knapsack problems, I demonstrate that exponentially large coefficients may be necessary in any strong integer formulation. Thus, strong integer formulations need large coefficients in general.
N&O seminar: Adrien Taylor (ENS Paris)
 20190403T11:00:00+02:00
 20190403T12:00:00+02:00
N&O seminar: Adrien Taylor (ENS Paris)
Start: 20190403 11:00:00+02:00 End: 20190403 12:00:00+02:00
Everyone is welcome to attend the N&O lecture of Adrien Taylor (ENS Paris) with the title 'Computeraided worstcase analyses and design of firstorder methods'.
Abstract:
In this presentation, we will provide a highlevel overview of recent approaches for analyzing and designing firstorder methods using symbolic computations and/or semidefinite programming. A particular emphasis will be given to the "performance estimation" approach, which enjoys comfortable tightness guarantees: the approach fails only when the target results are impossible to prove. In particular, it allows obtaining (tight) worstcase guarantees for fixedstep firstorder methods involving a variety of oracles  that includes explicit, projected, proximal, conditional, inexact, or stochastic (sub)gradient steps  and a variety of convergence measures.
The presentation will be examplebased, as the main ingredients necessary for understanding the methodologies are already present in the analysis of the vanilla gradient method. For convincing the audience, we will provide other examples that include novel (100% computergenerated) analyses of the DouglasRachford splitting, and of a variant of the celebrated conjugate gradient method.
The methodology is implemented within the package "PESTO" (for "Performance EStimation TOolbox", available at https://github.com/AdrienTaylor/PerformanceEstimationToolbox), which allows using the framework without any tedious semidefinite programming modelling step.
The talk is based on joint works with great collaborators: François Glineur (UCLouvain), Julien Hendrickx (UCLouvain), Etienne de Klerk (Tilburg/TU Delft), Yoel Drori (Google), Pontus Giselsson (Lund), Carolina Bergeling (Lund), Ernest Ryu (UCLA), Laurent Lessard (WisconsinMadison), Bryan Van Scoy (WisconsinMadison), and Francis Bach (Inria/ENS Paris).
Early bird registration NMC 2019: deadline 31 December 2019
 20190423T09:00:00+02:00
 20190424T18:00:00+02:00
Early bird registration NMC 2019: deadline 31 December 2019
Start: 20190423 09:00:00+02:00 End: 20190424 18:00:00+02:00
On April 2324, 2019, the Dutch Mathematical Congress (NMC 2019) will be held in the Congress Centre Koningshof (located in Veldhoven, close to Eindhoven).
Given the success of the first "NMC new style" earlier this year, we hope that in 2019 there will be even more participants. Once again we have compiled a very attractive programme with the following ingredients:
Plenary lectures by Barbara Gentz, Jan Hesthaven, Gábor Lugosi and Anke van Zuylen
Parallel sessions by the Gravitation programmes Networks and Quantum Software Consortium, and of pairs of clusters inspired by the new topics in the “Sectorplan”
A strategy session on the cluster evaluation and the “Sectorplan”
Speed dates with industry
Poster prize, KWG prize for PhD students, the Stieltjes prize and the new “innovation” prize for MSc students
Social programme with dinner and dance performance based on the ‘spurs of Lehmer’
The "early bird" registration period, giving you a discount of € 50,, ends December 31st, so register now!
You can find more information and a link to the registration form.
With regards,
On behalf of the organising committee,
Evgeny Verbitsky (chair)
Members
Associated Members
Publications

Chen, J.J, Bansal, N, Chakraborty, S, & von der Brüggen, G. (2018). Packing sporadic realtime tasks on identical multiprocessor systems. In 29th International Symposium on Algorithms and Computation (pp. 71:1–71:14). doi:10.4230/LIPIcs.ISAAC.2018.71

Dadush, D.N, Nikolov, A, Talwar, K, & TomczakJaegermann, N. (2018). Balancing vectors in any norm. In Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 1–10). doi:10.1109/FOCS.2018.00010

Carvalho Rodrigues, F, Schäfer, G, & Xavier, E.C. (2018). On the effectiveness of connection tolls in fair cost facility location games. In Proceedings of the 19th Italian Conference on Theoretical Computer Science (pp. 36–47).

van Heuven van Staereling, I.I. (2018). Tree decomposition methods for the periodic event scheduling problem. In OpenAccess Series in Informatics. doi:10.4230/OASIcs.ATMOS.2018.6

Carstens, C.J, & Kleer, P.S. (2018). Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) (pp. 36:1–36:18). doi:10.4230/LIPIcs.APPROXRANDOM.2018.36

Amanatidis, G, Birmpas, G, & Markakis, V. (2018). Comparing approximate relaxations of envyfreeness. In IJCAI International Joint Conference on Artificial Intelligence (pp. 42–48).

Dadush, D.N, & Huiberts, S. (2018). A friendly smoothed analysis of the simplex method. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 214–227). doi:10.1145/3188745.3188826

Bansal, N, Dadush, D.N, Garg, S, & Lovett, S. (2018). The GramSchmidt Walk: A Cure for the Banaszczyk Blues. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 (pp. 587–597). doi:10.1145/3188745.3188850

Kamphorst, B. (2018, May 31). Heavytraffic behaviour of scheduling policies in queues.

Apt, K.R, & Wojtczak, D.K. (2018). Verification of distributed epistemic gossip protocols. Journal of Artificial Intelligence Research, 62, 101–132.
Current projects with external funding

Continuous Methods in Discrete Optimization

Smart Heuristic Problem Optimization

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

Wiskundecluster DIAMANT

Approximation Algorithms, Quantum Information and Semidefinite Optimization (AQSO)

MixedInteger NonLinear Optimisation Applications (MINOA)

Polynomial Optimization, Efficiency through Moments and Algebra (POEMA)

Vóórkomen en voorkómen van incidenten op het spoor (PPS Prorail)

Towards a Quantitative Theory of Integer Programming (QIP)
Related partners

Alma Mater StudiorumUniversita di Bologna

AlpenAdriaUniversität Klagenfurt

CNR Pisa

CNRS

CTVrede

Dassault Systèmes B.V.

IBM

INRIA

Prorail

Rheinische FriedrichWilhelmus Universitaet Bonn

Technische Universität Dortmund

Tilburg University

Tromsø, Norway

Universita degli Studi di Firenze

Universität Konstanz

University of Birmingham