Matheon Sino-German Workshop

Nonlinear Integer Programming and Structural Optimization

Tuesday 10.7.2007, 13:00-19:10, TU-Berlin, Straße des 17. Juni 136, Room MA 313

13:00Martin GrötschelMatheonIntroduction
13:10Fredi TröltschTU Berlin Optimal Control of PDEs with state constraints --- mathematical challenges and applications
In many applications of the control theory, the state of the associated control system has to obey strict bounds. In contrast to bounds on the control, these so-called state constraints cause specific difficulties in theory and numerical methods. The talk surveys different problems, where state constraints are very important, explains the main mathematical difficulties and shows ways to resolve them.
13:50Ya-Xiang YuanLSEC Relaxation techniques for the quadratic assignment problem
The quadratic assignment problem is to minimize a quadratic function defined over the set of permutation matrices. Obtaining accurate estimates of the bounds of QAP is very important and helpful for constructing efficient branch-and-bound algorithms to solve QAP problems. In this talk, we will discuss various technique to relax the QAP problem in order to obtain bounds for QAP.
15:10Armin FügenschuhTU Darmstadt Solving Nonlinear Discrete-Continuous Optimization Problems with linear MIP Techniques
Several real-world optimization and control problems, in particular in engineering applications, consist of a blend of nonlinear continuous phenomena and discrete decisions. In order to find global optimal solutions (or at least, solutions with provable bounds on the optimality gap), one possible way is to model such problems as linear mixed-integer programs. The advantage of this approach is that for the solution of the latter several highly effective numerical codes are available. However, one has to approximate the non-linearities using only linear constraints and mixed-integer variables.
In this talk we give an overview on such approximation techniques for one- and two-dimensional nonlinear functions. Thereafter we discuss their applications to different industrial problems. One problem is the optimal control of airplanes under free-flight conditions, where discrete decisions emerge due to airspace restrictions. Another problem is in the area of topology optimization, where an optimal design of sheet metal product is demanded.
15:50Thorsten KochZIB The SCIP Framework
Solving Constraint Integer Programs is a solver framework combining techniques from linear mixed integer programming, from constraint programming, and from SAT solving. We will give an overview on the framework, its possibilities, and the algorithmic techinques used.
16:25Lingfeng Niu LSEC Experiments with nonlinear constraints in a MIP context
We consider the problem of scheduling the production of an open-pit mine with a single infinite-capacity stockpile. Modelled as a Mixed Integer Nonlinear Problem, we use nonlinear techniques to try to find global optimal solutions of the resulting subproblems. An auxiliary Mixed Integer Nonlinear Problem is solved to get the qualification for the the solution. Usually this method can be quicker than to use the linear relaxation directly, especially when required the solution satisfies the nonlinear constraints very well.
17:20Kshitij Kulshreshtha HU Berlin Structure Optimization with Flexible Frames
The talk concentrates on describing the modelling of a frame structure made of flexible elastic beams without the use of a discretization method like Finite Elements. Discretization methods involve a large number of variables and do not provide cheap derivative information for use with derivative based optimization. Our model reduces the number of variables considerably and is used in conjunction with algorithmic differentiation for design optimization.
17:55Stefan Körkel HU Berlin Mixed Integer Optimal Experiment Design
The modeling of dynamic processes leads to high-dimensional, nonlinear and stiff systems of differential equations. Usually these models contain parameters the values of which are not known. In order to obtain realistic simulations of the process behavior the model has to be validated.
Therefore the parameters are estimated by fitting the model to experimental data by the minimization of weighted least squares functionals, where the dynamic model equations appear as constraints. The uncertainty of the data causes an uncertainty of the parameter estimates which can be described the variance-covariance matrix, which is computed from sensitivities of the solution of the model equations w.r.t. the parameters.
An improvement of the significance of the parameter estimation can be achieved via the design of optimal experiments. This leads to the formulation of nonlinear optimal control problems. The variables thereby are quantities describing the layout of the experiments, the experimental conditions, the control of the processing, and the selection and placement of measurements. As objective function for optimum experimental design criteria on the variance-covariance-matrix are minimized. Special formulations result from multiple experiments and from the consideration of a-priori information from earlier experiments. The objective function can be modified in order to take uncertainties in the parameters into account.
To solve these nonstandard-optimal control problems, we apply the direct approach of optimal control. We apply SQP methods for the solution of the resulting nonlinear optimization problems. Special effort has to be made for the treatment of the intricate objective function.
The variables for the choice of measurements are binary variables. We use a relaxation combined with rounding heuristics to treat this mixed integer aspect of the problem. Our computations nevertheless show that even the results from the relaxation tend to be integer. This observation can be explained by a result from statistics.
In this talk we will discuss the numerical methods for the treatment of these problems, present the implemented software package and show the successful application of the methods to industrial problems.
18:30Andreas GriewankHU Berlin A continuous control formulation of the open pit mining planning problem
Given data about rock properties and mineral concentrations in a prospective open cut mine, the aim is to determine an excavation and processing schedule that optimizes the net present value. Currently this task is formulated and solved based on an a priori discretization into blocks of some 10-30 meters linear dimension. Recently, we have derived an alternative formulation as a continuos control problem and proved the existence of at least one local solution, of which there are typically several.
19:10EOT (End of talks)

Last Update 5.7.2007 by Thorsten Koch
© 2007 by Thorsten Koch, ZIB, Imprint