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


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.


On the surface this sounds like it's related to the knapsack problem.
Only instead of trying to maximize the value where the total size of
the collection of objects is less than some limit, you're coming from
the other side and trying to minimize the value of a collection of
objects whose size is at least some limit. For the traditional
knapsack problem, (which is NP-complete in terms of a general
solution), there is a reasonable dynamic programming solution when all
of the object sizes are small integers (which is obviously the case in
your problem).

It is also similar in some respects to the bin packing problem.

In both cases there is considerable literature, perhaps some research
in those directions might help.

.

Relevant Pages