CPNET SOFTWARE

SOFTWARE RELATED TO CPNET

PATH

The PATH solver applies techniques similar to those used in Newton methods for smooth systems to a nonsmooth reformulation of the MCP. The algorithm consists of a sequence of major iterations, each consisting of an approximation or linearization step (sometimes called successive LCP), the construction of a path to the Newton point (the solution to the approximation), and a possible search of this path. When the Newton point does not exist or the path cannot be entirely constructed, a step along the partially computed path is taken before the problem is relinearized. A nonmonotone watchdog strategy is employed in applying the path search; this helps avoid convergence to local minima of the norm function for the underlying nonsmooth equation and keeps the number of function evaluations required as small as possible.

The student version of PATH for linking with C, Fortran, Matlab, AMPL or GAMS is downloadable. To obtain a full version of the code please send mail to ferris@cs.wisc.edu

A description of the algorithm with some details on how to set options and the use of the methods can be obtained as:

Michael C. Ferris and Todd S. Munson: Complementarity Problems in GAMS and the PATH Solver.
(PDF file here) (abstract here)
Mathematical Programming Technical Report 98-12, September 1998.

Recent mathematical changes to the algorithm design are found in this report:

Michael C. Ferris, Christian Kanzow and Todd S. Munson: Feasible Descent Algorithms for Mixed Complementarity Problems. (abstract)
Mathematical Programming Technical Report 98-04, March 1998 (Revised November 1998).

An abstract of the original technical paper is available. The technical report version of the paper is available in postscript form. This paper appeared in Optimization Methods and Software 5, 123-156, 1995.

The following paper describes how PATH can be called from various other computing environments. Several of these are listed below. In particular, the downloadable student version of PATH mentioned above is documented in Interfaces to PATH 3.0: Design, Implementation and Usage. . (abstract) . (Computational and Applied Optimization 12: 207--227, 1999.)

PATH also has a variety of options to control the solution process and the amount of output produced. The default parameters are typically sufficient, but can be changed by the user if desired. A listing of some relevant option settings that affect the behaviour of PATH are described here. These are typically written into a file called path.opt.

AMPL

An AMPL (abstract)interface to complementarity codes is decribed in this paper. PATH is hooked up to AMPL using this interface. The link code is available on the WEB. You will additionally have to get a machine version of PATH library as mentioned above. You can try out the PATH solver under NEOS.

GAMS/MCP

PATH is hooked up a solver to GAMS. Contact sales@gams.com directly to obtain this code. Documentation about the options of PATH and how to run via GAMS is available. You can try out the PATH solver under NEOS.

MATLAB

MATLAB source and mex files are available, the required files are pathmcp.m and (the relevant MEX file) mcppath.*, (or pathlcp.m and lcppath.* for LCP's) . An alternative approach is to use the MATLAB/GAMS interface. Details on this can be found at MATLAB/GAMS interace.

NEOS Server for Complementarity

The NEOS Server currently offers the PATH algorithm for solving mixed complemen tarity problems. This code was developed at the University of Wisconsin by Steven Dirkse, Michael Ferris and Todd Munson. It is enhanced by the ADIFOR automatic differentiation tool, which calculates the derivatives automatically - you only have to supply a double precision FORTRAN subroutine to calculate the function values.

A postscript version of the documentation of this approach is available by anonymous ftp. You can try out the PATH solver under NEOS. All the user needs to provide to solve a mixed complementarity problem is the following:

The dimension of the problem;
A double precision FORTRAN routine to assign the initial point;
A double precision FORTRAN routine to assign the lower and upper bounds on the variables;
A double precision FORTRAN routine to evaluate the function.

MILES (Return to menu)

MILES is an extension of the classical Josephy-Newton method for NCP in which the solution to each linearized subproblem is computed via Lemke's almost-complementary pivot algorithm. This Newton point is used to define the Newton direction, which is then used in a damped linesearch. The merit function used measures both the violation in feasibility and in complementarity. MILES also employs a restart procedure in cases where the Newton point cannot be computed due to termination in a secondary ray. Every linearized subproblem is rescaled to equilibrate the elements appearing in the data of the subproblem.

SEMISMOOTH (Return to menu)

The SEMISMOOTH algorithm is based upon reformulating the NCP as a system of nonsmooth equations. The SEMISMOOTH algorithm implemented as a GAMS/MCP solver, using iterative solvers to improve performance on large scale problems. A description of an implementation is given at:

Todd S. Munson, Francisco Facchinei, Michael C. Ferris, Andreas Fischer and Christian Kanzow: The Semismooth Algorithm for Large Scale Complementarity Problems
(PDF file here) (abstract here)
Mathematical Programming Technical Report 99-06, June 1999.

Theoretical details can be found at:

Tecla De Luca, Francisco Facchinei and Christian Kanzow: A Theoretical and Numerical Comparison of some Semismooth Algorithms for Complementarity Problems
Mathematical Programming Technical Report 97-15, December 1997.

NE/SQP (Return to menu)

The NE/SQP algorithm is based upon reformulating the NCP as a system of nonsmooth equations. The NE/SQP algorithm implemented as a GAMS/MCP solver, its robustness improved using a proximal perturbation strategy giving the QPCOMP algorithm (abstract). The nonsmoothness of the equations is handled using directional derivatives of H.

SMOOTH (Return to menu)

The SMOOTH algorithm is based upon reformulating the NCP as a system of nonsmooth equations and then approximately solving a sequence of smooth approximations, which lead to a zero of the nonsmooth system (abstract here) . At each iteration, a smooth approximation to the original system is formed where the accuracy of the approximation is determined by the residual of the current point. This is implemented as a GAMS/MCP system.

Other Solvers (Return to menu)

Other solvers have been implemented as subsystems of GAMS and are compared in this paper. The abstract can be downloaded and the paper has appeared in the journal Computational Optimization and Applications.

Modeling Language Interfaces (Return to menu)

Solver Interface to GAMS

The technical report version of the paper is available in postscript form. An abstract of this paper is available.
This describes a library of routines that are available to help hook your solver to the GAMS/MCP modeling language. Contact steve@gams.com, rutherford@colorado.edu or ferris@cs.wisc.edu for further details.

Solver Interface to AMPL

The mechanism to hook up a solver to AMPL is available. Further details on the AMPL interface to complementarity codes is decribed in this paper. The abstract of this paper is available.
This describes the mechanism for writing complementarity constraints in an AMPL model, and gives results pertaining to a particular solver hooked up to AMPL for square complementarity problems. Contact 4er@iems.nwu.edu, dmg@lucent.com or ferris@cs.wisc.edu for further details.

MCPLIB: A Collection of Nonlinear Mixed Complementarity Problems (Return to menu)

An abstract of this paper is available. The technical report version of the paper is available in postscript form.
A complete version of the paper appeared in Optimization Methods and Software 5, 319-345, 1995. The collection of nonlinear mixed complementarity problems, problem descriptions, and how to access the GAMS source files for these problems are also available.

Complementarity Toolbox for MATLAB

An abstract of this paper is available. The technical report version of the paper is available in postscript form.
This (evolving) freely available toolbox consists of several mex and m-files. These also allow all the MCPLIB problems to be accessed from MATLAB without access to GAMS. The mex files give function evaluations and sparse Jacobian evaluations. Machine specific versions are available for version 4 and version 5. The PATH solver is also available in this toolbox, see details above.

Modified: September 2002 by ferris@cs.wisc.edu