 |
[ Home | Support | Sales | Solvers | Documentation | Model Libraries | Search | Contact Us ] |
|---|
|
GAMS/AlphaECP is a MINLP (Mixed-Integer Non-Linear Programming) solver based on the extended cutting plane (ECP) method. The solver can be applied to general MINLP problems and global optimal solutions can be ensured for pseudo-convex MINLP problems.
The ECP method is an extension of Kelley's cutting plane method which was originally given for convex NLP problems (Kelley, 1960). The method requires only the solution of a MIP sub problem in each iteration. The MIP sub problems may be solved to optimality, but can also be solved to feasibility or only to an integer relaxed solution in intermediate iterations. This makes the ECP algorithm efficient and easy to implement. Futher information about the underlying algorithm can be found in Westerlund T. and Pörn R. (2002). Solving Pseudo-Convex Mixed Integer Optimization Problems by Cutting Plane Techniques. Optimization and Engineering, 3. 253-280.
BARON (Branch-And-Reduce Optimization Navigator) is a computational system for solving non convex optimization problems to global optimality. Purely continuous nonlinear programs (NLPs), purely integer, and mixed-integer nonlinear programs (MINLPs) can be solved with the software.
BARON combines constraint propagation, interval analysis, and duality for efficient range reduction with rigorous relaxations constructed by enlarging the feasible region and/or underestimating the objective function.
Parts of BARON were created at the University of Illinois at Urbana-Champaign. The software is currently developed by Nick Sahinidis and Mohit Tawarmalani.
Schematic GAMS/BARON Connection Diagram
Local Versus BARON for Pooling Problems
BDMLP is the LP and MIP solver that comes for free with any GAMS system: it is part of the GAMS/BASE module.
BDMLP was originally developed at the World Bank by T. Brooke, A. Drud and A. Meeraus (hence its name) and is now maintained by GAMS Development Corp. The MIP part was added by M. Bussieck and A. Drud. The BDMLP solver is suited for small to medium sized problems.
GAMS/BDMLP can solve reasonably sized LP models, as long as the models are not very degenerate and are well scaled. The Branch-and-Bound algorithm for solving MIP is not in the same league as other commercial MIP codes that are hooked up to GAMS. Nevertheless, the MIP part of GAMS/BDMLP provides free access to a MIP solver that supports all types of discrete variables supported by GAMS: Binary, Integer, Semicont, Semiint, Sos1, Sos2.
For large problems we recommend to look at some of the commercial LP/MIP solvers (GAMS/CPLEX, GAMS/XA or GAMS/XPRESS).
BENCH comes free with any GAMS system. Licensing is dependent on licensing of the subsolvers. Thus, BENCH runs all solvers for which the user has a valid license.
The COIN-OR project (COmputational INfrastructure - Operations Research) is an initiative to spur the development of open-source software for the operations research community. GAMS has added a link to the solvers in COIN-OR.
The GAMS/COIN-OR Link for LP, NLP and MIP problems is available in source and free of charge with any licensed GAMS system. Potentially all solvers connected to the COIN-OR/Open Solver Interface (OSI) can be made available through the GAMS/COIN-OR link. As of GAMS Distribution 22.5 (2007), available solvers include:
For more information see the
GAMS/CONOPT is an alternative solver to MINOS and other non linear problem (NLP) solvers available for use with GAMS. The availability of multiple nonlinear solvers in the GAMS system should be seen as an attempt to increase the overall usefulness of nonlinear modeling with GAMS. CONOPT, developed by ARKI Consulting and Development in Denmark, is a multi-method solver. CONOPT and the other GAMS NLP solvers often complement each other. If one solver fails, one of the others will often be able to solve the model. If all solvers fail it is a good indication that the model is very difficult or very poorly scaled, and manual intervention from an experienced modeler is necessary.
The GAMS system contains multiple versions of CONOPT. Currently, the older CONOPT1, the proven CONOPT2 as well as the new CONOPT3 with some new algorithmic features are part of the GAMS system. The generic solver name CONOPT is an alias to the most reliable production version of GAMS/CONOPT (currently CONOPT3).
All CONOPT versions are being distributed in one package under a common license. Although the latest version is generally faster than an older one, there are still some cases where the older one dominates. In these cases users can select the specific version of CONOPT by adding the version number to the solver name (e.g. OPTION NLP=CONOPT1).
| Performance Profiles: | CONOPT1, CONOPT2, CONOPT3 on Cops Models |
| CONOPT3 default, without SQP, without SQP and without SLP |
GAMS can now compute exact second derivatives and this is used in our new CONOPT3 solver. Second derivatives can have a significant effect on highly nonlinear models and especially on models with many superbasic variables. Many previously unsolvable models can now be solved.
CONOPT3 is a multi-method solver with the following sub-methods (in addition to those of CONOPT2 mentioned below):
The inner workings of most components of the solver have been improved, since the release of CONOPT1, and several new algorithmic features have been added.
CONOPT and CONOPT2 are products of ARKI Consulting and Development:
CONVERT is a utility which transforms a GAMS model instance into formats used by other modeling and solution systems. CONVERT is designed to achieve the following goals:
GAMS/CPLEX is a powerful Linear Programming (LP), Mixed-Integer Programming (MIP), Quadratically Constraint Programming (QCP) and second order cone programs, and Mixed-Integer Quadratically Constraint Programming (MIQCP) solver based on the Cplex Callable Library from the ILOG CPLEX Division. It includes state-of-the-art implementations of simplex and barrier algorithms and runs on many different platforms. For solving LP models, the following algorithms are available:
CPLEX has proved to be a very stable LP solver, and the default settings are almost always sufficient to get an optimal solution with excellent solution times. For the cases where the end-user wants to set algorithmic options to improve performance, GAMS/CPLEX provides access to all the CPLEX tuning parameters through an option file. A presolver and aggregator can be invoked to reduce the size of the model before actually solving it.
The MIP algorithm is an implementation of a branch-and-bound search with modern algorithmic features such as cuts and heuristics. The MIP optimizer solves large and numerically difficult MIP models. Features include settable priorities on integer variables, choice of different branching, and node selection strategies.
GAMS/CPLEX comes in the following versions:
In addition if you have a callable library license from Cplex, we offer a GAMS/CPLEX link at a reduced price. This is the same program as the GAMS/CPLEX solver, but it uses your existing Cplex callable library license. It is noted that the link does not work on the CPLEX stand alone license.
GAMS/DECIS requires the availability of a GAMS/MINOS or a GAMS/CPLEX license.
DICOPT is a framework for solving MINLP (Mixed Integer Nonlinear Programming) models.
GAMS/DICOPT is based on methodology developed at the Chemical Engineering Department of CMU by the group of Prof. Ignacio Grossmann.
GAMS/DICOPT uses a standard GAMS MIP and NLP solver to solve the MIP and NLP subproblems generated by the algorithm. This means that in order to use DICOPT you will need to have a GAMS MIP solver (e.g. GAMS/CPLEX, GAMS/XA or GAMS/XPRESS) and a GAMS NLP solver (e.g. GAMS/CONOPT, GAMS/MINOS or GAMS/SNOPT).
GAMS/EXAMINER is a tool for examining points and making an unbiased, independent assessment of their merit. In short, it checks if solutions are really solutions. As an example, it can take a solution point reported as optimal by a solver and examine it for primal feasibility, dual feasibility, and optimality. It has a number of different modes, allowing it to check the input point from GAMS/BASE as well as the solution passed by a solver back to GAMS.
Many of the tests done by EXAMINER (indeed, perhaps all of them) are already being done by the GAMS solvers, so EXAMINER is in a sense redundant. However, a facility to make an independent, transparent check of a solver's solution is very useful in solver development, testing, and debugging. It is also useful when comparing the solutions returned by two different solvers. Finally, a tool like the EXAMINER allows one to examine solutions using different optimality tolerances and optimality criteria in a way that is not possible when working with the solvers directly.
GAMS/EXAMINER is installed automatically with your GAMS system. Without a GAMS/BASE license, EXAMINER will run in student or demonstration mode (i.e. it will examine small models only).
The GUROBI (Gurobi Optimization, Inc) suite of optimization products include state-of-the-art simplex-based linear programming (LP) and mixed-integer programming (MIP) capability.
The Gurobi MIP solver includes shared memory parallelism, capable of simultaneously exploiting any number of processors and cores per processor. The implementation is deterministic: two separate runs on the same model will produce identical solution paths.
KNITRO (Ziena Optimization, Inc) is a software package for finding local solutions of continuous, smooth nonlinear optimization problems, with or without constraints. Even though KNITRO has been designed for solving large-scale general nonlinear problems, it is effcient for solving all of the following classes of smooth optimization problems:
The KNITRO package provides the following features:
KNITRO implements both state-of-the-art interior-point and active-set methods for solving nonlinear optimization problems.
The LGO solver integrates algorithms of global and local scope. It serves to analyze and solve complex nonlinear models, under minimal analytical assumptions. In order to use LGO, only computable function values are required, without a need for gradient or higher order information.
LGO can be used in several search modes, providing a robust, effective, and flexible solver suite approach to a broad range of nonlinear models. The solver suite approach increases the reliability of the overall solution process.
LGO Solver Components
LGO has been successfully applied even to highly complex, 'black box' system models. Tractable model sizes depend only on the available hardware, although LGO has a 3000 variable, 2000 constraint size limit.
Illustrative Application Areas
GAMS/LGO Nonlinear Solver Suite: Key Features, Usage, and Numerical Performance
Nonlinear Optimization with GAMS/LGO (2006)
An illustrative global optimization model displayed in Excel
An illustrative global optimization model displayed in MATLAB
LGO is a product of Pintér Consulting Services, Inc.
LINDOGlobal finds guaranteed globally optimal solutions to general nonlinear problems with continuous and/or discrete variables.
The LINDO global optimization procedure (GOP) employs branch-and-cut methods to break an NLP model down into a list of subproblems. Each subproblem is analyzed and a) is shown to not have a feasible or optimal solution, or b) an optimal solution to the subproblem is found, e.g., because the subproblems is shown to be convex, or c) the subproblem is further split into two or more subproblems which are then placed on the list. Given appropriate tolerances, after a finite, though possibly large number of steps a solution provably global optimal to tolerances is returned. Traditional nonlinear solvers can get stuck at suboptimal, local solutions. This is no longer the case when using the global solver.
MILES is the MCP (Mixed Complementarity Problem) solver that comes for free with any GAMS system: it is part of the GAMS/BASE module.
MILES is developed by Prof. Thomas Rutherford of the University of Colorado at Boulder.
MCP models can be formulated directly in GAMS, but are also often generated from the MPSGE general equilibrium modeling environment.
GAMS/MINOS is the oldest NLP solver available with GAMS and it is still the NLP solver that is used the most. MINOS has been developed at the Systems Optimization Laboratory at Stanford University, and development is continuing today. Linearly constrained models are solved with a very efficient and reliable reduced gradient technique, that utilizes the sparsity of the model. Models with nonlinear constraints are solved with a method that iteratively solves subproblems with linearized constraints and an augmented Lagrangian objective function. This iterative scheme implies that only the final optimal solution is feasible for nonlinear models, in contrast to the feasible path method used by our other large scale NLP solver, CONOPT.
MINOS and CONOPT are very complementary to each other as they employ very different algorithms. To encourage users to have both NLP solvers available an NLP package consisting of GAMS/MINOS and GAMS/CONOPT is available with a 25% discount.
MOSEK is a software package for the solution of linear, mixed-integer linear, and convex nonlinear mathematical optimization problems. MOSEK is particularly well suited for solving large-scale linear programs using an extremely efficient interior point algorithm. The interior point algorithm has many complex solver options which the user can specify to fine-tune the optimizer for a particular model.
Furthermore, MOSEK can solve generalized linear programs involving nonlinear conic constraints and convex nonlinear programs.
These problem classes can be solved using an appropriate optimizer built into MOSEK. All the optimizers available in MOSEK are built for the solution of large-scale sparse problems. Current optimizers include:
Quadratic Conic Constraint Space
MPSGE is a mathematical programming system for general equilibrium analysis which operates as a subsystem within GAMS. MPSGE is essentially a library of function and Jacobian evaluation routines which facilitates the formulation and analysis of AGE models. MPSGE simplifies the modeling process and makes AGE modeling accessible to any economist who is interested in the application of these models. In addition to solving specific modeling problems, the system serves a didactic role as a structured framework in which to think about general equilibrium systems.
MPSGE requires the GAMS/BASE Module including the MILES MCP solver. Optionally it can use the PATH MCP solver.
MSNLP (Multi-Start NLP) is another stochastic search algorithm from Optimal Methods, Inc for global optimization problems. Like it's bigger brother OQNLP, MSNLP uses a point generator to create candidate starting points for a local NLP solver. Algorithm performance depends strongly on the starting point generator. MSNLP implements a generator creating uniformly distributed points and the Smart Random Generator. This generator uses an initial coarse search to define a promising region within which random starting points are concentrated. Two variants of Smart Random are currently implemented, one using univariate normal distributions, the other using triangular distributions.
MSNLP also comes with the local NLP solver LSGRG and is available as part of the Global Packages.
It is well known that many reformulations of an MPEC model as a standard NLP model or as a parameterized sequence of NLP models exist. Some of these reformulations have been around for decades, others are quite recent. Given an MPEC model, it is likely that there exists a reformulation strategy and NLP solver that will find an MPEC solution. Unfortunately, it is not always clear a priori what that reformulation strategy is, and manual experiments with different reformulations are very time-consuming.
The NLPEC solver automates the process of model reformulation. NLPEC reformulates the original MPEC as an NLP (using one of 23 different reformulation strategies), solves the resulting NLP, and translates the results back for return as an MPEC solution. Some of the reformulations involve a parameterized sequence of NLP models, with a penalty parameter going to zero; this sequence of models is constructed and run by NLPEC. A number of options exist to influence the initial points used by the NLP solvers and the construction of the NLP sequence in the case of parameterized NLP models.
Schematic GAMS/NLPEC Connection Diagram
Probability of Success for Different NLP Solver/Reformulation Combinations
OQNLP, from Optimal Methods and OptTek Systems, Inc., is a solver for global optimization of smooth constrained problems with either all continuous variables or a mixture of discrete and continuous variables. It starts any GAMS NLP solver from a set of starting points chosen by the widely used Scatter Search software, OptQuest. It can also be used to solve any NLP problem where solver failures are common, by automating the process of choosing multiple starting points.
OQNLP can also improve the reliability of any NLP solver, by calling it from many starting points. If you have a problem where you think the current NLP solver is failing to find even a local solution, choose an NLP solver and a limit on the number of solver calls, and try OQNLP. Even if a single call to the solver fails, multiple calls from the widely spaced starting points provided by OQNLP have a much better chance of success.
Often an NLP solver fails when it terminates at an infeasible solution. Then, the user is not sure if the problem is really infeasible or if the solver is at fault (if all constraints are linear or convex the problem is probably infeasible). OQNLP can help in such cases. To use it, the problem can be solved in its original form, and some solver calls may terminate with feasible solutions. OQNLP will return the best of these. If all solver calls terminate infeasible, the problem can be reformulated as a feasibility problem. That is, introduce "deviation" or "elastic" variables into each constraint, which measure the amount by which it is violated, and minimize the sum of these violations, ignoring the true objective. OQNLP can be applied to this problem, and it has a much better chance of finding a feasible solution (if one exists) than a single call to a solver does. If no feasible solution is found, you have much more confidence that the problem is truly infeasible.
OQNLP also comes with the local NLP solver LSGRG. A license for OQNLP also enables the use of OQNLP's little brother MSNLP.
Schematic GAMS/OQNLP Connection Diagram
Performance Profile - Local Solvers with and without OQNLP
Effective January 14, 2004, IBM has withdrawn all OSL products from active marketing. Although IBM will continue to make OSL available for sale, they will no longer make commitments for its future development and maintenance. However, GAMS Development will continue to support existing GAMS/OSL customers and keep OSL updated. We are aware that some customers may feel uncomfortable with this situation. Therefore, we have entered into an agreement with Ilog, Mosek Aps, Sunset Software and Dash Optimization to allow our customers to switch from OSL to other LP and MIP solvers such as GAMS/CPLEX, GAMS/MOSEK, GAMS/XA and GAMS/XPRESS. These four vendors, Ilog, Mosek Aps, Sunset Software and Dash Optimization, have agreed to accept GAMS/OSL as a 'trade-in'. As with other solvers, the trade-in value will be the original purchase price of GAMS/OSL adjusted by any outstanding maintenance and support charges. This trade-in will allow our OSL users to retain their investment in solver technology. We would like to thank our solver vendors and acknowledge their time and effort in bringing this idea to fruition, and in teaming with GAMS to put the interest of our customers first. |
GAMS/OSL is a high performance integrated solver for Linear Programming (LP) and Mixed Integer Programming (MIP) problems. It is specifically designed for solving large and difficult problems.
GAMS/OSL provides access to the following solvers of OSL:
GAMS/OSL is designed to give the user access to all the power of OSL without having to worry about subroutine calls, options, and parameters.
Effective January 14, 2004, IBM has withdrawn all OSL products from active marketing. Although IBM will continue to make OSL available for sale, they will no longer make commitments for its future development and maintenance. However, GAMS Development will continue to support existing GAMS/OSL customers and keep OSL updated. We are aware that some customers may feel uncomfortable with this situation. Therefore, we have entered into an agreement with Ilog, Mosek Aps, Sunset Software and Dash Optimization to allow our customers to switch from OSL to other LP and MIP solvers such as GAMS/CPLEX, GAMS/MOSEK, GAMS/XA and GAMS/XPRESS. These four vendors, Ilog, Mosek Aps, Sunset Software and Dash Optimization, have agreed to accept GAMS/OSL as a 'trade-in'. As with other solvers, the trade-in value will be the original purchase price of GAMS/OSL adjusted by any outstanding maintenance and support charges. This trade-in will allow our OSL users to retain their investment in solver technology. We would like to thank our solver vendors and acknowledge their time and effort in bringing this idea to fruition, and in teaming with GAMS to put the interest of our customers first. |
OSL-SE (Stochastic Extensions) is a powerful, flexible nested decomposition solver for stochastic linear and quadratic programs.
The PATH solver for MCP models is a Newton-based solver that combines a number of the most effective variations, extensions, and enhancements of this powerful technique. It is available as a GAMS subsystem, providing the complementarity and equilibrium modeler with a powerful tool to solve large and difficult models.
The PATHNLP solver suitable is for NLP programs. PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems. The solution to the original NLP is extracted from the KKT solution and returned to GAMS. All of this takes place automatically - no special syntax or user reformulation is required.
Typically, PATHNLP works very well for convex models. It also has a comparative advantage on models whose solution via reduced gradient methods results in a large number of superbasic variables, since the PATH solver won't construct a dense reduced Hessian in the space of the superbasic variables as reduced gradient solvers do. For nonconvex models, however, PATHNLP is not as robust as the reduced gradient methods.
SBB is a GAMS solver for Mixed Integer Nonlinear Programming (MINLP) models. It is based on a combination of the standard Branch and Bound method known from Mixed Integer Linear Programming and some of the standard NLP solvers already supported by GAMS.
Stochastic programs with recourse employing a discrete distribution of the random parameters become a deterministic programming problem. They can be solved by an appropriate optimization algorithm, ignoring the stochastic nature of (some or all) parameters.
SCENRED is a tool for the reduction of scenarios modeling the random data processes. The scenario reduction algorithms provided by SCENRED determine a scenario subset (of prescribed cardinality or accuracy) and assign optimal probabilities to the preserved scenarios. The reduced problem is then solved by a deterministic optimization algorithm provided by GAMS.
Scenario reduction for Stochastic Programming using GAMS/SCENRED
GAMS/SNOPT is a new large scale SQP (Sequential Quadratic Programming) solver developed by Philip Gill (University of California at San Diego) and Walter Murray and Michael Saunders (Stanford University).
SNOPT is a general-purpose system for solving optimization problems involving many variables and constraints. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs.
SNOPT finds solutions that are locally optimal, and ideally any nonlinear functions should be smooth. It is often more widely useful. For example, local optima are often global solutions, and discontinuities in the function are provided by the automatic differentiation engine of GAMS.
SNOPT uses a sequential quadratic programming (SQP) algorithm that obtains search directions from a sequence of quadratic programming subproblems. Each QP subproblem minimizes a quadratic model of a certain Lagrangian function subject to a linearization of the constraints. An augmented Lagrangian merit function is reduced along each search direction to ensure convergence from any starting point.
SNOPT is most efficient if only some of the variables enter nonlinearly, or if the number of active constraints (including simple bounds) is nearly as large as the number of variables. SNOPT requires relatively few evaluations of the problem functions.
GAMS/XA is a solver for Linear and Mixed Integer problems from Sunset Software Technology.
The GAMS/XPRESS solver is an adaptation of the XPRESS-MP Optimization Subroutine Library from Dash and runs only in conjunction with the GAMS modeling system. GAMS/XPRESS is a versatile, high-performance optimization system. The system integrates a powerful simplex-based LP solver, an MIP module for integer programming problems, and a barrier module implementing a state-of-the-art interior point algorithm for very large LP problems.
