Description

Leader of the group Networks and Optimization: Guido Schäfer.

In today’s society, complex systems surround us. From transport and traffic, to behavioural 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 works to make this complexity manageable.

 

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.

More

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 in the research project "Approximation Algorithms, Quantum Information and Semidefinite Optimization" - Read More…

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.

Postdoc on the subject of Network Games with Combinatorial Structures - Read More…

News

Monique Laurent elected as Fellow of SIAM

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.

Monique Laurent elected as Fellow of SIAM - Read More…

Rubicon grants for David de Laat and Alessandro Zocca

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.

Rubicon grants for David de Laat and Alessandro Zocca - Read More…

Events

N&O Lecture: Dion Gijswijt (Delft)

  • 2016-06-09T11:00:00+02:00
  • 2016-06-09T12:00:00+02:00
June 9 Thursday

Start: 2016-06-09 11:00:00+02:00 End: 2016-06-09 12:00:00+02:00

Room L016 CWI Amsterdam

Everyons who is interested is welcome to attend the lecture of Dion Gijswijt, with the title 'Asymptotic upper bounds on progression-free sets in Z_p^n'.

Abstract:  

We show that any subset of Z_p^n (p an odd prime) without 3-term 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)

  • 2016-06-08T09:00:00+02:00
  • 2016-06-08T10:00:00+02:00
June 8 Wednesday

Start: 2016-06-08 09:00:00+02:00 End: 2016-06-08 10:00:00+02:00

Room L016 CWI Amsterdam

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 n-dimensional 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
mixed-binary 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 CVaR-constrained 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)

  • 2016-05-11T09:00:00+02:00
  • 2016-05-11T10:00:00+02:00
May 11 Wednesday

Start: 2016-05-11 09:00:00+02:00 End: 2016-05-11 10:00:00+02:00

Room L016 - CWI

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

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
  • AQSO
    Approximation Algorithms, Quantum Information and Semidefinite Optimization
  • CoMGA
    Combining Machine Learning and Game-theoretic Approaches for Cluster Analysis
  • ITSLOG
    Real Time Verkeersdata voor Goederenvervoer (ITSLOG)
  • Networks
    Networks (eerste fase)
  • SocialACT
    Societal Impact Games

Partners

  • CTVrede
  • Rovecom BV
  • Stanford University
  • Radboud Universiteit
  • Technische Universiteit Eindhoven
  • Universiteit Leiden
  • Universiteit van Amsterdam
  • Universiteit van Amsterdam