Research Fields

Discrete and Combinatorial Optimization

In discrete and combinatorial optimization one aims at selecting an optimal solution from a set of feasible solutions. The research of the combinatorial optimization at the TU Graz focuses on both theory and applications.

A key topic of the theoretically oriented research lies on the design of efficient exact and approximate algorithms for combinatorial optimization problems. A key research topic is to investigate how special structures posed on the input data of a combinatorial optimization problem can be exploited to arrive at more efficient solution approaches. This question is closely related to the investigation of the borderline between between efficiently solvable problems and NP-hard problems. In recent years the focus has been on investigations of location problems, nonlinear assignment problems, the TSP, combinatorial optimization problems with quadratic costs and recently robust combinatorial optimization problems.

The application-oriented part of our research focuses on complex real-world optimization problems, such combined location-transportation problems, production planning problems from chemical industry, cutting problems from paper industry, reducing the global CO2 fleet emission and a number of problems in logistics. We have successfully cooperated with industrial partners over the years and are very open to cooperations.

  • Keywords: NP-hard problems, approximation algorithms, assignment problems, efficiently solvable special cases, robust optimization, complex real-world problems