Combinatorial Optimization

  • PO Box 513, Department of Mathematics and Computer Science

    5600 MB Eindhoven

    Netherlands

  • Groene Loper 5, MetaForum

    5612 AP Eindhoven

    Netherlands

Organization profile

Introduction / mission

The Combinatorial Optimization group investigates the structure and relationship between different problems, in order to design efficient and effective algorithms for solving them.

Highlighted phrase

Combinatorial Optimization: finding an optimal solution from a finite set of solutions

Organisational profile

Countless practical optimization problems are, in fact, combinatorial optimization problems: they have an optimal solution that needs to be found amongst a finite set of possible solutions. The aim of combinatorial optimization (CO) is to rapidly and efficiently find such an optimal solution.

CO is related to discrete mathematics, theoretical computer science, applied mathematics, operations research, algorithm theory and computational complexity theory and has important applications in several fields. These include scheduling, production planning, logistics, network design, communication and routing in networks, health care, artificial intelligence, machine learning, auction theory, and software engineering.

The Combinatorial Optimization (CO) group at Eindhoven University of Technology (TU/e) focuses on the analysis and solution of discrete algorithmic problems that are computationally difficult. The group investigates the structure of such problems, analyzes the relations between different problems, and uses this knowledge to design efficient and effective algorithms for solving them. We study both exact and heuristic algorithms. The Group is also interested in combinatorial optimization problems where the input is revealed only gradually, or where there is uncertainty in the parameters, leading to online, stochastic or robust solution methods.

Combinatorial Optimization develops theoretic results, for instance in graph theory and matroids, and apply these to real-world situations. Typical application areas are scheduling, production planning, logistics, network design, communication and routing in networks, and health care. The Group cooperates with KU Leuven, CWI (National Research Institute for Mathematics and Computer Science) and DIAMANT (Discrete, Interactive and Algorithmic Mathematics, Algebra and Number Theory, Dutch mathematics cluster).

Research focuses on:

  • polyhedral techniques
  • local search methods
  • performance guarantee for approximation algorithms
  • online route planning
  • scheduling
  • matroid structure and visualization
  • network problems

Network Recent external collaboration on country level. Dive into details by clicking on the dots.

Research Output 1988 2019

Asymptotics of symmetry in matroids

Pendavingh, R. & van der Pol, J., 1 Mar 2019, In : Journal of Combinatorial Theory, Series B. 135, p. 349-365

Research output: Contribution to journalArticleAcademicpeer-review

Matroid
Automorphism Group
Symmetry
Trivial
Transposition

Building Kidney Exchange Programmes in Europe: an overview of exchange practice and activities

Biro, P., Haase-Kromwijk, B., Andersson, T., Ásgeirsson, E., Baltesová, T., Boletis, I., Bolotinha, C., Bond, G., Böhmig, G., Burnapp, L., Cechlárová, K., Di Caccio, P., Fronek, J., Hadaya, K., Hemke, A., Jacquelinet, C., Johnson, R., Kieszek, R., Kuypers, D., Leisman, R. & 10 othersMacher, M-A., Manlove, D., Menoudakou, G., Salonen, M., Smeulders, B., Sparacino, V., Spieksma, F. C. R., de la Oliva Valentín Muñoz, M., Wilson, N. & van de Klundert, J., 1 Jul 2019, In : Transplantation. 103, 7, p. 1514-1522 9 p.

Research output: Contribution to journalArticleAcademicpeer-review

Open Access
File
Kidney
Living Donors
Practice Guidelines
Tissue Donors
Scandinavian and Nordic Countries

Column generation based math-heuristic for classification trees

Firat, M., Crognier, G., Gabor, A., Hurkens, C. A. J. & Zhang, Y., 6 Jul 2019, (Submitted) In : Computers & Operations Research. 29 p., 1810.06684v1

Research output: Contribution to journalArticleAcademicpeer-review

File
Classification Tree
Column Generation
Decision trees
Linear programming
Integer Linear Programming

Prizes

Algorithms for coping with uncertainty and intractability

Nikhil Bansal (Recipient), 2013

Recognition: ERCConsolidatorScientific

Combinatorial optimization
Approximation algorithms
Computer science
Uncertainty
Optimum design

Faster algorithms in computer science

Jesper Nederlof (Recipient), 2019

Recognition: ERCStartingScientific

Computer science
Polynomials
Computational complexity

NWO Vici Award : Continuous Methods in Discrete Optimization

Nikhil Bansal (Recipient), 2018

Recognition: NWOViciScientific

Discrete Optimization
Rounding
Discrepancy
Computer Science
Stable Polynomials

Press / Media

ACUITY: Algorithms for coping with uncertainty and intractability

Nikhil Bansal

8/11/16

1 item of media coverage

Press/Media: Expert Comment

Student theses

Analysis of an algorithm for finding perfect matching in k-regular bipartite graphs

Author: Blom, D. A., 31 Aug 2017

Supervisor: Pendavingh, R. (Supervisor 1)

Student thesis: Bachelor

File

Bank transaction minimization

Author: Salomé, D., 31 Aug 2017

Supervisor: Nederlof, J. (Supervisor 1) & Verhoeff, T. (Supervisor 2)

Student thesis: Bachelor

File

Curve clustering: hardness and algorithms

Author: Struijs, M., 26 Nov 2018

Supervisor: Nederlof, J. (Supervisor 1), Buchin, K. (Supervisor 2) & Driemel, A. (Supervisor 2)

Student thesis: Master

File