Re: Anyone interested in being paid to find a solution to a commercial problem?

Toni Lassila wrote:
On 28 Feb 2006 02:33:03 -0800, josh@xxxxxxxxxxxxxx wrote:

We are software developers for the vacation rental business. We need
to code an availability search (in Microsoft SQL Server) to find the
cheapest combination of properties that will accommodate a given
capacity. Testing all possible combinations is not an option as forty
properties will yield roughly a trillion combinations. We have got to
the point where we take each property in turn, starting with the
cheapest in terms of cost per head, and then adding the next cheapest
and so on, until greater than or equal to the required capacity is
reached. If that capacity is reached EXACTLY, we then have a solution.
So far so good. But if we have gone over the required capacity, there
is a possibility that a different mix with a lower capacity will be
cheaper, even if the cost per head of capacity is higher, as a result
of the spare capacity in going over what is required rather than
matching it exactly.

This sounds like fairly elementary binary linear programming. Of
course, actual implementation could be difficult if the properties
have complicated dependencies with each other (like "if you want X you
need Y unless you get Z, in which case you can't get W"). If you can
get all the constraints sorted out there are well-known algorithms for
solving the problem.

We also need to be able to implement a solution WITHIN SQL Server as it
is extremely complex and difficult to call external software (we have
attempted unsuccessfully to do this with commercial linear programming
solutions).

However, from experience I can tell you that writing it all in T-SQL
is a non-trivial task. I think if you proceed in this way you'll face
more technical difficulties with the SQL Server implementation than
the actual optimization algorithms.

A binary linear program with 40 binary variables would not be practical
(in this case). If I understand the problem correctly, this is the
knapsack problem. The original poster mentions exact matches, but I am
assuming a non-exact match can be optimal, e.g. to house 11 heads you
may find three 4-head properties for less cost then a 6-head and
5-head.

The knapsack problem is NP-complete in the general case, but that
doesn't mean it cannot be solved. q.v. dyanamic programming, etc.

.

Relevant Pages