[Edinburgh-pm] elastic search

[Miles Gould]

On Sat, Mar 05, 2011 at 07:35:33PM +0000, Aaron Crane wrote:
> "Binary integer programming (BIP) is the special case of integer
> programming where variables are required to be 0 or 1 (rather than
> arbitrary integers). This problem is also classified as NP-hard, and
> in fact the decision version was one of Karp's 21 NP-complete
> problems."

Curses!

> Ouch.  20 sounds fine for exhaustive search, 30 probably not, and 80
> is well into "give up and choose a different hobby" territory.

Yep. Well, it's into "throw a GA at it and hope" territory, anyway.

> I was hoping it would be some nice easy problem in register
> allocation, or something — you won't find many CPUs with more than 16
> general-purpose registers. :-)

Hmmmm. It *might* be possible to adapt a register-allocation algorithm,
somehow, but I'd have to think about that for a bit.

[Aside: Mike O'Boyle's compilers course has a wonderful slide in it,
which looks roughly like this:

WHY ARE COMPILERS HARD?

front end -----> middle end ------> back end
   ^                ^                  ^
   |                |                  |
everything's     everything's       everything's
polynomial       undecidable        NP-hard       ]

> Further, the answers are all going to be quite small — 80 bits if you
> encode them carefully enough.  Given that, and assuming this is a
> public service, it's almost certainly worth caching every answer you
> ever emit, just on the off chance someone else wants it in the future.
>  Like the same user coming back again the next day.

Excellent idea. We'd get decent reusability for the "weight is no
object" and "cost is no object" answers, at least.

> You might also consider letting users tell you which cams they already
> have; each additional such piece of information halves the size of the
> search space.

I'd want to do that anyway, to provide more relevant answers, but that's
an excellent point.

> > We can restrict to cams whose range intersects with the
> > range of interest; this would throw out a lot.
> Yes.

In particular, anything above fist-sized is considered specialist gear.

> > We might be able to throw
> > out cams that are overly-heavy or prohibitively expensive in the user's
> > locale, though this would be tricky.
> 
> If you can get additional constraints of the form "maximum rack weight
> is X", that certainly lets you discard cams which are individually
> heavier than that.  But I fear that's unlikely to be practical — for
> one thing, I bet there aren't many people who'd impose a rack weight
> smaller than the weight of many commercially available cams.  Or do
> you mean something cleverer than that?

I didn't really have a concrete idea here - I guess I was thinking if
Manufacturer X and Manufacturer Y make cams covering the same range, but
Manufacturer X's is lighter, then we can exclude consideration of
Manufacturer Y's entirely. But I don't know how common that situation
is, and I'd guess it's quite rare.

> The Wikipedia article says that there are efficient algorithms if the
> constraint matrix is, like, totally unimodular, but I didn't bother
> following the link to that definition, so I don't know whether this
> problem meets that condition.

I skimmed it, and I don't think it applies here.

> It also mentions some "advanced algorithms" for solving integer LP
> problems; maybe one of those will work for you.
> 
> I have a vague idea for a heuristic, but I've no idea if it will
> actually work in practice.
[snip]

Actually, it looks like the "branch-and-cut" algorithm is a more
sophisticated version of your approach:

http://en.wikipedia.org/wiki/Branch_and_cut

That looks worth a go, anyway.

Miles

-- 
There is no such thing as luck, only skillz.
  -- Great Teacher Largo