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 problems:

• 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: jpvial@uni2a.unige.ch. 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, December 1995.

• 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:

• J.-P. Vial, A generic path-following algorithm with a sliding constraint and its application to linear programming and the computation of analytic centers, Technical Report 1996.8, Department of Management Studies, University of Geneva, Switzerland, February 1996.

• O. du Merle, J.L. Goffin and J.P. Vial, On the Comparative Behavior of Kelley's Cutting Plane Method and the Analytic Center Cutting plane Method, Technical Report 1996.4, Department of Management Studies, University of Geneva, Switzerland, March 1996.

• J.-L. Goffin and J.-P. Vial, Shallow, deep and very deep cuts in the analytic center cutting plane method, Logilab Technical Report 96.1, Department of Management Studies, University of Geneva, Switzerland, May 1996.

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:

• J. Gondzio, R. Sarkissian and J.-P. Vial, Parallel implementation of a central decomposition method for solving large scale planning problems, HEC Technical Report 1998.1, Department of Management Studies, University of Geneva, Switzerland, January 1998.

• E. Fragniere, J. Gondzio and J.-P. Vial, A planning model with one million scenarios solved on an affordable parallel machine, HEC Technical Report 1998.11, Department of Management Studies, University of Geneva, Switzerland, June 1998.