Industry Leading Solver Technology

Document created by neillcrossley@fico.com Advocate on Jul 21, 2017Last modified by Makenna.Brei on Sep 8, 2017
Version 20Show Document
  • View in full screen mode

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:

 

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 methodsLP \ convex Q barrierOuter approximationSequential 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 programs

Linear programming (LP) involves solving problems of the form

minimizecT x
subject toAxb

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

minimizef(x)
subject togj(x)b, j
xk integral

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

minimizecT x + xT Q x
subject toAxb

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

minimizecT x + xT Q x
subject toAxb
qjTx + xT Pj x  dj, j

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.

minimizecT x + xT Q x
subject toAxb
x is in Cj, j

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

minimizef(x)
subject togj(x)b, j

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.

Attachments

    Outcomes