Universität Paderborn » SFB 901 » Projects » Project Area C » C3 » Abstract

Subproject C3 (until June 30, 2015)

Modeling of Optimization Problems

Abstract

In this project, we examine the application of the On-The-Fly Computing paradigm to the modeling and solution of optimization prolems, in particular in the domain of public supply and logistics networks. Traditionally in this domain, large monolithic software systems prevail, which are difficult to adapt to new requirements. In our research, we want to examine how the planning task itself as well as its mathematical model and its software implementation can be decomposed into components in order to enable the On-The-Fly construction of an optimization system for an individual planning task.


Flexible Generation of Optimization Systems

Our main goal within the subproject can be summarized as to enable the flexible generation of optimization-based decision support systems with the aid of CRC 901- and C3-Techniques. To that end we envision the realization of the following process visualized in the Figure above. The process starts with an abstract optimization model to be generated for the problem situation at hand. The model can be created or reused in a typical Algebraic Modeling Language (AML) such as AMPL, GAMS or AIMMS. With the C3-Techniques of AML Reengineering and Ontology Optimization Models it will be possible to transfer the model into a representation that captures the necessary semantics. The ontology representation also serves as an intermediate layer before the generation of a model instantiation service, see also the second Figure.

With the ontology representation of the optimization model it is possible to edit and manipulate the model easily, even for machines. In addition to that, the representation is based on reusing conceptualizations for goals and constraints independent of data models. Changes of data models or constraint formulations, e.g., when using a smoothed reformulation for NLP optimization, are manipulations of the ontology graph and can in the most simple case only consist of a single type change. With the straight-forward generation of a SSL-Service Description (subproject B1), a model service is described for the automated composition with other services such as solvers and preprocessors. Before the execution of the system, the semi-automated generation of required adaptor services is supported by the approach due to the specification of data semantics in ontologies.

The flexible generation of optimization systems can now be performed by CRC 901 techniques such as matching and composition, and the whole design allows to reconfigure the system in case of a failing composition or unsatisfactory execution. Thereby, the reconfiguration is highly automatable due to the usage of an ontology model representation.

Second Figure: Ontology-Representation as an intermediate Layer

Water Distribution Systems: A Domain for Optimization

We explore the methods in the area of water distribution systems. These systems can be represented by the following network structure: Nodes typically represent tanks, reservoirs and junctions where water enters or leaves the system. Links between nodes model pipes through which the water can flow from one node to another. Special components in a water distribution system are valves, which can control pressure and flow in the network and allow the filling of tanks from a water outlet. Other special components are pumps which transport water from nodes with low elevation to nodes with a higher elevation. Both components may be required in order to keep the network operable.

The operation of pumps and valves leads to the problem of optimal operation. This problem is one of many tasks allowing a mathematical formulation in terms of an optimization problem. Other problems may include layout decisions. Due to water-saving measures, the water consumption decreased and a lot of components in water distribution systems do not have the right dimensions to work efficiently. Therefore, the dimensions of these components can be optimized.

Third Figure: A fictitious water distribution system

Description, Composition and Analysis: Cooperation within the CRC

In order to describe semantic services for optimization models, solvers and further components, a new form of service specification investigated in subproject B1 is required. The SSL-Service Specification besides others allows for a matching of provided and required services on a suited level of detail. Other questions affect composition and configuration. We collaborate with subproject B2 in the context of template-based composition. The verification of service compositions is another important technique investigated in subproject B3. Finally, all our cooperations are coordinated within the Querschnittsthema "Beschreibung, Komposition und Analyse von Services".

Conclusion

To conclude, we focus our work in the following three areas of research within the first period:

  1. Development of a semantic representation of optimization models
  2. Investigation of OTF-Concepts at the C3-Example
  3. Development of models, methods and applications for different optimization problem situations