|
|
The MetaNEOS Solvers
We have been implementing solvers for important problem classes - linear and
nonlinear integer programming, stochastic programming,
combinatorial optimization, global optimization - and use them to
solve problem instances of unprecented size and complexity.
- Integer Linear Programming: FATCOP. Integer programming problems
arise in airline crew scheduling, video-on-demand placement,
manufacturing logistics, many other areas. FATCOP is an
opportunistic branch-and-bound solver that uses Condor to solve
large instances of these problems.
- Integer Nonlinear Programming: NLBranch. These problems combine the
combinatorial features of integer programming with the numerical
difficulties of nonlinear programming, making them extremely
challenging. NLBranch solved some difficult instances for the first
time.
- Quadratic Assignment Problem: MW-QAP. Despite its simple statement
- minimize the assignment cost of n facilities to n locations - it
is extremely difficult to solve even modest instances of this
problem. Problems with n>20 are difficult; problems with n>30 have
not yet been solved. QAP-BB uses a new relaxation technique,
together with a branch-and-bound strategy. We have entered the
competition for the QAP world record!
- Stochastic Programming: LShaped, VERIFY. In solving a
decision-making problem as an optimization problem, we enhance
robustness of the solution by taking uncertainty into account. (An
optimal crew schedule for an airline is not much use if it
collapses under minor weather delays!) Because of the large number
of possible scenarios we need to consider, the computational
requirements become very large. Two tools running under MWDriver -
LShaped and VERIFY - solve large stochastic linear programs and
estimate solution quality.
- Global Optimization: DGSOL, DGSOL is a distance geometry problems solver.
A parallel version of DGSOL has been developed to run in the opportunistic environment of Condor.
.
|
