MINOS

Linear programming, unconstrained and constrained nonlinear optimization

Linear programming: A primal simplex method is used. A sparse LU factorization of the basis is maintained, using a Markowitz ordering scheme and Bartels-Golub updates as implemented in the LUSOL package of Gill, Murray, Saunders, and Wright.

Nonlinear objective, linear constraints: A reduced-gradient algorithm is used. This is an active-set method (a natural extension of the simplex method). The variables are classified as basic, superbasic, and nonbasic, with the number of superbasics indicating the effective nonlinearity of the objective. The constraints are satisfied before the objective is evaluated. Feasibility is maintained thereafter. Search directions are generated using a quasi-Newton approximation to the reduced Hessian.

Nonlinear constraints: A projected augmented Lagrangian algorithm is used. As in Robinson's method, each major iteration solves a linearly constrained subproblem to generate a search direction. The subproblem objective is an augmented Lagrangian function. The subproblem constraints are the true linear constraints plus linearizations of the nonlinear constraints. Convergence is usually achieved, although the steplength choice is heuristic. (A reliable merit function is not yet known.)

MINOS is designed to handle thousands of constraints and variables. Constraint data may be input from MPS files or via subroutine parameters. Nonlinearities are specified by Fortran subroutines. (Ideally these should provide both functions and gradients. Missing gradients are estimated by finite differences.) The GAMS and AMPL systems may be used as alternative user interfaces. See their entries for details.

MINOS is distributed on floppy disk. Fortran 77 source code is provided, along with test problems and makefiles for Unix, VMS and DOS systems.

One-time license fees for individual use are: $350 (academic or non-profit), $5000 (commercial, in-house). Department, Site and World licenses are also available.

Need more info?

Check out SOL Software Information, or contact SBSI:

Stanford Business Software, Inc.
2672 Bayshore Parkway, Suite 304
Mountain View, CA 94043
Phone: (415) 962-8719
Fax: (415) 962-1869

Reference:

B. A. Murtagh and M. A. Saunders, MINOS 5.4 User's Guide, Report SOL 83-20R, Systems Optimization Laboratory, Stanford University, December 1983 (revised February 1995).

Last revised 10/14/97.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]