Optimisation Software

John M. Sullivan (TU Berlin) (14:00 - 14:20 )

Surface Evolver

Konrad Polthier (ZIB), Klaus Hildebrandt (ZIB) (14:20 - 14:40 )

Surface optimization and feature extraction

Rene Henrion (WIAS) (14:40 - 15:00 )

Calculating values and gradients of polyhedral chance constraints

Many applications in engineering sciences or mathematics of finance leed to optimization problems with probabilistic or chance constraints. These allow to model inequalities which are effected by random parameters.

The talk presents a solution approach to a special type of frequently encountered chance constraints. The main numerical difficulty occurs when the number of inequalities exceeds the dimension of the random vector. Even if the latter has a regular normal distribution, the mentioned situation will inevitably lead to the consideration of singular normal distirubtions.

Our approach relies on an inclusion exclusion formula for polyhedra which allows to get back to regular distributions again. The numerical solution procedure combines Fukuda's Scdd+ - code for corner determination of polyhedra with efficient codes for evaluating regular normal distributions (e.g., Genz, Szantai).

We demonstrate the advantages of our method - which are striking in problems of moderate size - by comparison with competing methods (e.g. crude Monte Carlo, Deak's code for the probability of convex sets, Genz' code for singular normal distributions by numerical integration). A corresponding implementation as a software tool is under development.
Download talk (PDF)

Andreas Rathsfeld (WIAS), J.Elschner (WIAS), G.Schmidt (WIAS) (15:00 - 15:20 )

Optimisation of diffraction gratings with DIPOG

Many modern optical devices include diffractive optical elements. Clearly, the optimization of their performance is an important task.
The program package DIPOG provides fast and rigorous simulation tools for optical gratings based on the approximation of Maxwell's equations by FEM.

Additionally, DIPOG is also able to optimize the geometrical shape of binary gratings, i.e., of gratings composed of rectangular blocks. The optimization routines are based on local gradient methods like Projected Conjugate Gradient Methods or Interior Point Methods.

The gradients expressed as a function of Maxwell solutions are computed by FEM. Currently, we extend these algorithms to cover optimal design problems for general polygonal shapes.
Download talk (PDF)

Thorsten Koch (ZIB) (15:50 - 16:10 )

Soplex (Simplex based LP Solver) and ZIMPL (Modeling language)

SoPlex is an implementation of the revised simplex algorithm. It features primal and dual solving routines for linear programs, i.e., min c^T x subject to Ax <= b, x >= 0, and is implemented as a C++ class library that can be used with other programs. An example program to solve standalone linear programs given in .mps or .lp format files is also included.
Zimpl is a little language to translate the mathematical model of a problem into a linear or (mixed-) integer mathematical program expressed in .lp or .mps file format which can be read and (hopefully) solved by a LP or MIP solver, for example, SoPlex (LP) and SCIP (MIP).
Download talk (PDF)

Tobias Achterberg (ZIB) (16:10 - 16:30 )

Solving Constraint Integer Programs (SCIP)

The software package SCIP is a solver and a framework for Constraint Integer Programming. It integrates solving techniques from the two fields "Constraint Programming" and "Mixed Integer Programming".
Mixed Integer Programming originated in the OR community. A Mixed Integer Program (MIP) is an optimization problem with linear objective function and linear constraints. Additionally, some or all of the variables may be restricted to integral values. These integrality conditions render the problem NP hard. For solving MIPs, one usually applies a branch-and-bound algorithm in which the problem is successively divided into smaller subproblems. For each subproblem, the LP relaxation is solved (and possibly strengthened by so-called cutting planes) in order to generate a dual bound.
Constraint Programming originated in the AI community. Constraint Programs (CPs) are much more general than MIPs. Both, the objective function and the constraints may be non-linear. If the domains of the variables are finite, a CP can be solved by (implicitly) enumerating all potential solutions, similar to the branch-and-bound algorithm for MIPs. In contrast to MIP solvers, which rely on the LP relaxation, CP solvers employ so-called domain propagation in the subproblems to deduce additional restrictions on the variables' domains and thereby pruning the search tree.
SCIP is oriented towards the needs of Mathematical Programming experts who want to have total control of the solution process and access detailed information down to the guts of the solver. It has the following features:

• framework for branching, cutting, pricing and propagation
• multi LP solver support through an LP interface
• highly flexible through many possible user extensions:
  • constraint handlers to implement arbitrary constraints
  • separators to apply cutting planes on the LP relaxation
  • pricers to dynamically generate problem variables
  • domain propagators to reduce the variables' domains
  • primal heuristics
  • node selectors to guide the search
  • branching rules to split the problem into subproblems
  • relaxators to incorporate relaxations additional to the LP relaxation (e.g. SDP)
  • presolvers to simplify the solved problem
  • file readers to understand different input file formats
  • event handlers to get informed each time a node was solved, a specific variable changed its bounds, a new solution was found, ...
• every existing unit is implemented as a user extension, leading to an interface flexible enough to meet the needs of most additional user extensions
• simple preprocessing shell w.r.t. variables: the user may mix preprocessed and active problem variables arbitrarily in any expression
• cut pool management
• arbitrarily many children per node (arbitrary branching)
• possibility to solve or not to solve the LP relaxation at each single node
• conflict analysis to learn from infeasible subproblems

Ivo Nowak, Lufthansa Systems Berlin (16:30 - 16:50 )

LaGO - A solver for mixed integer nonlinear programs

In this talk we give a short overview of the Lagrangian Global Optimizer (LaGO), which solves general mixed integer nonlinear programs.

We will describe the basic optimization tools and present numerical results.
Download talk (PDF)

Steffen Weider (LBW) (16:50 - 17:10 )

Bundlemethods

In this talk we present a bundle method to solve unconstrained convex minimization problems. This bundle method also provides primal information for Lagrangean relaxations of linear programs and can therefore be used as a fast replacement of a simplex solver, if accuracy of the solution is not crucial. We will outline how the algorithm works and show some applications of our bundle method.
Download talk (PDF)

Jan Riehme (HU), Andreas Griewank (HU Berlin & Matheon) (17:30 - 17:50 )

Software for Evaluating Derivatives of Programs

Software for solving nonlinear optimization problems typically expects the user to provide routines for evaluating objectives and constraints as well as their first derivatives. When first derivatives are not provided, most solvers resort to divided difference approximations, a rather crude approach which severely limits efficiency and solution accuracy. A rather tedious task for the user is also the specification of the sparsity patterns of derivative matrices. Many rather academic problems have now been specified in AMPL, GAMS or another modeling environment, where gradients and even Hessians are available without any significant effort to the user.

On the other hand many industrial practicioners resort to derivative free search methods or abstain from systematic optimization alltogether, because their models appear too complicated for the evaluation of derivatives. While some obstacles like heterogenous and proprietory codes are certainly serious, others can be overcome with the help of algorithmic differentiation software and some user training. The key assumption remains to date that the problem functions are provided as source code in a Fortran or C variant.

We present two of the most important tools for these programming languages and discuss small examples. Finally we show briefly, how checkpointing techniques can be used to solve time dependent problems efficiently.
Download talk (PDF)

Tobias Gaenzler (ZIB) (17:50 - 18:10 )

Function space interior point methods in KASKADE

The finite element software KASKADE and its commercial counterpart JCMsolve were primarily designed for the solution of partial differential equations in 1D, 2D and 3D. Types of PDE's which can be solved include Maxwell's equations, static convection-diffusion, linear elasotomechanics and timeharmonic Helmholtz problems.
Recently KASKADE has been extended to solve PDE-constrained optimization problems with a convex objective and bound constraints on the control u and the state y.
In this talk we will present the software and how the optimization problem is solved by function-space interior point methods.
Download talk (PDF)

Marc Steinbach (ZIB) (18:10 - 18:30 )

Modular codes for NLP, QP, and KKT systems

The talk describes research codes that have been developed for solving quadratic and nonlinear programs, particularly in the areas of discretized multistage stochastic programs and DAE boundary value problems.

The codes include an SQP method, an Interior Point Method for QP, and various special solvers for structured KKT systems, or meta-solver in the case of multi- stage stochastic programs. They also include a convenient C/C++ interface to the BLAS and LAPACK libraries.
Download talk (PDF)