[Edinburgh-pm] elastic search

[Miles Gould]

> > Anyone know any good
> > algorithms for solving integer programming problems where the variables
> > (but not the coefficients) must be 0 or 1?
> 
> Isn't that NP-hard, even with the restriction that the variables must
> be binary?

I'm not sure. It's certainly NP-hard without that restriction. Even with
the restriction it feels like it should be easy to convert into some
kind of satisfiability problem.

> How many variables are you dealing with?  O(2**n) can be tractable,
> given sufficiently small n and constant factors...

Hmmmmmmm. That depends on the question the user wants answered,
unfortunately. Average case is probably about 20-30, worst case is about
80. It might be worth cacheing the worst-case calculation, because
that's the one everyone's going to try first to test the site out :-)

I should probably explain the actual problem at this point. In rock
climbing, it's common to protect climbs with spring-loaded camming
devices (or just "cams" for short). You insert a cam into a handy crack
in the rock, clip your rope to it and then climb past; if you fall, then
the downward force on the cam will cause it to bite harder into the rock
and arrest your fall. Modern cams can literally hold the weight of a
car:

http://www.dmmclimbing.com/video.asp?id=2

Cams revolutionised rock climbing when they were invented in the 70s:
suddenly, loads of routes were merely scary instead of unprotectable
death routes. But there are two problems with cams: they're expensive
and heavy. Well, make that three problems: each cam can only grip cracks
whose width is within a given range, so your "rack" needs to contain
cams of the correct sizes for your route. Here's an investigation of
current cams on the market, and a calculation of their
weight-efficiency.

http://www.summitpost.org/size-matters-a-gear-comparison/694359

But, I thought, this sounds like a linear programming problem. We just
need to ask a user what range of cracks they're likely to want to
protect (to a first approximation, this is a feature of the crag and
rock type you're climbing on), and then we can use MATHS!!!!11!!7!! to
calculate the minimum-weight set of cams that covers that range. Treat
each 1mm range as a binary coefficient (we need to protect 203-204mm
cracks/we don't need to), treat each type of cam as a variable, have
"sum of weights" as our objective function, and throw Algorithm::Simplex
at it. Even better, we could use "sum of costs" as our objective
function to get the cheapest possible rack, or a linear combination of
the two (obtained by asking the user "how much would you pay to shave
10g off your rack?") and get a personalised "best rack for you"
calculation.

Then I realised that Algorithm::Simplex would probably tell me to buy
2/7 of a Black Diamond #4 and 1/3 of a DMM #3, and that this would be
precisely no use to me. So I googled for "integer programming", and
discovered that this was NP-hard :-(

So, anyway. We can restrict to cams whose range intersects with the
range of interest; this would throw out a lot. 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. And we can coalesce ranges to
minimise the number of coefficients to consider. But that still leaves
us with an uncomfortably large n for an O(2**n) search.

Thoughts?

Miles

-- 
Oh god, you're patient zero aren't you? Let the feline-avian viral
apocalypse commence! And just in time for the weekend, too.
  -- Richard Morgan