|
When modeled in the AMPL
modeling language, optimization problems may be
examined by a set of tools found in the
AMPL Library.
Dr. Ampl is a meta solver which,
by use of the AMPL Library, dissects such models, obtains
statistics on their data, is able to symbolically prove or numerically
disprove convexity of the functions involved and provides aid in the
decision for an appropriate solver. A problem is associated with a number
of appropriate solvers available on the
NEOS Server for Optimization
by means of relational database.
The AMPL engine sees Dr. Ampl as a
solver — an interface between the engine and a problem
modeled in AMPL, able to read in data from the problem
description, manipulate it and return a result. This includes
programs which attempt to find an approximate solution to the
problem, but is more general and also includes programs which examine
the problem with other purposes in mind. Dr. Ampl falls in the latter category,
which, to avoid any confusion, we refer to as meta solvers.
Solvers aiming to find a local solution can advantageously use what structural
information is available:
-
convexity properties,
-
simplifications that occur by preprocessing the constraints,
-
polynomiality of the objective and constraints,
-
bounds on the objective and constraint values over the feasible set,
-
etc…
Dr. Ampl examines a problem and attempts to collect relevant information about
its data:
-
the nature of the problem,
-
the degree of nonlinearity of the objective and constraint functions,
-
the convexity of these functions,
-
the monotonicity of these functions,
-
lower and upper bounds on these functions.
The nature of a problem is the class in which it fits in some
prescribed classification of optimization problems.
Based on what it can observe, Dr. Ampl classifies the problem into one
of those categories:
linear programs,
quadratic programs,
mixed-integer programs, complementarity problems,
etc…
Bound estimates are obtained by bound propagation.
Bound propagation works in both forward and reverse mode.
In forward mode, Dr. Ampl recursively infers bounds on the
linear and nonlinear expressions involving the variables.
Such bounds help detect redundant constraints and infeasible problems.
Bound propagation in reverse mode allows to infer tighter
bounds on the variables from the constraints and updated bounds on the
objective and constraint functions. This enables some level of nonlinear
preprocessing in certain cases.
By combining symbolic and numerical methods, Dr. Ampl is able, to some extent,
to assess the convexity and concavity of nonlinear expressions.
As a consequence of this, we can assess the convexity of the problem and of the
feasible set.
Currently, Dr. Ampl is designed to work with problems whose objective and
constraint functions are twice continuously differentiable. Most principles apply,
however, to more general problems. We hope to extend Dr. Ampl in many
directions in the future.
Please check the how section for details on the
mechanisms making this structural analysis possible.
|