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.
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.
- FICO Xpress Optimization Community License - try Xpress Solver for free
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|
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
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
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 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 programs
Mixed-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 programs
Convex quadratic programming (QP) involves solving problems of the form
for which the matrix Q is symmetric and positive semi-definite (that is, xT 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 programs
Convex quadratically constrained quadratic programming (QCQP) involves solving problems of the form
for which the matrix Q and all matrices Pj are positive semi-definite.
The most efficient solution techniques are based on interior point methods.
Second order conic problems
Second 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 Cj is a convex second order cone and Q is positive semi-definite.
The standard form of a second order cone is xTI xy*y where y is non-negative, or (a rotated second order cone) xTI 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 problems
Nonlinear 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.