Dr. Martin Tieves
Contact / Research / Publications / Conferences and Workshops / Teaching
Research Interests
- Discrete and robust optimization
- Design of telecommunication networks
Specific problems: "Network Design with Compression" and "Virtual Network Embedding" - Algorithmic approaches to the equitable vertex coloring problem
Projects
See also (link)- Virtual Network Embedding (VINO)
Funding: BMBF Programm Mathematik für Innovationen in Industrie und Dienstleistungen
The research project VINO deals with mathematical models and solution methods for problems that arise from the dynamic of modern ICT-networks. Regarding the requirements of the operators and users of such networks particular focus lies on the dynamic optimization of Flexgrid optical transport networks as well as on the embedding of virtual networks into physical substrate networks. The goal of the project is the development of new mathematical approaches, which provide solutions of both problem classes under consideration of temporal changes of the data and requests. A further aim is the development and implementation of algorithms, which build the basis for practically applicable tools.
The project is divided into four subprojects, each focusing on a particular aspect of the whole project. These are 1) multi-period-optimization under consideration of temporal, non-stochastic changes, 2) static, detailed models for the generation of bounds for comparison purposes, 3) pro-active long-term planning models under uncertainties and 4) online-optimization and fast reconfiguration algorithms. An important aspect throughout the project is the active exchange between the subprojects and the corporation with our industrial partners.
The results of the research project will be made available to the involved companies. This includes the developed algorithms and software prototypes as well as relevant know-how gained in the project, giving the partners an advantage in the competition.
Results (Excerpt):
Poster (DRCN 2015)
Publications
Data Uncertainty in Virtual Network Embedding: Robust Optimization Approaches, Stefano Coniglio, Arie M.C.A. Koster, Martin Tieves, Journal of Network and Systems Management 24 (2016), no. 3, 681-710 (link).
Virtual network embedding under uncertainty: Exact and heuristic approaches, Stefano Coniglio, Arie M.C.A. Koster, Martin Tieves, 11th International conference on the Design of Reliable Communication Networks (DRCN 2015), IEEE (2015), 1-8. (link). - Branch-and-Bound Algorithmen for the Equitable Graph Coloring Problem (EqColor)
Funding: DFG Excellence Initiative
An equitable graph coloring is a vertex coloring, such that the size of the color classes differ by at most one. In application, this problem arises, for example, in scheduling problems where tasks should be assigned to workers or maschines in a fair manner.
Fig.1 - An equitable coloring
In this project, we consider a flow-based scheme for generating pruning rules for enumerative algorithms such as DSATUR. Such scheme models the extendability of a partial (equitable) coloring into an equitable coloring via network flows. We extend on the former undergraduate funds project Implementation of a new branch and bound algorithm for the equitable coloring problem (IBBVeF) by Sven Förster für. The aim of this project is to find further theoretical results and to develop a state of the art C++ implementation of such branch and bound algorithm. - UP BEAT - User-friendly Program for Better Effectiveness of Advertising Tools
Funding: DFG Excellence Initiative
Online advertising has become a full member of the marketing mix and is still growing in importance. The US market for online advertising was 22.7 billion USD in 2009 (Silverman 2010) and is expected to grow to 37.2 billion USD in 2013 (IAB 2009). For Europe the prospects are similarly impressive. With so much money being spent for online advertising one would expect that there are highly sophisticated controlling systems in place to make sure that the money is spent only for efficient forms of advertising.
However, the reality is far from it. Although there is a large flood of data (e.g., information about online advertising impressions as well as records of each click on an online advertisement) researchers and practitioners very often just use basic regression models to estimate the impact of their advertising campaigns and to optimize the distribution of advertising budget between different forms of online advertising (e.g., email, search engine marketing, banner advertising). Academic research has demonstrated that, in addition to short-term advertising effects, it is important to incorporate long-term and synergy effects when analyzing advertising effectiveness. The authors have shown that advanced econometric methods can be used to improve the allocation of online advertising budgets, but given the complex nature and its time consuming calculations researchers and practitioners have not yet taken full advantage of those insight.
The aim of the project is to substantially increase the user-friendliness, increase the calculation speed, and increase the flexibility of advertising effectiveness models so that researchers and practitioners can take full advantage of the latest academic insights regarding the efficient allocation of advertising budgets. In that way they will be able to include not only short-term but in particular long-term and synergy effects when analyzing the efficiency of different forms of advertising. - METASOLVER - Competing Solution Algorithms for Optimization Problems
Funding: DFG Excellence Initiative
Mixed Integer Programming (MIP) has been one of the most powerful methods to solve discrete optimization problems for more than 50 years. Incredible progress can be observed, which is not only due to faster computers, but also to better algorithms. The framework, however, did not change significantly: the branch-and-bound method dividing the problem in smaller and smaller subproblems and exploiting the information derived from these subproblems for the overall problem. Important advances include the use of cutting planes throughout the branch-and-bound tree, so-called branch-and-cut, the dynamic generation of columns, faster algorithms for solving the linear programs.
The competition between the various solvers (Cplex, Gurobi, Scip, etc.) has stimulated new developments, yielding a ever-improving performance of all of them. These developments however also has a drawback: researchers and practitioners using MIP solvers as black-box or with their own additional features have to choose a MIP solver to perform computation experiments. For academic researchers, all major solvers (commercial and non-commercial) are free to use, but the selection of the best solver for a particular application is a time-consuming activity (including solver specific coding) with the threat to be forced to reverse a decision after the release of a new version of one of the solvers. Further, a best MIP solver for the problem at hand might not exist. In particular, our experience with the various MIP solvers has shown that some are particular good in finding good solutions at an early stage of the solution process, whereas other solvers find strong dual bounds early.
While this is problematic for a single user, the diverse situation can potentially be exploited to obtain faster optimality proofs. That is, in this project, we develop a software, which runs multiple solvers in parallel, such that certain information can be exchanged (e.g. primal- and dual bounds). The aim is to exploit synergies among the different solvers, such that an overall faster solution process can be obtained.
last modified: 06/01/2017 - 09:37
math2.rwth-aachen.de