Xpress-MP: What’s new in release 13?

Xpress-Optimizer Developments

Mixed integer quadratic programming (MIQP)
Mixed integer quadratic programming (MIQP) problems can now be handled by Xpress-MP, supported by an improved barrier QP algorithm and a new simplex QP algorithm. The barrier QP algorithm was introduced in release 12 to solve QP problems, i.e., LP problems with a quadratic objective function. Now improvements to the barrier QP algorithm, a new simplex QP algorithm, and support for quadratic objectives within the global search allow MIQP problems - MIP problems with a quadratic objective function - to be solved.

MIQP problems can be input from MPS and LP format matrix files using the XPRSreadprob function, loaded directly from program arrays using the XPRSloadqglobal function, or loaded through BCL. Please refer to the new Optimizer Reference Manual for details of the MPS and LP formats and a description of the XPRSloadqglobal function. Once loaded, MIQP problems can be accessed and manipulated using the existing Optimizer functionality together with three new functions specifically to access the quadratic objective function: XPRSgetqobj, XPRSchgqobj and XPRSchgmqobj. These new functions are described in the Optimizer Reference Manual. MIQP problems can also be exported to LP format matrix files using the XPRSwriteprob function; problems can not yet be exported to MPS format matrix files.

To solve MIQP problems, use the existing XPRSminim/maxim functions either with the g (global) option or followed by a call to XPRSglobal. The barrier QP algorithm will be used by default; to select the primal simplex QP algorithm, set the XPRS_DEFAULTALG control to 3 before calling XPRSminim/maxim. The p (primal) option to XPRSminim/maxim can also be used to select the primal simplex algorithm over the barrier algorithm for the initial QP relaxation only, or when solving QP (non-MIQP) problems. To give you an idea of the performance, one MIQP instance with 234 variables, of which 41 were integer variables, solved in 4 seconds on a 400 MHz Pentium II. Another instance with 600 integers and 36000 quadratic entries in the objective function solved in 27 seconds using simplex based MIQP.

Algorithmic improvements
The dual simplex algorithm has an improved pricing algorithm selection. The simplex algorithm in general has better sparse/dense problem handling. On average, the time taken to solve LPs has been reduced by 30%.

The Newton barrier algorithm now incorporates row-wise Cholesky factorization, which gives improved performance on many problems, and has more efficient memory usage. A new control, XPRS_BARMEMORY, allows the amount of memory used to be controlled more easily, as described in the Optimizer Reference Manual.

The presolve has more efficient memory management, and the eliminator phase has been improved.

The branch and bound algorithm has improved cut selection and faster clique cut generation. A new branching option, strong branching, has been added, which you can apply using the two new XPRS_SBITERLIMIT and XPRS_SBBEST controls. A new control XPRS_MAXCUTTIME allows cut generation phase to be limited by time in addition to the number, size and type of cuts. All new controls are fully described in the Optimizer Reference Manual.

Other developments
A new type of MIP variable (or global entity) is supported: semi-continuous integer variables. These are variables that can take the value 0, or any integer between a given lower and upper bound - for instance, one set of valid values might be 0, 5, 6, 7, 8. They are a combination of the existing integer and semi-continuous types. They can be input from MPS and LP format matrix files using the XPRSreadprob function, loaded directly from program arrays using the XPRSloadglobal function, or loaded through BCL or Mosel. Please refer to the new Optimizer Reference Manual for details of the MPS and LP formats and a description of the XPRSloadglobal function.

Goal programming - previously only accessible from Optimizer console - is now supported from Optimizer C/C++, by means of the new XPRSgoal function. The analysis of irreducible infeasible sets (IIS) is also fully supported in Optimizer C/C++, by means of two functions, XPRSiis and XPRSgetiis. Please refer to these functions in the Optimizer Reference Manual for further details.

Access to the problem in its presolved and original forms has been made easier to understand and apply. Two separate functions are now provided to get the solution: XPRSgetsol gets the solution in its original (post solved) form; XPRSgetpresolvesol gets the solution in its presolved form. The function XPRSloadpresolvedirs allows directives to be loaded for the presolved problem, while the functions XPRSloadpresolvebasis and XPRSgetpresolvebasis allow bases to be loaded and obtained for the presolved problem. The function XPRSloadsecurevecs allows vectors (rows and columns) to be secured against presolve operations, that is, they will not be eliminated by the presolve.

The parallel MIP optimizer now permits cuts at the top node of the branch and bound tree. The XPRSinitglobal function now removes all cuts from the matrix and cut pool.

A new function XPRSgetlasterror returns a character string containing the last error that occurred for a specified problem, while another new function XPRSgetbanner returns a character string containing the banner and copyright message. Long row and column names - up to 64 characters - are fully supported.