ACCPM - Analytic Center Cutting Plane Method
ACCPM is a package for solving large scale convex optimization
problems. The code is an implementation of the cutting plane method.
Instead of solving every relaxed master problem to optimality (as is the
case in classical decomposition approaches), ACCPM looks for an analytic
center of the current localization set. The projective algorithm
is successfully applied for this purpose.
The code can be licensed for academic purposes. Check what to do to
get ACCPM library.
The theoretical development of the ACCPM started from the paper:
- Goffin J.-L. and J.-P. Vial, Cutting planes and column generation
techniques with the projective algorithm, Journal of Optimization Theory
and Applications 65 (1989) 409-429.
and was continued in:
- Goffin J.-L., A. Haurie, and J.-P. Vial, Decomposition
and nondifferentiable optimization with the projective algorithm, Management
Science 38, 2 (1992) 284-302.
- Goffin J.-L., A. Haurie, J.-P. Vial, and D.L. Zhu, Using central
prices in the decomposition of linear programs, European Journal of
Operational Research 64 (1993) 393-409.
An early (Matlab) implementation of the method was written by Olivier Bahn
and Olivier du Merle. Later on, a prototype C code was developed by Olivier
du Merle and successfully applied to solve nontrivial convex optimization
- Bahn O., O. du Merle, J.L. Goffin and J.P. Vial, A cutting plane
method from analytic centers for stochastic programming, Mathematical
Programming, 69 (1995) 45-73.
- Bahn O., J.L. Goffin, J.P. Vial and O. du Merle, Implementation
and behavior of an interior point cutting plane algorithm for convex
programming: an application to geometric programming, Discrete Applied
Mathematics 49 (1994) 3-23.
- du Merle O., Interior points and cutting palnes:
development and implementation of methods for convex optimization and large
scale structured linear programming, Ph.D Thesis, Department of Management
Studies, University of Geneva, Geneva, Switzerland, 1995 (in French).
The success of this prototype code, justified the effort to develop a state of
the art general purpose implementation of the method. Its new variant has been
written in C++ by Jacek Gondzio, Olivier du Merle and Robert Sarkissian. The
new code has already been applied to solve different large scale optimization
problems, see, e.g.:
- Goffin J.-L., J.Gondzio, R. Sarkissian and J.-P. Vial,
Solving nonlinear multicommodity flow problems by the analytic center
cutting plane method, Mathematical Programming 76 (1996) 131-154.
TR 1994.21 (PS file).
- J.Gondzio, R. Sarkissian and J.-P. Vial, Using an interior
point method for the master problem in a decomposition approach,
European Journal of Operational Research 101 (1997) 577-587.
TR 1995.30 (PS file).
- Lisser A., R. Sarkissian and J.-P. Vial,
Survivability in telecommunication networks, Technical
Report 1995.3 Department of Management Studies, University of Geneva,
Switzerland, March 1995.
- Lisser A., R. Sarkissian and J.-P. Vial, Optimal
joint synthesis of base and reserve telecommunication networks, Technical
Report 1995.??, Department of Management Studies, University of Geneva,
Switzerland, October 1995.
It is our intention to make the ACCPM library available upon request to any
research application. The reader intereseted in such a use should contact
Jean-Philippe Vial: firstname.lastname@example.org. The library libaccpm.a
was released in January 1996.
The following papers address practical use of the ACCPM library:
- Gondzio J. and O. du Merle, Analytic Center
Cutting Plane Method - User's Guide for the Library, Technical Report
1995.33, Department of Management Studies, University of Geneva, Switzerland,
- Gondzio J., O. du Merle, R. Sarkissian and J.-P. Vial,
ACCPM - A Library for Convex Optimization Based on an Analytic Center
Cutting Plane Method,
European Journal of Operational Research, 94 (1996) 206-211.
TR 1995.34(PS file).
The research on ACCPM is being continued. The most recent progress
is documented in the following papers:
Parallel version of ACCPM has been developed. For portability reasons
it uses MPI for parallel communication; it has been run on SP2 machine
of IBM and on a cluster of 10 Linux PC's: