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, real-world 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 problem-specific 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 real-world problems. We are always interested in new algorithmic challenges arising in real-world applications and are open to new cooperations.

Watch our group video to get a glimpse of our activities.

Video about our collaboration with ProRail (in Dutch)

Vacancies

No vacancies currently.

CWI co-organizes international trimester program at Bonn University

Together with TU/e, UU and LSE London, CWI is co-organizing an international trimester program on Discrete Optimization at the Hausdorff Research Institute for Mathematics (HIM) in Bonn. Goal of this research community service is to collaborate and make progress on long-standing open problems.

Monique Laurent elected as EUROPT Fellow 2021

Monique Laurent, researcher and management team member at CWI and a professor at Tilburg University, was recently elected as EUROPT Fellow 2021. She was honoured for being an outstanding researcher in continuous optimization.

Strong Contribution of Networks and Optimization at IPCO 2021

Research carried out by CWI's Networks and Optimization (N&O) group has resulted in several contributions to the 22nd Conference on Integer Programming and Combinatorial Optimization, IPCO 2021: three presentations of research papers and the award in the Student Poster Competition.

NETWORKS consortium awarded €1M from EU COFUND for postdoc programme

After receiving the COFUND grant from the Horizon 2020 programme for 14 PhD positions, NETWORKS has been granted a COFUND grant of €1.0 million to appoint 14 postdoctoral researchers for 2 years.

Current events

Dutch Seminar on Optimization (online series) with Hadi Abbaszadehpeivasti (Tilburg) and Utku Karaca (Erasmus University)

• 2021-12-09T16:00:00+01:00
• 2021-12-09T17:00:00+01:00
December 9 Thursday

Dutch Seminar on Optimization (online series) with Hadi Abbaszadehpeivasti (Tilburg) and Utku Karaca (Erasmus University)

Start: 2021-12-09 16:00:00+01:00 End: 2021-12-09 17:00:00+01:00

Online seminar

The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.

Title:
Utku Karaca : Differentially Private Resource Sharing

Difference-of-convex (DC) problems arise naturally in many applications. The DCA (Difference-of-Convex Algorithm) is a popular algorithm for tackling DC problems. In this talk, we study the convergence rate of the DCA, also known as the convex-concave procedure, by using Performance estimation. We derive a worst-case convergence rate of O(1/sqrt(N)) after N iterations of the objective gradient norm for certain classes of unconstrained DC problems. We give an example which shows the order of convergence cannot be improved for a certain class of DC functions. In addition, we study DC problems on a given convex set and we obtain a convergence rate O(1/N) for some termination criterion. Finally, we investigate the DCA with regularization and we get the same convergence rate.
https://arxiv.org/abs/2109.13566

Abstract of "Differentially Private Resource Sharing" (Utku Karaca):

This study examines a resource-sharing problem involving multiple parties that agree to use a set of capacities together. We start with modeling the whole problem as a mathematical program, where all parties are required to exchange information to obtain the optimal objective function value. This information bears private data from each party in terms of coefficients used in the mathematical program. Moreover, the parties also consider the individual optimal solutions as private. In this setting, the great concern for the parties is the privacy of their data and their optimal allocations. Methodology and results: We propose a two-step approach to meet the privacy requirements of the parties. In the first step, we obtain a reformulated model that is amenable to a decomposition scheme. Although this scheme eliminates almost all data exchange, it does not provide a formal privacy guarantee. In the second step, we provide this guarantee with a differentially private algorithm at the expense of deviating slightly from the optimality. We provide bounds on this deviation and discuss the consequences of these theoretical results. The study ends with a simulation study on a planning problem that demonstrates an application of the proposed approach. Managerial implications: Our work provides a new optimization model and a solution approach for optimal allocation of a set of shared resources among multiple parties who expect privacy of their data. The proposed approach is based on the decomposition of the shared resources and the randomization of the optimization iterations. With our analysis, we show that the resulting randomized algorithm does give a guarantee for the privacy of each party's data. As we work with a general optimization model, our analysis and discussion can be used in different application areas including production planning, logistics, and network revenue management.
https://arxiv.org/abs/2102.07178

Dutch Seminar on Optimization (online series) with Andreas Wiese (VU Amsterdam)

• 2022-01-27T16:00:00+01:00
• 2022-01-27T17:00:00+01:00
January 27 Thursday

Dutch Seminar on Optimization (online series) with Andreas Wiese (VU Amsterdam)

Start: 2022-01-27 16:00:00+01:00 End: 2022-01-27 17:00:00+01:00

Online seminar

The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.

Speaker: Andreas Wiese (VU Amsterdam)

Title:

A PTAS for the Unsplittable Flow on a Path problem
(joint work with Fabrizio Grandoni and Tobias Mömke)

Abstract:

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge $e$ is at most the capacity of $e$. The problem admits a QPTAS. After a long sequence of improvements, the currently best known polynomial time approximation algorithm for UFP has an approximation ratio of $1+\frac{1}{e+1}+\eps < 1.269$. It has been an open question whether this problem admits a PTAS.
In this talk, we present a polynomial time $(1+\eps)$-approximation algorithm for UFP.

Current projects with external funding

• Smart Heuristic Problem Optimization ()
• Wiskundecluster DIAMANT ()
• Mixed-Integer Non-Linear Optimisation Applications (MINOA)
• Optimization for and with Machine Learning (OPTIMAL)
• 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 Studiorum-Universita di Bologna
• CNR Pisa
• CNRS
• Dassault Systèmes B.V.
• IBM
• INRIA
• Prorail
• Rheinische Friedrich-Wilhelmus Universitaet Bonn
• Technische Universität Dortmund
• Tilburg University
• Tromsø, Norway
• Universita degli Studi di Firenze
• Universität Konstanz
• University of Birmingham
• Universiteit van Tilburg