> Otherwise my experience is that asking for a general purpose solver is, for now, hopeless.
> Instead, for the real problems I've had success with, have to look carefully at the problem and exploit special structure particular to that problem.
I am in complete agreement.
One way I have thought about this is that, rather informally, "the mapping from problems to solutions is highly discontinuous". That is, suppose you have a problem statement, and you figure out a method to attack the problem and solve it in practice. Now, vary the problem statement slightly. There is a reasonable chance that the new problem is dramatically harder to solve, and you need a completely different body of theory to even think about it, let alone solve it.
For example, suppose you have a polynomial equation in a bunch of complex variables. This is easily solved numerically in practice to any degree of precision you care for. Let's reword the problem a little and require that you are only willing to accept integer-valued solutions. Now you're talking about Diophantine equations! Have fun!
In practice, if you're participating in some project to solve business / industrial problems using optimisation, it is pretty common to have the definition of the problem change slightly every few weeks or months, as you learn more about the domain, or as people change their minds, or as the business actually changes what it does. Often you need to figure out clever ways of exploiting the mathematical structure in a particular problem statement to figure out a tractable way of solving the problem. Best to hope that the new version of your problem doesn't suddenly break that structure while you're "sprinting" towards the next release!
IMHO it has been, since the
1950s, mostly this "sprinting"
that was in practice just too
difficult, that is, too costly
in time and money, for far too
large a fraction of organizations,
budgets, managers, etc. that
could have used optimization.
Now with current computing and
the Internet, a lot in applied
math, in principal powerful and
valuable for important real problems,
seems to be growing significantly
in popularity.
The "sprinting"
is much easier but, sadly,
too often still too challenging.
Of course part of the "sprinting"
challenge was solved by, say,
A Mathematical Programming Language
(AMPL) where can just type in
something like
max z = f(x)
subject to g(x) >= 0
x in C
where for large positive integers
m and n and the real numbers R,
x in R^m and g: R^m --> R^n.
So, then, with the problem thusly
typed in, just need a solver!
Right: Maybe from the back side
of one of the moons of Pluto?
Gee, we know how to sort, know a
lot about sorting, in O( n log(n) ),
etc., so maybe we should have
solvers that would do as well
on optimization as we can do now
on sorting? Then quickly
we encounter the monster of the
question P versus NP.
So, without an algorithm that shows
that P = NP, we're back to
column generation here, Lagrangian
relaxation there, branch and bound
too often, some group theory
sometimes, etc. and "sprinting".
Yes, it was interesting
philosophically how central
and challenging P versus NP
is, but I'd rather have just
had a way to solve optimization
problems routinely, gotten
home in time for dinner, and spent
Sunday at a BBQ!
> Instead, for the real problems I've had success with, have to look carefully at the problem and exploit special structure particular to that problem.
I am in complete agreement.
One way I have thought about this is that, rather informally, "the mapping from problems to solutions is highly discontinuous". That is, suppose you have a problem statement, and you figure out a method to attack the problem and solve it in practice. Now, vary the problem statement slightly. There is a reasonable chance that the new problem is dramatically harder to solve, and you need a completely different body of theory to even think about it, let alone solve it.
For example, suppose you have a polynomial equation in a bunch of complex variables. This is easily solved numerically in practice to any degree of precision you care for. Let's reword the problem a little and require that you are only willing to accept integer-valued solutions. Now you're talking about Diophantine equations! Have fun!
In practice, if you're participating in some project to solve business / industrial problems using optimisation, it is pretty common to have the definition of the problem change slightly every few weeks or months, as you learn more about the domain, or as people change their minds, or as the business actually changes what it does. Often you need to figure out clever ways of exploiting the mathematical structure in a particular problem statement to figure out a tractable way of solving the problem. Best to hope that the new version of your problem doesn't suddenly break that structure while you're "sprinting" towards the next release!