|
New Xpress-MP 2004 Software Release
Xpress-MP 2004 Highlights
Introduction
The Xpress-MP product range has undergone
extensive development during 2003 and the new Xpress-MP 2004
edition is now available.
A key development direction has been to benchmark
the LP and MIP optimizers against a range of theoretical and
practical problems. Performance has been minutely analyzed
and the behaviour understood. This has resulted in a host
of minor improvements which, taken together, have improved
performance and reliability. With reference to the Mittelmann
benchmark set of problems, the most recent update of Mittlemann's
website showed that Xpress-MP was the fastest LP/MIP code
available.
Vertical Sectors
Xpress-MP has been thoroughly benchmarked, enhanced and
tuned for a range of key vertical sectors. These include:
- Aviation
- Supply Chain
- Retail
- Pricing
- Sourcing
- Auctions, and,
- Finance
Optimizer - MIP
Xpress-MP is well known for getting good solutions in a short
time. Recent developments have concentrated on improving the
lower bound, faster. This results in faster times to proven
optimality and, in the case of large problems, a better bound
within the time allocated. Average speed improvements in excess
of 30% have been achieved.
Specific
areas of improvement are:
- Heuristics: there are
now six heuristics in Xpress-MP, including heuristics specifically
for lot sizing problems and crew scheduling problems, together
with heuristics that are more generally applicable.
- Lift-and-project:
New lift-and-project cuts that replace the old Gomory cuts.
With little additional work, the classical Gomory cuts are
improved using a lift-and-project procedure to produce a
set of cuts that are tighter than the Gomory cuts. Cuts
are now generated within the branch and bound tree by default,
which improves the ability to raise the bound within the
search.
- Strong branching: New
branching scheme based on strong branching and global pseudo
costs is now used by default. It is self-tuning based on
problem characteristics.
- Presolve improvements,
including the ability to detect MIP objects such as integer
variables and special ordered sets that are implied by the
formulation and can be used to improve cut generation and
branching.
- Other areas of improvement are overall
speed, duplicate dependant row removal, constraint tightening,
coefficient reduction, automatic disaggregation, and semi-continuous/integer
variable.
| MIP performance data |
|
|
|
| |
|
2003 |
2004 |
Speed up |
| Arithmetic mean |
896 |
496 |
81% |
| Geometric mean |
2111 |
102 |
107% |
| Solved |
40 |
55 |
|
| Mittlemann MIP test set;
59 problems |
|
|
Optimizer - Primal simplex
The column and row selection algorithms
have been improved, and the primal simplex has been made more
robust and better able to handle numerically difficult problems.
The primal simplex is up to eleven times faster than Xpress-MP
2003 (Optimizer release 14.05) and is especially good for
scheduling problems and problems in general that degenerate
or have a very tight feasibility.
| Primal simplex performance
data |
|
|
| |
|
2003 |
2004 |
Speed up |
| Arithmetic mean |
11077 |
1221 |
807% |
| Geometric mean |
642 |
281 |
128% |
| Mittlemann LP test set;
29 problems |
|
|
Optimizer - Barrier
The
Cholesky factorisation has been improved which gives much
better performance for large problems. These improvements
include a better use of cache memory; exploitation of special
new CPU instructions and features; and in general less non-numeric
overhead. The barrier optimiser now achieves ~4.5 Gigaflops
peak and ~4 Gigaflops sustained performance on a P4/2.8Ghz
machine (on large problems), and is up to two times faster
than Xpress-2003.
| Barrier simplex performance
data |
|
|
| |
|
2003 |
2004 |
Speed up |
| Arithmetic mean |
319 |
167 |
91% |
| Geometric mean |
67 |
53 |
26% |
| Mittlemann LP test set;
29 problems |
|
|
IVE
- New stochastic programming interface
to support Xpress-SP
- Sprinter: a new integrated
optimizer performance tuning aid
- NEOS client: the Xpress-IVE Student Edition
may now be used as a client for the Xpress-MP service on
NEOS. This allows students to solve problems without any
capacity restrictions. An account for NEOS with Dash Optimization
is required, and there are usage restrictions.
- Modelling
assistant/wizard: helps you develop models in Xpress-IVE
- Further improved
matrix, problem and solution visualization, including SLP
specific features
Mosel
- New
stochastic programming module to support Xpress-SP
- Irreducible infeasible set (IIS) analysis
now available within Mosel
- Execution of the 'exists' function has
been improved so that sums and loops over sparse sets are
now significantly faster
- Further optimisation of the execution
of sparse loops and sums with the 'exists' function (see
also above)
- Full 64 bit support, maintaining cross
platform support for bim files, independent of the architecture
- New file handling:
a module may include IO drivers which are referred via a
filename. This will enable the use of memory as a file (e.g.
"mem:0x123456/1024" is a location in memory of
1kB), and the use of a call-back as a file, which improves
the handling of streams in VB/Java (e.g. "cb:0x123456"
is a function located at the given address).
BCL
- Significant speed up through new memory
manager
- Improved handling of operations involving
linear expressions under C++ and Java
- Sensitivity analysis
("ranging") available
Product Support
- Mp-model
and AMPL to Mosel translators
- New
Getting Started manual to replace Essentials and to accompany
the recently published book, Applications of Optimization
with Xpress-MP. In addition the existing documentation undergoes
a programme of continuous revision and improvement.
- 64-bit Solaris, AIX, and HPUX distributions
of the Optimizer and BCL now included on CD as standard.
SLP now available on Unix platforms.
- License manager now
starts automatically, is faster and exits more reliably.
More descriptive error messages and better error trapping.
|
