Engineering and Physics

Optimization in Engineering and Physics

The EDOM group has a rich history of collaborations with engineers with projects involving all kinds of engineering questions. We are specifically interested in bringing methods from discrete optimization to application in fields where they are not well established: Most engineering models are modeled with a well-established simulation model in the background. Discrete parameters are then often introduced via trial-and-error or heuristic methods. We have shown in various applications that it is possible to produce guaranteed globally optimal solutions in such cases.

In order to understand the characteristics of certain physics problems, it is helpful to study their minimum-energy states, or, if possible, the complete partition function. In this project, we focus on the area of disordered systems. Our goal is to provide effective methods and fast implementations for challenging physics problems. We focus on the design of exact solution procedures that always generate correct solutions, as this is often required by the application. A variety of our implementations is publicly available via the spin glass ground-state server.

Further details can also be found at http://cophy.informatik.uni-koeln.de/

 

Current Projects

Quality control by robust optimization

The long-term goal of the whole CRC1411 is the property design of single particles and particulate products made from these single particles. The objective of Subproject D06 within the CRC1411 is the development, algorithmic design, implementation and validation of robust mathematical optimization methods for protecting the design of particulate products against uncertainties. Global solution methods are investigated for optimal robust chromatography as well as synthesis processes, developing methods based on reformulation and decomposition. The obtained results are validated with the projects. Information on which uncertainties are most relevant and should be reduced, together with recommendations on robust optimum design and quality control, are returned to the experimental projects.

For more details visit: https://www.crc1411.research.fau.eu

Contact: Frauke Liers, Jana Dienstbier

Ising Spin Glasses

Algorithmically, minimizing the energy function for Ising spins is an unconstrained quadratic binary optimization problem that is well known to be equivalent to the max-2-cut problem. Given an edge-weighted graph, max-2-cut asks for partitioning the nodes into two disjoint sets maximizing the sum of the weights of edges connecting nodes in different partitions. Max-2-cut is in general an NP-hard problem that is also difficult in practice. For special graph classes, however, it allows solution in polynomial time. We develop exact approaches for both the NP-hard and the polynomially solvable cases of the max-2-cut problem and use them for the physics application.

Contact: Frauke Liers

Finished Projects

LeOpIn – Life-cycle oriented optimization for a resource- and energy-efficient infrastructure

The goal of the project LeOpIn is to devise methods for life-cycle oriented planning and evaluation of buildings and related infrastructure. To this end we develop simulation and optimization tools which can cope with this task. A concrete application is the planning of a building and pipes undergoing high pressure scenarios for which a software solution will be prototypically developed. The development of the planning and evaluation procedures demands a tight interaction between mathematical and engineering techniques. We plan to employ methods of numerical simulation and of discrete and nonlinear optimization. The main focus lies on integration of these techniques since only by this the high complexity of the treated problems can be handled appropriately.

Details

Contact: Alexander Martin and Stefan Schmieder (Project A) or Lars Schewe and Jakob Schelbert (Project B)

Optimal combination of active and passive parts in load carrying systems

Mechanical trusses are found in many applications (undercarriages of airplanes, bicycles, electrical towers, etc.). Those trusses are often overdimensioned to withstand given forces under several uncertainties in loadings, material, production processes, etc. Active parts (e.g. piezo-elements) can react on these uncertain effects and reduce the dimension of trusses. CRC 805 introduces new technologies to handle uncertainty in load carrying systems. Mathematically, this leads to a mixed-integer semi-definite programming problem.

For more details visit http://www.sfb805.tu-darmstadt.de/

Contact: Sonja Mars or Kai Habermehl (TU Darmstadt)

Commanding Uncertainties in Systems of Mechanical Engineering

Depending on the level of abstraction, various processing chains with uncertainties occur within this project. Here, we start with a mathematical model for process chains and their inherent uncertainties with the help of a distribution over a set of random envents or scenarios. We follow two approaches. One deals with very large structured mixed integer programs as known from stochastic programming. The other one deals with PSPACE-complete problems like Quantified Integer Programs or some special classes of the Dynamic Graph Reliability problem.

Contact: Alexander Martin, Ulf Lorenz (TU Darmstadt), Nicole Ziems

Collaborative Research Centre 666: Integral sheet metal design with higher order bifurcations – Development, Production, Evaluation

Branches are found in a lot of sheet metal products. The CRC666 studies a very new technique, called “Linear flow splitting”, to create integral sheet metal products with branches. Mathematical Optimization is the emphasis of two subprojects. The aim of the first one is the optimization of the topological structure and the geometry of the products, using Discrete and Nonlinear Optimization. The second one is engaged to find an optimal procedure to produce the product subject to manufacturing restrictions. Here Discrete Optimization and Graph Theory plays an important role

For more details visit http://www.sfb666.tu-darmstadt.de/

Contact: Wolfgang Hess (TU Darmstadt) or Ute Günther

Layout and Process Optimization in Recovered Paper Production

Recovered paper nowerdays is the most important resource in the paper production. One trouble in the paper manufactoring process are production losses due to tacky particles called stickies. The aim of this project is the simultaneous optimization of the layout and setting of a machine cleaning the waste paper suspension from these stickies. The separation process itself can be descibed by nonconvex functions. Including the layout decision then results in a mixed-integer nonlinear problem (MINLP). We solve the model using piecewise linear approximations of the nonlinear functions.

 

Contact: Alexander Martin, Christine Hayn, Armin Fügenschuh (ZIB)

Examination of the rearrangeable blocking behaviour of Clos-Networks with respect to multicast traffic

Clos networks have been invented by Charles Clos in 1953 in order to reduce network size and cost. A Clos network is composed from smaller crossbars, which are arranged in three stages. A multicast connection request is an arbitrary partial function from the set of outputs to the set of inputs of a network. To this day, no formula is known in order to determine the minimal number of middle stage crossbars such that in the associated Clos network any multicast connection request is routable. We have computationally determined this number for a set of small Clos networks, yielding significant cost reductions compared to trivial switching networks.

Contact: Peter Lietz, Alexander Martin

Optimal Grid Partitioning for Block Structured Grids

In order for mesh-based scientific simulations to be efficiently executed on parallel hardware it is inevitable to distribute the mesh elements among the available processors such that the computational load is balanced and the time required for interprocessor communication is minimized. In this project we develop a new way to reflect hardware restrictions in communication schedules by setting up (and solving) a new integer programming formulation of the graph partitioning problem.

Contact: Alexander Martin

Potts Spin Glasses

In a Potts spin glass, a spin can attain one of k states. The determination of energy-minimum states amounts to computing a maximum k-cut in the graph of interactions. Thus, the task is to partitioning the set of vertices of a graph into k disjoint subsets so as to maximize the total weight of the edges joining vertices in different partitions. We design and implement exact branch-and-cut algorithms based on semidefinite programming and cutting planes.
Another function of interest is the partition function that encodes the complete physics of a system. For Potts glasses with a large number of states, the dominant term in the partition function can be determined by solving the optimum cooperation problem that can be explained as follows. Suppose we are given a set of researchers. For each pair of researchers, we know the benefit of working together. The optimum cooperation problem asks for an assignment of people to projects such that the number of research projects covered plus the total benefit is maximum. Using graph-theoretic considerations, we considerably reduce the number of iterations of the method in practice.

Contact:Frauke Liers

Coulomb Glasses

The problem of determining ground states of Coulomb glasses can be modelled as an equicut problem in a weighted complete graph. Given a partitioning of its nodes into two partitions of equal size, the equicut is defined as the set of edges joining nodes in different partitions. Computing an equicut with maximum weight is an NP-hard task. We design an exact branch-and-cut approach using general and problem-specific separation routines.Details on the coulomb glasses

Contact: Andreas Schmutzer

Spin Glass Ground-State Server

As a service to the community, our implementations are publicly available via the spin-glass ground state server. Short- and long-range spin glass realizations of different dimensions can be submitted to the server, either through a web interface or using a command-line client. Big job batches are possible as well. Results are returned via e-mail.

Details at http://www.informatik.uni-koeln.de/spinglass/

Contact: spinglass[ät]informatik.uni-koeln.de