From: Digital Puer on
I need some help on identifying a type of "blackbox"
combinatorial optimization problem. Also, I would like
to figure out when I should look for an approximation
algorithm and when I should use some kind of randomised
search, like a genetic algorithm or hill-climbing.

To place my question in context, suppose I am first dealing
with the zero-one knapsack problem. It is a combinatorial
problem because I am either selecting or not selecting each
item to be placed into the knapsack. Now, the selection
process can be guided because it's known that if you order
the items by decreasing profit density and choose from them
in that order, you can then use an approximation algorithm
or a search heuristic like A* or branch-and-bound to get a
good solution. Here, one can immediately see how selecting
or not selecting an item has an impact on the profit and
weight of the knapsack.

Now, suppose you have a "blackbox" combinatorial problem
where you are either selecting or not selecting items,
and you want find the best selection to get the optimal
score. However, here you have no idea how to predict
the outcome from your choice. You select some items,
feed it through a function, and out pops a resulting
score. You can assume that for all inputs, some real
value other than 0 is returned, but you don't know what
is the effect of selecting any particular item, unlike
the knapsack problem. As a result, I believe it is not
possible to create an approximation algorithm or to use A*
(because an admissive heuristic is not known). You would
have to use a randomised search, like a genetic algorithm
or hill-climbing.

So my question is: what is this type of "blackbox"
combinatorial problem called? I have called it "blackbox",
but is there a more formal name or description? Are such
types of "blackbox" problems common? Perhaps this is a
machine-learning problem?

And getting back to my first question: when faced with this
type of combinatorial optimization problem, how would I
know when to stop looking for an approximation algorithm
and when I should start using a randomised search? A colleague
mentioned "convex functions", which I know about, but I don't
see how that is helpful here.
From: tchow on
In article <625dc589-25dc-452c-a02b-f6c31259452c(a)k18g2000prf.googlegroups.com>,
Digital Puer <digital_puer(a)hotmail.com> wrote:
>Now, suppose you have a "blackbox" combinatorial problem
>where you are either selecting or not selecting items,
>and you want find the best selection to get the optimal
>score. However, here you have no idea how to predict
>the outcome from your choice.

If the problem is truly a black-box problem then there is nothing you can do
other than exhaustive search. The only way you can do better is if there is
some kind of structure to the problem. For example, to use hill-climbing,
knowing the value of the function at a particular point must convey some
information about values at nearby points; if there is no such "neighborhood
structure" then moving from one point to a nearby point is not any better
than blindly jumping around the search space.

In reality, problems that arise in practice do have some structure. There
is unfortunately no general method of figuring out the best way to identify
that structure and exploit it. The best thing you can do is to identify
similar problems to yours that have been studied in the past, and see what
techniques have worked well on those related problems. The "Handbook of
Approximation Algorithms and Metaheuristics," edited by Teofilo Gonzalez,
is a good reference for this purpose. So is "Algorithmics for Hard Problems"
by Juraj Hromkovic.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: James Dow Allen on
On Feb 19, 8:32 am, tc...(a)lsa.umich.edu wrote:
> If the problem is truly a black-box problem then there is nothing you can do
> other than exhaustive search....
> In reality, problems that arise in practice do have some structure.  There
> is unfortunately no general method of figuring out the best way to identify
> that structure and exploit it....

I assume the structure in OP's problem exists, but is unknown
and too complicated to easily deduce experimentally.

Since his is simple binary selection, it would seem to be
a perfect candidate for the method of Genetic Algorithm.

James Dow Allen
From: tchow on
In article <56520ef0-199e-4dd0-bf8f-35620e0f1587(a)b7g2000pro.googlegroups.com>,
James Dow Allen <jdallen2000(a)yahoo.com> wrote:
>I assume the structure in OP's problem exists, but is unknown
>and too complicated to easily deduce experimentally.

Right.

>Since his is simple binary selection, it would seem to be
>a perfect candidate for the method of Genetic Algorithm.

I'm not sure what you're referring to. The OP mentioned a knapsack problem,
but as an example of something where he understood the structure well enough
to design an approximation algorithm. I didn't see any mention of a specific
"blackbox" problem that the OP was having trouble with.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Digital Puer on
On Feb 18, 5:32 pm, tc...(a)lsa.umich.edu wrote:
> In article <625dc589-25dc-452c-a02b-f6c312594...(a)k18g2000prf.googlegroups..com>,
> Digital Puer  <digital_p...(a)hotmail.com> wrote:
>
> >Now, suppose you have a "blackbox" combinatorial problem
> >where you are either selecting or not selecting items,
> >and you want find the best selection to get the optimal
> >score. However, here you have no idea how to predict
> >the outcome from your choice.
>
> If the problem is truly a black-box problem then there is nothing you can do
> other than exhaustive search.  The only way you can do better is if there is
> some kind of structure to the problem.  For example, to use hill-climbing,
> knowing the value of the function at a particular point must convey some
> information about values at nearby points; if there is no such "neighborhood
> structure" then moving from one point to a nearby point is not any better
> than blindly jumping around the search space.
>
> In reality, problems that arise in practice do have some structure.  There
> is unfortunately no general method of figuring out the best way to identify
> that structure and exploit it.  The best thing you can do is to identify
> similar problems to yours that have been studied in the past, and see what
> techniques have worked well on those related problems.  The "Handbook of
> Approximation Algorithms and Metaheuristics," edited by Teofilo Gonzalez,
> is a good reference for this purpose.  So is "Algorithmics for Hard Problems"
> by Juraj Hromkovic.
> --
> Tim Chow       tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences


Thanks for the reply. You mentioned "neighbourhood structure,"
namely that "knowing the value of the function at a particular point
must convey some information about values at nearby points."

Is there a formal terminology for this type of structure for the
evaluation function? For example, the function can be "structured"
or "structureless"?

If there is such a terminology, is there any published textbook or
article that states outright that "the lack of neighbourhood structure
limits the effectiveness of search-space algorithms like
hill-climbing or genetic algorithms"?

As I wrote in my original post, a theorist colleague mentioned that
it would be helpful if the function were convex, which I think would
be
an overkill example of neighbourhood structure, since a convex/concave
function would imply a global optimum, making the search very
easy.