FICO Xpress Solver Technology Overview
FICO Xpress Solver technology is used by thousands of companies worldwide to solve all sorts of optimization problems, ranging from supply chain planning to portfolio management, from the process industry to financial services. It is designed for solving optimization problems with millions of variables and millions of constraints, on all common operating systems and computing platforms, as a standalone system, in the cloud or embedded in your software environment.
Key Features
FICO Xpress Solver features state-of-the-art algorithms for a wide range of mathematical optimization problems. It solves linear programs (LP), quadratic programs (QP), quadratically constrained programs (QCPs), second-order cones programs and their mixed-integer equivalents mixed integer linear and quadratic programming problems (MIP, MIQCQP, MISOCP). It also offers a distinguished solver for nonlinear, non-convex optimization problems, continuous or mixed-integer. It supports continuous, integer, partial integer, and semi-continuous variables, special ordered sets and indicator constraints.
Using Xpress Solver through the Xpress Mosel modelling language brings in the possibility of distributed computing and employing robust optimization concepts. Further Xpress Mosel lets you link XML, R, CSV, Excel, Hadoops HDS, ODBC and Oracle data sets into your models. We also offer interfaces to C, C++, Java, Python, .NET, VB, and Matlab.
Predictability and reproducability are key factors of our solver development. All solver components are deterministic by nature. Moreover, a unique feature is that it takes identical solution paths independent of the computing environment, and even independent of the number of used system threads. This is due to the superior parallelization scheme that uses so-called "tasks". It is designed to scale on large number of used system threads. The concept of using maintaining more parallel tasks than threads leads to a high CPU workload. Furthermore, using a trailing read barrier instead of fixed synchronization points for the parallel tasks allows for a high flexibility.
FICO Xpress Solver is also noted for its ability to solve numerically hard or unstable problems, which is one of the reasons why it is the clear market leader in the process industries. Besides many others, this is achieved by an innovative solution refiner that resolves numerical infeasibilities a posteriori.
More Information:
- FICO Xpress Optimization Community License - try Xpress Solver for free
Solver Recommendations
In real-world applications, it is vital to match the right optimization technology to your problem. The FICO Xpress libraries provide dedicated, high performance implementations of optimization technologies for the many model classes commonly appearing in practical applications. This includes solvers for linear programming (LP), mixed integer programming (MIP), convex quadratic programming (QP), and convex quadratically constrained programming (QCQP), and general nonlinear programming (NLP).
The graphic below provides a guide on the Solver (and possible alternatives), that we recommend for different problems:
Simplex methods | LP \ convex Q barrier | Outer approximation | Sequential Linear | NLP interior point | |
---|---|---|---|---|---|
Linear Problems LP | |||||
Convex Quadratic QP | |||||
Quadratic Constrained QCQP | |||||
Second order conic SOCP | |||||
General nonlinear NLP | |||||
Mixed integer, in branch & bound & others | |||||
Linear problems MIP | |||||
Convex quadratic MIQP | |||||
Quadratic constrained MIQCQP | |||||
Second order conic MISOCP | |||||
General nonlinear MINLP | |||||
| |||||
Recommend solver: | |||||
Possible alternative: |
Summary information on the different problem types and FICO Xpress Solvers are provided below:
The Simplex Method The simplex method is one of the most well-developed and highly studied mathematical programming tools. The solvers in FICO Xpress Solver are the product of over 30 years of research, and include high quality, competitive implementations of the primal and dual simplex methods for both linear and quadratic programs. A key advantage of the simplex method is that it can very quickly re-optimize a problem after it has been modified, which is an important step in solving mixed integer programs. | The Logarithmic Barrier Method The interior point method used in FICO Xpress Solver is a state of the art implementation, with leading performance across a variety of large models. It is capable of solving not only the largest and most difficult linear and convex quadratic programs, but also convex quadratically constrained quadratic and second order conic programs. It includes optimized versions of both infeasible logarithmic barrier methods, and also homogeneous self-dual methods. | Outer approximation schemes A drawback of the barrier methods is that they are not efficiently warm-started. This makes these methods unattractive for solving several related problems, like the ones arising from a branch and bound search. While for linear and convex quadratic problems the simplex methods can be used, there is no immediate such alternative for convex quadratic constrained and second order methods. To bridge the gap, outer approximation cutting schemes are used, which themselves may be warm started by a barrier solution. |
Successive Linear Programming For general nonlinear programs which are very large, highly structured, or contain a significant linear part, the FICO Xpress Sequential Linear Programming solver (XSLP) offers exceptional performance. Successive linear programming is a first order, iterative approach for solving nonlinear models. At each iteration, a linear approximation to the original problem is solved at the current point, and the distance of the result from the the selected point is examined. When the two points are sufficiently close, the solution is said to have converged and the result is returned. This technique is thus based upon solving a sequence of linear programming problems and benefits from the advanced algorithmic and pre-solving techniques available for linear problems. This makes XSLP scalable, as well as efficient for large problems. In addition, the relatively simple core concepts make understanding the solution process and subsequent tuning comparatively straightforward. | Second Order Methods Also integrated into the Xpress suite is KNITRO from Ziena Optimization, a second-order method which is particularly suited to large-scale continuous problems containing high levels of nonlinearity. Second order methods approximate a problem by examining quadratic programs fitted to a local region. This can provide information about the curvature of the solution space to the solver, which first-order methods do not have. Advanced implementations of such methods, like KNITRO, may as a result be able to produce more resilient solutions. This can be especially noticeable when the initial point is close to a local optimum. | Mixed Integer Solvers The FICO Xpress MIP Solver is a highly scalable parallel branch and bound framework for all classes of mixed integer programs. It is based on a branch and bound search utilizing continuous solvers, advanced cutting planes in-tree presolving and multiple heuristics, for discovering primal solutions and tightening best bounds. The search is guided by advanced methods for selecting branching variables and estimating sub-tree sizes/efforts. Mixed integer programming forms the basis of many important applications, and the implementation in FICO Xpress Solver has proven itself in operation for some of the world's largest organizations. |
FICO® Xpress Optimization Innovations
Solving 1983: LP solver running on PCs 1992: Parallel MIP (1997 on distributed PC/Linux networks) 1995/1996: Commercial branch and cut algorithm 1998: Bound switching in dual simplex 2003: Lift-and-project cuts 2009: Parallel MIP heuristics 2010: LP/MIP solver crosses 64-bit coefficient indexing threshold 2013: Tight integration of different NLP technologies 2013: Automatic solver selection for NLP 2014: Parallel simplex 2016: Task based parallel MIP 2017: barrier warm start and parallel crossover parallel black box optimization | Modelling 1983: General purpose algebraic modeling language (mp-model) 2001: Algebraic modeling language combining modeling, solving, and programming (Mosel) 2005: Profiler and debugger for a modeling language 2005: User-controlled parallelism at the model level 2010: Algebraic modeling language supporting distributed computing 2012: Mosel remote launcher 2014: Parallel profiler and debugger; robust optimization 2017: Cloud based optimization model and solution development |
Mathematical Programs Overview
There are many specialized forms of model in mathematical programming, and if such a form can be identified, there are usually much more efficient solution techniques available.
This section describes some of the major types of problem that Xpress Solver can identify automatically:
Linear programsLinear programming (LP) involves solving problems of the form
and in practice this encompasses, via transformations, any problem whose objective and constraints are linear functions. Such problems were traditionally solved with the simplex method, although recently interior point methods have come to be favoured for larger instances. Linear programs can be solved quickly, and solution techniques scale to enormous sizes of the matrix A. However, few applications are genuinely linear. It was common in the past, however, to approximate general functions by linear counterparts when LPs were the only class of problem with efficient solution techniques. | Mixed integer programsMixed-integer programming (MIP), in the most general case, involves solving problems of the form
It can be combined with any of the other problem types, giving Mixed-Integer Linear Programming (MILP), Mixed-Integer Quadratic Programming (MIQP), Mixed-Integer Quadratically Constrained Quadratic Programming (MIQCQP), Mixed-Integer Second Order Conic Problems (MISOCP) and Mixed-Integer Nonlinear Programming (MINLP). Efficient solution techniques now exist for all of these classes of problem. | Convex quadratic programsConvex quadratic programming (QP) involves solving problems of the form
for which the matrix Q is symmetric and positive semi-definite (that is, x^{T} Q x 0 for all x). This encompasses, via transformations, all problems with a positive semi-definite Q and linear constraints. Such problems can be solved efficiently by interior point methods, and also by quadratic variants of the simplex method. | ||||||||||||||||
Convex quadratically constrained quadratic programsConvex quadratically constrained quadratic programming (QCQP) involves solving problems of the form
for which the matrix Q and all matrices P_{j} are positive semi-definite. The most efficient solution techniques are based on interior point methods. | Second order conic problemsSecond order conic problems is a special form of a convex quadratically constrained quadratic program, where although the quadratic matrix is not positive semi-definite, the feasible range of the problem is convex, and there are specialized algorithm to solve them.
for which the matrix C_{j} is a convex second order cone and Q is positive semi-definite. The standard form of a second order cone is x^{T}I xy*y where y is non-negative, or (a rotated second order cone) x^{T}I xy*z where y and z are non-negative. Many quadratic problems can be formulated as a second order convex conic problem, including any convex quadratically constrained quadratic programs. Transformation happens automatically for most convertible problems. | General nonlinear optimization problemsNonlinear programming (NLP) involves solving problems of the form
where f(x) is an arbitrary function, and g(x) are a set of arbitrary functions. This is the most general type of problem, and any constrained model can be realized in this form via simple transformations. Until recently, few practical techniques existed for tackling such problems, but it is now possible to solve even large instances using Successive Linear Programming solvers (SLP) or second-order methods. |
For more information and guidance on Mathematical Programs, Solvers and FICO recommendations, please raise a question through the FICO Xpress User Forum.