Software for Optimization:
A Survey of Trends in Mathematical Programming Systems
for Operations Research and Management Science

by Robert Fourer

OR/MS Today, December 1998, pages 40-43.

This page provides a variety of links and references keyed to the above-cited article.  Since no listings in this area can be complete or correct for long, suggestions for additions and corrections are welcome.  They may be sent to the author at 4er@iems.nwu.edu.

Last updated December 29, 1998.
 

Solvers

Linear & integer programming:  For lists of large-scale linear and integer programming codes, see question 2 of the LP FAQ. and the OR/MS Today Linear Programming Software Survey.  Many developers and distributors of optimization software also advertise in OR/MS Today.

Constraint programming:  For general information and availability of software, see the Constraints Archive maintained by Peg Eaton.  The following include discussions of various interactions between solvers for constraint programming and integer programming:
 

• J.N. Hooker and M.A. Osorio, Mixed Logical/Linear Programming, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (June 1997).
• T. Hurlimann, An Efficient Logic-to-IP Translation Procedure, Institute of Informatics, University of Fribourg, Fribourg, Switzerland (March 1998).

ILOG Planner brings together commercial constraint programming and linear programming solvers, which it can apply cooperatively to solve problems that mix linear and combinatorial constraints on continuous and integer variables. Hybrids that combine commercial software for constraint programming with established branch-and-bound procedures for mixed-integer optimization are under development by Dash/Cosytec and by ILOG/CPLEX.

Specialized discrete optimization software:  "One can find good packages, for example, that are dedicated to network problems (GIDEN), or logistics problems (CAPS Logistics Toolkit), or vehicle routing problems (LogicRoute), or even school-bus routing problems (BUSTOPS)."  The OR/MS Today Vehicle Routing Software Survey lists 20 different packages.

Stochastic programming:  See question 6.12 of the LP FAQ, and the NEOS Guide introduction to stochastic programming.  There is also an extensive Stochastic Programming Bibliography.  One recent survey is Introduction to Stochastic Programming by John R. Birge and Francois Louveaux (Springer Verlag, 1997). Among commercial systems, IBM's Stochastic Solutions and Optimization Library Stochastic Extensions provide particularly extensive features for setting up and solving multi-stage stochastic optimization problems.

Complementarity problems:  See the Complementarity Problem Net pages.

Interior-point methods for nonlinear programming.  Papers that describe recent experiments in this area can be found by searching for "nonlinear" in the Interior Point Archive.  You can download an evaluation copy of LOQO that supports general convex optimization through a modeling language interface.

Semidefinite programming:   Christoph Helmberg's semidefinite programming page provides an extensive list of references and software in this area.

Global optimization:  Arnold Neumaier's global optimization site links to papers and codes for global optimization of many kinds.

Modeling Systems

General information:  Optimization modeling systems are listed along with solvers in question 2 of the LP FAQ. and in the OR/MS Today Linear Programming Software Survey.  Many of these systems can express a range of optimization problem types beyond linear programming.  The principal commercial systems are frequently advertised in OR/MS Today.

Application development:  AIMMS has the most extensive built-in application development tools among optimization modeling systems.  OPL Studio optionally converts a model description from the OPL modeling language to C++ code that can be embedded in an application.  EMOSL is a subroutine library that enables an application to access XPRESS-MPs modeling routines as well as its solving routines.

Modeling language extensions:  Newly available modeling language features that support recent advances in solvers include:
 

• Concise descriptions of complementarity constraints, in AMPL.
• Extended constraint forms and search directives for support of constraint logic programming, in OPL Studio.
• Computation of second derivatives by automatic differentiation of objective and constraint functions, in AMPL.

Analysis of optimization problems:  ANALYZE was a pioneer in the analysis of large linear programs.  MProbe offers a range of analysis tools for nonlinear objectives and constraints expressed in a modeling language.  Infeasibility analysis through routines for extracting an irreducible infeasible subset of constraints is provided as an option of many solvers, including CPLEX, LINDO, LS-XLSOL, OSL, and XPRESS-MP.

Remote Execution
 
The following list of on-line sources of optimization services is adapted from listings in the LP FAQ and NLP FAQ.
 

• AMPL. A convenient interface supports experimentation with the AMPL modeling language on test problems up to 300 variables and 300 constraints + objectives. Users can request any example from the AMPL book, or provide their own model, data and execution script by cut-and-paste or from local files. There is a choice among 8 solvers for linear, nonlinear, and mixed integer programs and complementarity problems.

 
• DecisionNet. Provides access to "a distributed collection of decision technologies," including linear programming, "that are made available for execution over the World Wide Web. These technologies are developed and maintained locally by their providers. DecisionNet contains technology metainformation necessary to guide consumers in search, selection, and execution of these technologies." Facilities for submitting problems in popular modeling language formats are currently being tested.

 
• GIDEN. An interactive graphical environment for a variety of network optimization problems and algorithms. It is written in Java, so you can try it out through any Java-enabled Web browser.

 
• IBM Optimization Subroutine Library (OSL). Linear and quadratic programs in MPS format may be submitted by anonymous ftp.

 
• Internet Enabled HQP Optimization Service. Problems in the nonlinear SIF format may be submitted by e-mail.

 
• LPL by Tony Hürlimann.  Problems may be submitted, through a web form or from a local file, in the LPL modeling language.  Models in LPL may contain logical constraints, which are translated symbolically into constraints using 0-1 variables.

 
• MILP by Dmitry V. Golovashkin. Small-scale mixed-integer programs in a simple algebraic format are solved through a web form interface.

 
• Network-Enabled Optimization System (NEOS) Server. Offers access to about a dozen solvers for linear and integer programming as well as various nonlinear optimizationproblems.

 
• Linear and integer programs in MPS format may be submitted by sending e-mail, by submitting URLs through a Web page, or via a high-speed socket-based Unix interface.  (Submissions from local files are coming soon.)
• Linear and integer programs in the AMPL modeling language can also be sent to some of the solvers using AMPL Remote Access via e-mail, URL, or a NEOS "client" program invoked from a local AMPL session.
 
• NIMBUS. A nondifferentiable multiobjective optimization system that accepts algebraic problem specifications through a series of Web forms.

 
• Numerica. Global nonlinear optimization problems may be submitted in Numerica's algebraic modeling language. The web form interface makes it easy to do a series of runs, changing the model or data incrementally.

 
• UniCalc. A variety of nonlinear optimization problems may be submitted in UniCalc's algebraic modeling language, through a web form interface.