tr-announce

Download

tr-announce@lists.rwth-aachen.de

November 2011

1 participants
2 discussions

2011-25: Compiler-Generated Subgradient Code for McCormick Relaxations
by Carsten Fuhs 27 Nov '11

27 Nov '11

The following technical report is available from http://aib.informatik.rwth-aachen.de: Compiler-Generated Subgradient Code for McCormick Relaxations Callum Corbett, Michael Maier, Markus Beckers, Uwe Naumann, Amin Ghobeity, Alexander Mitsos AIB 2011-25 McCormick Relaxations are special convex and concave under- and overestimators which are used in the field of nonconvex global optimization. As they are possibly nonsmooth at some points subgradients are used as derivative information. Subgradients are natural extensions of usual derivatives. They may be used to construct linear or piecewise linear relaxations. [Mitsos et al. 2009] developed a corresponding method and the library libMC (written in C++) for propagating relaxations and related subgradients using the tangent-linear mode of Algorithmic Differentiation (also known as Automatic Differentiation) by operator overloading. This report extends [Mitsos et al. 2009] by providing libMC functionality by source transformation in Fortran. The corresponding Fortran module modMC is described. A research prototype of the NAG Fortran compiler has been extended with domain-specific inlining techniques to enable the generation of tangent-linear McCormick code. Speedups by factors of up to four with respect to the runtime of the respective libMC-based implementation can be observed. These results are supported by a number of relevant applications. To perform the numerical experiments, an interface between tangent-linear McCormick code written in Fortran and the existing C++-implementation of the branch-and-bound algorithm has been established.

1 0

2011-24: Demonstration of a Branch-and-Bound Algorithm for Global Optimization using McCormick Relaxations
by Carsten Fuhs 27 Nov '11

27 Nov '11

The following technical report is available from http://aib.informatik.rwth-aachen.de: Demonstration of a Branch-and-Bound Algorithm for Global Optimization using McCormick Relaxations Callum Corbett, Uwe Naumann, Alexander Mitsos AIB 2011-24 This report is meant to demonstrate the actions performed by a branch-and-bound algorithm for global optimization on a simple minimization problem. McCormick relaxations are used to construct piecewise affine underestimators of the objective function.

1 0