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.
ANTIGONE (Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations) from Princeton University is a deterministic global optimization solver for mixed-integer nonconvex optimization problems (MINLP). ANTIGONE performs equivalently to GloMIQO when all nonlinearities in MINLP are quadratic.
GAMS/AMPL allows users to solve GAMS models using solvers within the AMPL modeling system. The GAMS/AMPL link comes free with any GAMS system. Users must have a licensed AMPL system installed and have the AMPL executable in their path.
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 a 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.
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.
Bonmin (Basic Open-source Nonlinear Mixed INteger programming) from the COIN-OR project (COmputational INfrastructure for Operations Research) implements branch-and-bound, branch-and-cut, and outer approximation algorithms for MINLPs. It is available free of charge with any licensed GAMS system under Linux, MacOS X, Solaris Intel, and Windows.
CBC (COIN-OR branch and cut) from the COIN-OR project (COmputational INfrastructure for Operations Research) is a simplex solver for LPs and a branch-and-cut solver for MIPs. It is available free of charge with any licensed GAMS system under Linux, MacOS X, Solaris Intel, and Windows.
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. The generic solver name CONOPT is an alias to the most reliable production version of GAMS/CONOPT (currently CONOPT3).
|Performance Profiles:||CONOPT1, CONOPT2, CONOPT3 on Cops Models|
|CONOPT3 default, without SQP, without SQP and without SLP|
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:
Couenne (Convex Over and Under ENvelopes for Nonlinear Estimation) from the COIN-OR project (COmputational INfrastructure for Operations Research) implements a spatial branch-and-bound algorithm for solving nonconvex (MI)NLPs to global optimality. It is available free of charge with any licensed GAMS system under Linux, MacOS X, Solaris Intel, and Windows.
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 IBM ILOG CPLEX. 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. Finally, a bare-bone interface to the LP and MIP solver of Cplex is available under the name OSICPLEX, it comes free of charge with any GAMS system.
The DE Solver generates and solves the deterministic equivalent of a stochastic program, DE is part of EMP/SP
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 and a GAMS NLP solver. The performance will heavily depend on the choice of the selected subsolvers.
EMP (Extended Mathematical Programming) is not a solver but an (experimental) framework for automated mathematical programming reformulations. The idea behind EMP is that new upcoming types of models which currently cannot be solved reliably are reformulated into models of established math programming classes in order to use mature solver technology. At this stage, EMP supports the modeling of Bilevel Programs, Variational Inequalities, Disjunctive Programs, Extended Nonlinear Programs and Embedded Complementarity Systems, but additional features are being added regularly. Extended mathematical programs are collections of functions and variables joined together using specific optimization and complementarity primitives.
EMP has been developed jointly by Michael Ferris of UW-Madison, Ignacio Grossmann of Carnegie Mellon University and GAMS Development Corporation.
EMP and JAMS come free of charge with any licensed GAMS system but require a subsolver to solve the generated models.
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 continuous (LP, QP, and QCP) and mixed-integer programming (MILP, MIQP, and MIQCP) problems 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.
In addition if you have a callable library license from Gurobi, we offer a GAMS/GUROBI link at a reduced price. This is the same program as the GAMS/GUROBI solver, but it uses your existing Gurobi callable library license. It is noted that the link does not work on the GUROBI stand alone license. Finally, a bare-bone interface to the LP and MIP solver of Gurobi is available under the name OSIGUROBI, it comes free of charge with any GAMS system.
Ipopt (Interior Point Optimizer) from the COIN-OR project (COmputational INfrastructure for Operations Research) is a solver for large-scale nonlinear programs (NLPs). It is available free of charge with any licensed GAMS system under Linux, MacOS X, Solaris Intel, and Windows.
GAMS/IpoptH extends GAMS/Ipopt by making the linear solver of the Harwell Subroutine Libraries (MA27, MA57, MA86, and MA97) available in Ipopt.
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 by Pinter Consulting Services 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
GAMS/LINDO finds guaranteed globally optimal solutions to general nonlinear problems with continuous and/or discrete variables. GAMS/LINDO supports most mathematical functions, including functions that are nonsmooth, such as abs(x) and or even discontinuous, such as floor(x). Nonlinear solvers employing methods like successive linear programming (SLP) or generalized reduced gradient (GRG) return a local optimal solution to an NLP problem. However, many practical nonlinear models are non-convex and have more than one local optimal solution. In some applications, the user may want to find a global optimal solution.
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 either 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 subproblem 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.
GAMS/LINDO can automatically linearize a number of nonlinear relationships, such as max(x,y), through the addition of constraints and integer variables, so the transformed linearized model is mathematically equivalent to the original nonlinear model. Keep in mind, however, that each of these strategies will require additional computation time. Thus, formulating models, so they are convex and contain a single extremum, is desirable. In order to decrease required computing power and time it is also possible to disable the global solver and use GAMS/LINDO like a regular nonlinear solver.
GAMS/LINDO has a multistart feature that restarts the standard (non-global) nonlinear solver from a number of intelligently generated points. This allows the solver to find a number of locally optimal points and report the best one found. This alternative can be used when global optimization is costly. A user adjustable parameter controls the maximum number of multistarts to be performed.
LINDO automatically detects problem type and uses an appropriate solver, e.g., if you submit an LP model to LINDO, it will be solved as an LP at LP speed, regardless of what you said in the ”solve using” statement. With the NLP parameter NLP QUADCHK turned on, LINDO can detect hidden quadratic expressions and automatically recognize convex QCPs, as well as second-order cones (SOCP), like in Value-at-Risk models, allowing dramatically faster solution times via the barrier solver. When such models have integer variables, LINDO would use the barrier solver to solve all subproblems leading to significantly improved solution times when compared to the case with the standard NLP solver.
In order to use GAMS/LINDOGlobal, users need a GAMS/LINDOGlobal license. Additionally a GAMS/CONOPT license is required for solving nonlinear subproblems. The GAMS/LINDOGlobal license places upper limits on model size of 3,000 variables and 2,000 constraints. To use GAMS/LINDO, no additional license is required. Also, there is no upper limit on the model size with GAMS/LINDO and, in addition, it allows to solve stochastic models Neither the GAMS/LINDO not the GAMS/LINDOGlobal license does include the Barrier solver option. LINDO would be able to use the barrier solver when the user has a separate license for the GAMS/MOSEK barrier 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 Wisconsin.
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 withnonlinear 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.
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
In addition if you have a callable library license from Mosek, we offer a GAMS/MOSEK link at a reduced price. This is the same program as the GAMS/MOSEK solver, but it uses your existing Mosek callable library license. It is noted that the link does not work on the MOSEK stand alone license. Finally, a bare-bone interface to the LP and MIP solver of Mosek is available under the name OSIMOSEK, it comes free of charge with any GAMS system.
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. QNLP 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
OS (Optimization Services) from the COIN-OR project (COmputational INfrastructure for Operations Research) allows users to solve GAMS models by sending them to an Optimization Services Server. Users must have access to such a server to use this tool. OS is available free of charge with any licensed GAMS system under Linux, MacOS X, Solaris Intel, and Windows.
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.
SCIP (Solving Constraint Integer Programs) is framework for Constraint Integer Programming and is developed at Zuse Institute Berlin, TU Darmstadt, and University of Erlangen-Nürnberg. Within GAMS, the MIP and (MI)NLP solving facilities of SCIP are available. Since SCIP is distributed under the ZIB Academic License, it is only available for users with a GAMS academic license.
GAMS/SNOPT is a 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.
SoPlex (Sequential object-oriented simPlex), developed at the Zuse Institute Berlin, is a Linear Programming (LP) solver based on the revised simplex algorithm. Since SoPlex is distributed under the ZIB Academic License, it is only available for users with a GAMS academic license. The GAMS/SoPlex interface is based on the COIN-OR Osi/SoPlex interface.
GAMS/SULUM is a solver for Linear and Mixed Integer Linear problems from Sulum Optimization.
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 Fico 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.
In addition if you have a callable library license from Xpress, we offer a GAMS/XPRESS link at a reduced price. This is the same program as the GAMS/XPRESS solver, but it uses your existing Xpress callable library license. It is noted that the link does not work on the XPRESS stand alone license. Finally, a bare-bone interface to the LP and MIP solver of Xpress is available under the name OSIXPRESS, it comes free of charge with any GAMS system.