The XPRESS-MP optimizer is one of the leading solvers in the market today. With over 20 years of research and development it is at the forefront of optimization technology today. XPRESS for MPL gives MPL users access to this renowned solver of linear programming and mixed integer programming from within the user-friendly Windows environment of MPL. Like all our solvers the XPRESS optimizer is actually accessed from MPL for Windows as a Dynamic Link Library (DLL). This tight integration allows MPL users to transparently access XPRESS solution algorithms and options from their MPL application. XPRESS is employed by a huge variety of commercial installations throughout the world to provide fast, reliable solutions to problems with millions of variables and constraints.
XPRESS-MP is a Linear and Integer Programming optimizer, which has been designed to take full advantage of matrix structure. XPRESS has a number of cutting edge algorithms enabling you to solve:
XPRESS has a complete set of algorithms to handle LP problems, encompassing the dual simplex, primal simplex and barrier methods. It has an integrated presolve algorithm to reduce the problem size. XPRESS simplex optimizers provide fast, reliable implementations of the primal and dual simplex methods for solving LP problems. Having automatic settings for best performance and an extensive range of user-configurable parameters for advanced control of the optimization process. Have fast restarts from an existing advanced basis. Problems can be modified and then resolved in a fraction of the original solution time. If the problem is degenerate, XPRESS can employ effective degeneracy resolution techniques.
The XPRESS Optimizer Barrier algorithm provides an alternative to the simplex algorithms and uses interior point methods to solve both linear programming and quadratic programming problems. The barrier algorithm has cutting edge Cholesky factorization techniques and can handle dense columns.
XPRESS can handle QP models that have a quadratic objective function and linear constraints. To solve QPs in MPL by XPRESS one has to set in MPL the "ModelType" to Quadratic. XPRESS also has the capability of solving MIQPs these are QPs in which some or all the variables can take discrete values.
The XPRESS MIP Optimizer uses a sophisticated branch and bound algorithm to solve MIP and MIQP problems and is well known for its ability to quickly find high quality solutions. It encompasses:
XPRESS offers users a choice of methods to be used for solving LP problems: the primal and dual simplex algorithms and the Newton barrier interior point algorithm. The best algorithm to use for optimization in a given situation is problem-specific. As a general rule, the dual simplex is usually much faster than the primal simplex if the model is not infeasible or near-infeasibility. If the problem is likely to be infeasible, then the primal simplex is probably the best choice as it makes determining the cause of the infeasibility simpler. Interior point methods such as the Newton barrier algorithm perform better on certain classes of problems, typically these are large sparse problems.
If performance is an issue it is best to experiment with these different algorithms. If one is using the simplex methods one can look into changing the pricing options. Typically, partial pricing results in a greater number of fast iterations whereas Devex pricing results in fewer, slow iterations. Which is better is highly problem-dependent. The Newton barrier method is influenced by a number of controls, which can be altered if the solution search seems slow. Ensuring that the "Cachesize" is set correctly can have a significant effect on the performance. Similarly, altering the ordering algorithm for the Cholesky factorization can also affect performance. Setting this to "Minimum local fill" often produces better results, although the ordering itself can be significantly slower.
MIP problems can be extremely difficult to solve, though there are no steadfast rules on enhancing MIP performance, certain things may be advantageous in improving the performance on some models and be a hinderous on other problems. Below are some of the considerations one should look into when try to solve difficult MIP problems with XPRESS:
Priority orders:Assign higher priority to the integer variables that should be decided earlier, these tend to represent decisions that are strategic or activate processes. The order, the variables are defined in MPL indicates the MIP priority, earlier the definition the higher the priority.
Cutoffs: The concept of a cutoff value can be applied even when no integer solution has been found if it is known, or it may be assumed from the outset that the optimal solution must be better than some value. If the relaxation is worse than this cutoff, then the node may be abandoned. There is a danger, however, that all integer feasible solutions, including the optimal one, may be missed if an overly optimistic cutoff value is chosen.
Preprocessing: XPRESS's integer preprocessing can be performed at each node of the branch and bound tree search (including the top node). This incorporates reduced cost fixing, binary variable fixing and probing at the top node. If a variable is fixed at a node, it remains fixed at all its child nodes, but it is not deleted from the matrix (unlike the variables fixed by presolve). It is usually always good practice to ulitize one or more of the MIP preprocessing procedures.
Cuts:The global search for a solution of a MIP involves optimization of a large number of LP problems, known as nodes. This process is often made more efficient by supplying additional rows (constraints) to the matrix which reduce the size of the feasible region, whilst ensuring that it still contains any optimal integer solution. Such additional rows are called cutting planes, or cuts. By default, cuts are automatically added to the matrix by the XPRESS during a global search to speed up the solution process. However, the level of cuts added can be altered. There is a tradeoff to be had the more cuts means more time processing the nodes, whereas adding the cuts usually tighten the formulation and prevent the traversing of "useless" branches. Typically for difficult MIP models it is best to choose the "Aggressive cut strategy".
To be able to run the XPRESS Optimizer requires a valid licence file, which is named xpauth.ini. This may be configured for a specific machine, ethernet address or an authorized dongle. If the license file or dongle is missing, a message will be displayed describing the problem and the Optimizer will exit.
For machine specific licenses one needs to run the program, xpihostid this will give out the ihostid codes for the machine in xml format. This code then needs to be sent in an email back to us. Once received we can issue the XPRESS license, which will be some lines of text which need to be stored in the file xpauth.ini. Note: it is preferable that the license file be kept in the same directory as the xprl.dll is installed in typically C:\Mplwin4 folder.
For full description of all the XPRESS Parameters that are supported in MPL please go to the XPRESS Option Parameters page.