Artelys Dualis
A numerical component for the solution
of large scale combinatorial problems
Decomposition of large scale combinatorial
problems
Many industrial problems are modeled as combinatorial optimization
problems: staff planning, logistics, distribution, production
management.
Often, large instances of complex problems cannot be solved
by a single method. Breaking down the initial problem into
a series of simpler ones can make its solution easier. Artelys
Dualis is a non differentiable convex optimization tool very
useful in the framework of decomposition and coordination
methods, such as the Lagrangian relaxation.
Presentation of Artelys Dualis
Artelys Dualis is an effective and robust numerical component
for minimizing (resp. maximizing) non-differentiable convex
(resp. concave) functions. For instance, Artelys Dualis is
extremely useful to implement Lagrangian relaxation methods.
Indeed, up-dating the multipliers in a Lagrangian relaxation
framework requires the maximization of a non-differentiable
concave function (the dual function).
Artelys Dualis is based on the bundle method. To minimize
a convex function, this method minimizes a sequence of piecewise
linear approximations, built using cuts of the initial convex
function. In order to limit memory usage, the bundle method
selects and maintains only a limited number of these cuts.
A dedicated powerful quadratic programming algorithm guarantees
stabilization. The bundle method makes it possible to prove
optimality at a given precision, as opposed to other convex
minimization techniques like sub-gradient methods.
A robust and flexible component, yet
easy to use
Artelys Dualis is a C++ library of very simple use. Communication
between Artelys Dualis and the calling program is as follows:
Artelys Dualis returns a new iterate; the calling program
computes the objective function and a subgradient at this
point and sends their values back to Artelys Dualis; and so
on.
This so called "reverse" communication allows easy
integration into existing codes. One need not be an optimization
expert to use Artelys Dualis, as its default settings proved
very robust and efficient. However, if the user wishes to
do so, these setting can be modified. It is also possible
to impose bounds on the variables. Finally Artelys Dualis
will be useful in a Branch-and-Bound framework if bounds are
estimated by means of Lagrangian relaxation.
Artelys Dualis is available under Windows, Linux and Sun Solaris.
Academic partnership
Artelys proposes partnership programs with universities and
other public training and research centers. These partnerships
aim at promoting teaching and research in optimization.
Contact
For more information, please contact
us at:
•
Tel: +33 1 44 77 89 00
•
E-mail: info-dualis@artelys.com
Back
to the top |
