LOGARITHMIC BARRIER DECOMPOSITION METHODS FOR
D.Haglin, J. Kaliski, C. Roos, T. Terlaky
A computational study of some logarithmic barrier decomposition
algorithms for semi--infinite programming is presented in this paper. The
conceptual algorithm is a straightforward adaptation of the logarithmic
barrier cutting plane algorithm which was presented recently by den Hertog
et al., to solve semi-infinite programming problems.
Usually decomposition (cutting plane methods) use cutting planes to improve
the localization of the given problem. In this paper we propose an extension
which uses linear cuts to solve large scale, difficult real world problems.
This algorithm uses both static and (doubly) dynamic enumeration of the
parameter space and allows for multiple cuts to be simultaneously added for
The algorithm is implemented both on sequential and parallel computers.
Implementation issues and parallelization strategies are discussed and
encouraging computational results are presented.
Key Words: column generation, convex programming, cutting plane
methods, linear programming, quadratic programming, interior point method,
logarithmic barrier function, semi--infinite programming.
Delft University of Technology,
P.O.Box 5031, 2600 GA, Delft, The Netherlands