Performance Profiles and Quality of Solution
Overview
Previous work using
performance profiles proved useful for
convex models, such as linear programs (LPs) or certain quadratic programs
(QPs). But the resulting graphs only considered:
- solver efficiency
- solver robustness
but not quality of solution. Thus, a solver appears to be "better"
than another in the original performance profile plots
as long as it solves successfully (based on GAMS model
and solve status return codes) and is the most efficient.
While this makes sense for convex models, such as LPs,
the resulting graphs may be unduly biased when analyzing results
for non-convex models or models
with discrete variables. In particular with recent advances in global
optimization other factors involving solution quality play an important
role as well.
For example, one solver may indeed be more efficient, but
the solution may be worse than that of a solver which is
slower in terms of solver resource time.
Thus, for models such as mixed-integer programs (MIPs), nonlinear
programs (NLPs), or mixed-integer nonlinear programs (MINLPs),
useful performance metrics should consider:
- solver efficiency
- solver robustness
- and solver quality of solution
Therefore, performance tools should also give information depending
on what is deemed more important by the user: solver efficiency
or solver solution quality. We have extended the performance profiles
to include quality of solution information.
Sample Scenario
Consider the following sample performance profiles, which show the
effect of considering quality of solution (i.e. the best solution)
and solver efficiency, compared to only solver efficiency. The
example shows performance profiles for two solvers on a set of
MINLP models. One solver is much faster than the other, but quality
of solution is worse. See the
Performance in pprocess.gms
The automated performance tool
pprocess.gms,
which runs all performance routines automatically, including
the performance profile routine, takes into account the quality of
the solution.
In particular, the routine shows multiple performance profile plots,
taking into account that a solver "wins" if it is more efficient only,
if it within n % of the best solution, or if it found the
best solution.
See the sample results using pprocess.gms, which were used
in the
ORMS Today August 2002 ad
featuring CONOPT:
Top
