Science and Industry under One Roof

The BMBF Research Campus MODAL starts its first main phase. In four mathematical labs, academia and industry join forces to work on data driven modelling, simulation, and optimization of complex real world processes from transportation, energy, medicine, and the development of general solver technology.

Decision Making 4.0

Imagine a world in the not so distant future where planning and control are easy. Trains are scheduled punctually and on demand. The gas-transport network and other supply networks are shared in a nondiscriminatory way by competing suppliers. Cancer and other diseases are diagnosed early by routine blood tests. Powerful planning and control tools make smart use of ubiquitous data. Making this utopia become a reality is the vision of the Research Campus MODAL, whose first five-year phase was initiated in a grand opening ceremony on October 13, 2014, by State Secretary Dr. Georg Schütte of the Federal Ministry for Research and Education (BMBF).

State Secretary Dr. Georg Schütte of the BMBF at the MODAL Opening Ceremony on October 13, 2014

Mathematical Optimization and Data Analysis Laboratories

This is what the acronym MODAL stands for. MODAL is one out of nine Research Campuses supported by the Federal Ministry of Research and Education as part of the  Hightech Strategy of the German government.

Located at and operated by the Zuse Institute Berlin in cooperation with Freie Universität Berlin, MODAL fosters public-private research partnerships. Currently, twelve companies participate, ranging from small spin-offs to established global players. With its 15-year horizon and a research budget of more than two million euros per year, the more than 40 researchers of the campus will advance the data-driven development of pioneering modeling, simulation, and optimization methods. Within the excellence platform of the Einstein Center for Mathematics Berlin, MODAL provides the link to industrial mathematics. A unique feature of the campus is MODAL AG (MAG), a nonprofit-oriented company that offers maintenance, support, and system-integration services for MODAL partners and other interested parties that the participating research institutions cannot provide. MAG ensures the long-term utilization of research results.

Scientific and Industrial Partners in the Research Campus MODAL

The LabsWork: RAILWAYS, GAS NETWORKS, CANCER DIAGNOSIS, GENERAL SOLVERS

The Research Campus MODAL consists of four interdisciplinary labs whose basic application-oriented research is focused on specific innovation problems while at the same time concrete industrial problems are tackled.

  • The RailLab works on the optimization of train rotations using algorithmic hypergraph theory. Industry partner DB Fernverkehr, the long-distance passenger transport division of Deutsche Bahn, uses the optimization core ROTOR to schedule the German ICE fleet, while Berlin companies LBW and IVU Traffic Technologies market the rotation optimizer VS-OPT-rail in the scheduling system ivu.rail.
  • The MedLab researches the efficient storage, classification, and pattern recognition of mass spectrometric omics data for cancer diagnosis. Cooperation partner SAP provides high-performance in-memory storage technologies, the SMEs companies 1000shapes and CIT develop professional software for model-based data analysis, and the associated partner Inbion helps improve standard operating procedures.
  • The GasLab develops mixed-integer non-linear constraint programming methods to control the gas transport network of Germany. Operator Open Grid Europe, formerly known as E.ON Gas Transport, must ensure security of supply, nondiscriminatory access, efficiency, and flexibility to make the energy revolution in Germany a success.
  • The SynLab investigates general discrete-continuous-stochastic optimization problems and provides the open-source solver SCIP as an academic research and development platform. The manufacturers of the leading industrial solvers CPLEX, Gurobi, and Xpress; the software integrator GAMS; and SAP and Siemens cooperate within SynLab on the development of new optimization methods.

In addition to the activities of the labs, MODAL bundles respective legal competence, international cooperation, and capacity building. For example, MODAL runs several programs for attracting and educating the next generation of researchers and practitioners. In this respect, MODAL runs the Graduate Research in Industrial Projects for Students (G-RIPS) program in cooperation with the NSF Institute for Pure and Applied Mathematics (IPAM) of the University of California, Los Angeles, and Freie Universität Berlin. Every year, G-RIPS provides an opportunity for high-achieving graduate-level students to join the labs. Working in international teams (two students from the US and two from European universities), an academic mentor, and an industrial sponsor, a real-world research project is addressed. Successful participation is rewarded with ten 10 ECTS credits.

The RailLab: Optimal Train Rotations

The German railway system consists of 340,000 kilometers of tracks. A total of 5,300 cargo and 27,000 passenger trains per day transport more than one million tons of goods and 5.2 million people. The high-speed fleet alone operates about 1,400 trips per day with 250 trains of five different types, conveying about 340,000 people. A single ICE3 train costs about 40 million euros. This rolling stock should be put to best possible use.

Despite the complexity of the system, railway scheduling is still largely done by hand. This is in sharp contrast to the related airline and public-transport sectors, where mathematical fleet and crew optimizers are today established as an industry standard (FN: R. Borndörfer, M. Grötschel, U. Jaeger {2010}. Planning Problems in Public Transit. Production Factor Mathematics, pp. 95-122, 2010, isbn: 978-3-642-11247-8. Preprint available as ZIB-Report 09-13). These tools have, in particular, played an important role in revolutionizing the way airlines have operated since the 1990s. Clearly, the railways want similar tools. The key problem here is vehicle rotation scheduling, the topic of the MODAL RailLab.

Railway Systems are Hypergraphs

The main obstacle in railway optimization is the technical constraints of the wheel-rail system that prevent straightforward attempts to decompose the planning process. In contrast to buses and aircraft, where individual vehicles are considered, trains are composed of multiple units that operate in sequence and orientation, such that classic network flow methods do not apply. Instead, an algorithmic theory of flows in hypergraphs is needed to deal with vehicle rotations and train compositions at the same time (FN: R. Borndörfer, M. Reuther, T. Schlechte, S. Weider {2011}. A Hypergraph Model for Railway Vehicle Rotation Planning. 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics {OASIcs}{20}, pp. 146-155. Preprint available as ZIB-Report 11-36.). Such methods are also useful for scheduling crews in teams.

Modelling Railway Vehicle Rotations Using Hypergraphs

Vehicle-rotation-planning problems are large scale, and their solution requires high-performance algorithms. The RailLab has developed a new coarse-to-fine method, which allows them to deal with most of the problems on a coarse train or vehicle level and to focus on the important parts in a finer sequence and orientation level where necessary, guided by bounds that control the approximation error (FN:R. Borndörfer, M. Reuther, T. Schlechte {2014}. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 79-91, Vol.42, OpenAccess Series in Informatics {OASIcs}. Preprint available as ZIB-Report 14-26.). On this basis, high-quality vehicle rotations can be constructed using novel Lin-Kernighan-type algorithms.

The ROTOR and VS-OPT-rail Optimizers

These methods are at the heart of RailLabs ROTOR and VS-OPT-rail optimization cores that are integrated as solvers in the FEO (Fahr- und Einsatzoptimierung) and ivu.rail systems of the industry partners DB Fernverkehr AG and LBW GbR and IVU Traffic Technologies AG, respec-tively. These tools are already in daily use at several railways in Germany and elsewhere. Currently, cyclic strategic plan-ning problems for the “standard week” are solved; this is important for service design and vehicle procurement. To achieve a more direct impact on costs and quality, detailed fully dated problems for a set calendar period have to be solved. This leads to acyclic hyperflow problems with boundary conditions. Ultimately, RailLab aims at providing mathematical optimization support for the complete range of railway planning problems involving rolling stock.


Cyclic High Speed Train Timetable for a Standard Week

Strategic planning of ICE train rotations: Hypergraph visualization tool HyDraw of Ricardo Euler and Gerwin Gamrath based on JavaView of Konrad Polthier. In strategic train rotation planning rotation cycles for so-called standard weeks are designed in order to determine the number of trains needed for the future timetable. 

The MedLab: Diagnosing Cancer using Omics-Data

In recent years, the development of high-throughput technologies has enabled the generation of vast amounts of information from multiple biological data sources such as genomics, transcriptomics, proteomics, and meta-bolomics – the “omics” sources.  

 

Using these data sources has increased our understanding of many molecular and cellular mechanisms in biological systems like the processes underlying severe diseases in the human body. In contrast,this explosive growth of data poses a challenge in our understanding of medicine: current analysis approaches can use the huge amount of collected mass data only minimally; medically important relationships are lost in this data tsunami. While the potential opportunities are not questioned in principle, many high expectations from the early 2000s have been disappointing so far. For example, proteomics-based biomarkers that have been hyped for quite some time never met the expectations that were promised, such as new diagnostic tools for fighting cancer etc. The main reasons for this were technical difficulties with data analysis and problems with data acquisition, which led to studies that could not be reproduced across laboratories. These problems are usually not due to principle impossibility but mainly exist because of a lack in data quality and analysis methods.

Diseases Leave Traces on a Molecular Level

Taming the Data Tsunami

While it has been known for a long time that changes in cells while they are undergoing transformation from “normal” to malignant cells (e.g. during infections) happen on many biological levels, such as genome, transcriptome, proteome, and metabolome, traditional analysis approaches still depend on only one data source – for example, transcriptomics. This is in contrast to the central dogma of molecular biology that states that these levels are actually highly interconnected and depend on each other.

Modern -omics Platforms Can Measure Several Types of Molecules

INDIVIDUALIZEDDIAGNOSTICS

The MODAL MedLab is developing new mathematical methods like sparse classification schemes and network-based data analysis that allow (1) identifica-tion of multivariate disease signatures that describe changes in multiple data sources and (2) development of multi-level models that embeds these findings into the actual biological context. Both parts combined with efficient data management techniques will eventually lead to a thorough understanding of the modeled process and open up the opportunity to use the respective model for diagnostic purposes for individuals, thus allowing high-throughput classification of biological samples. These techniques can then be adjusted to an individual by using its omics data and thus allow to derive information about the individual’s state, for example, as diagnostic tools for a certain disease that is captured by the data and the model. Ultimately this will lead to better treatments for today’s patients and accelerate progress in making medical discoveries. Our main goal is to transform found biological insight directly into diagnoses, prognosis, and therapeutics that improve our ability to detect and treat human disease. We develop advanced tools in close cooperation with our industrial partners and in collaboration with several clinical research groups at hospitals in Berlin and abroad.

The GasLab: CHALLENGES OF GAS-TRANSPORT-NETWORK OPERATION

An important part of the energy consumed in Germany is produced from natural gas. Therefore, in optimizing the allocation and usage of the gas grid ,one could save a sufficient amount of energy. However, the liberalization of the German gas market and the associated divestiture of gas companies have led to new challenges in the planning and operation of gas-transport grids over the last few years. 


The MODAL GasLab addresses these challenges and aims to develop new methods for gas-grid planning and operation, combining the most modern mathematic algorithms and up-to-date information technology. The tools developed in the GasLab will assist gas dispatchers and planners in their work and put them in a position to make better decisions based on foresighted and comprehensive information. The GasLab brings together the main areas of expertise of the scientific partners; that is, modeling, simulation, and optimization to advance the state of the art in gas-grid management and facilitate innovations. This is supported by a detailed understanding of the issues and comprehensive data, which will be ensured by collaboration with and the know-how of the industrial partner Open Grid Europe GmbH.

The OGE Gas Network in Germany With a Subnetwork

The gas network of the German gas supplier OpenGridEurope. The network consists of passive and active components such as pipelines, compressors, and valves.

A Guidance System for Gas Networks

The main task of the project is the sci-entific research and development of so-lution procedures to design efficient algorithms and construct a novel software tool, the Navi, that provides a plan for managing the gas grid in advance for a period of at least twenty-four hours. Similarly to a navigation route guidance device for cars, the tool should provide a safe and cost-minimizing sequence of operating decisions to the gas dispatcher to assist in actual decision making with regard to gas-grid management measures, such as changing the mode of compressor stations or closing or opening valves.

Gas Compressor Station

There are several aspects that make the corresponding problem challenging. For example, due to the compressibility of gas, the gas grid itself acts as storage. The appropriate description of the gas be-havior involves a set of partial differential equations for each pipeline, and the feasible operating ranges of the gas compressors form a nonconvex set. The model should be able to handle the transient case, which allows a dynamic change of the variables in time. The model involves both discrete and continu-ous decisions, like opening a valve or deciding to run a compressor on a certain pressure adjustment level, which further complicates the modeling. In addition to the challenges in modeling, a good prediction of transport demands and an estimate of the associated uncertainty is crucial for detecting critical future network situations early to react to these properly. Finally, the navigation tool has to operate a real-world gas grid without interruption.

Ensuring Non-Discriminatory Access

In addition to technical measures, the gas- grid operators have regulatory options to ensure the secure operation of the grid while satisfying the transport demands of the customers. One option is to restrict a gas power station in a critical situation to obtaining gas from one specific entry instead of ordering gas from any entry point of the network.

 

Given a set of power stations at exit points with their corresponding fixed restriction entry point as well as the current network situation, the project aim is the development of a tool, the KWP-Tool, that calculates a foresighted decision sug-gestion for the gas-grid operator as to which power stations this option will need to be used on the upcoming gas day. Therefore, the tool has to identify critical network situations in advance for the next forty hours and that cannot be balanced by technical measures only. Moreover, since the product may be applied for several gas power stations, the decisions suggested by the KWP-Tool need to be nondiscriminatory. These challenges will be addressed by research on game theory, modeling of gas flow, and statistical forecasting and evaluation methods; enhanced by heuristics derived from expert knowledge from our industrial partner; facilitating both scientific progress and practical use of the novel methods.

The SynLab: Advancing Optimization Technology

The development of state-of-the-art optimization software at ZIB started more than 25 years ago. It has been driven by various industrial applications coupled with a strong academic focus. The optimization software developed and maintained at ZIB, forming the SCIP Optimization Suite, is globally recognized and stands as one of the most versatile and best performing open-source packages for mixed-integer linear and nonlinear optimization.

 

SYNLABSCIPSTRUCTURE

The SCIP Optimization Suite. SCIP consists of a core framework, given by the grey structure, and numerous plugins, the colored nodes. A strength of SCIP is the plugin structure that permits the simple extension of the solver.

The Power of Cooperation

In the SynLab of the Research Campus MODAL, the world’s leading researchers and developers from companies like Gurobi (FN:Gurobi Optimization, Inc., www.gurobi.com), FICO Xpress (FN:FICO Xpress Optimization, www.fico.com/en/products/fico-xpress-optimization-suite), and GAMS (FN:GAMS, www.gams.com) cooperate with ZIB researchers to develop the mathematical methods behind the next generation of mathematical optimization tools. In addition, long running collaborations with SAP (FN:SAP Software & Solutions, www.sap.com) and Siemens(FN:Siemens, www.siemens.com) have also been integrated into the SynLab, supplying challenging industrial problems. As a result of the Siemens cooperation, the linear programming (LP) solver SoPlex has become the fastest exact LP solver on the market. Finally, in 2014 Google started to use SCIP in their combinatorial optimization library or-tools (FN:Google Optimization Tools - Optimization, developers.google.com/optimization).

Striving for the Best

The most recent release of SCIP, version 3.1.1, is currently the fastest non-commercial mixed-integer programming solver. SCIP integrates the techniques of mixed integer programming, constraint programming, and satisfiability testing to solve complex problems. In recent years, parallel extensions of SCIP have been developed as part of the UG (FN:Y. Shinano, S. Heinz, S, Vigerske, M. Winkler {2013}. FiberSCIP - A shared memory parallelization of SCIP. ZIB-Report 13-55, Zuse Institute Berlin, Takustr. 7, 14195 Berlin) framework. The result of this development has seen SCIP solving mixed-integer programs on supercomputers utilizing up to 80,000 cores in parallel. Advancements achieved with SCIP have led to the successful completion of numerous outstanding collaborative research projects and underlines many of the projects within the Research Campus MODAL.

SYNLABSCIPPERFORMANCS

The solving performance of SCIP on the benchmark MIPLIB2010 test instances compared to other commercial and non-commercial solvers.

Continued, Successful, and Openly Shared Development

The projects of SynLab successfully promote the further development of the SCIP Optimization Suite. A focus of SynLab is the development of software to meet the growing number of everyday data-intensive processes. A Goo-gle Faculty Award was awarded for the project Mixed Integer Optimization as a Service, which aims to advance SCIP to address modern technological requirements. Furthermore, the SynLab strives to advance mixed-integer programming techniques by improving the cutting plane and branching approaches of SCIP. Keeping with the “shared development” theme of the SynLab, an extension of SCIP called SCIP-Jack (FN:G. Gamrath, T. Koch, D. Rehfeldt, Y. Shinano {2014}. SCIP-Jack - A massively parallel STP solver. ZIB-Report 14-35, Zuse Institute Berlin, Takustr. 7, 14195 Berlin) has recently been developed. It is a solver, available in source, for the general Steiner Tree Problem in Graphs – a classic combinatorial optimization problem – and won in multiple categories at the recent DIMACS challenge (FN:11th DIMACS Implementation Challenge, dimacs11.cs.princeton.edu). SCIP-Jack can solve ten different variants of the Steiner Tree Problem, including the prize-winning Steiner Tree, maximum weight connected subgraph, and the group Steiner Tree Problems. The promotion of the SCIP Optimization Suite to the wider academic community is an important focus of the SynLab. This is achieved through vari-ous visits by researchers – including Domenico Salvagnin, Zonghao Gu, Hans Mittelmann, Christina Burt, Atsuko Ikegami, and Andrea Lodi – and the successful hosting of an intensive three-day SCIP workshop at ZIB with more than 50 participants.