Board index » delphi » Re: Looking for an algorithm

Re: Looking for an algorithm


2006-08-07 11:37:34 PM
delphi205
Scout writes:
Quote
This is not for Walmart. They don't even exist where I push my
Delphi code.
You work in heaven!??!??!
 
 

Re: Looking for an algorithm

Eric Grange writes:
Quote
True though IME in practice the reduction of the solution space the LP
can give you is sufficient to make branch/bound or exhaustive search
feasible (the equation won't give you the solution point, but will
instead transform a near-infinite solution space into something small
enough to be dealt with).
Most LP solvers actually provide support for integer variables.
Sure, but assuming that we are not talking about millions of product
categories, discounts and purchased items, wouldn't it be at least as
efficient to do it the simple way Anders Isaksson suggested in another
post, e.g. in conjunction with some clever listing and sorting using
hash trees?
 

Re: Looking for an algorithm

Perhaps because the guy that makes the deal has limited knowledge of
computers?
"somebody" <XXXX@XXXXX.COM>writes
Quote
"Scout" <XXXX@XXXXX.COM>writes

>Any suggestions for appropriate data structures or algorithms will be
>much appreciated.

I have to ask: What's the point of making promotions so convoluted that
even
writing the code to pick the best deal becomes an exercise in frustration?
I'd say "everything 5% off"...



 

Re: Looking for an algorithm

Quote
Sure, but assuming that we are not talking about millions of product
categories, discounts and purchased items, wouldn't it be at least as
efficient to do it the simple way Anders Isaksson suggested in another
post, e.g. in conjunction with some clever listing and sorting using
hash trees?
It would all depends on how simple the rules/equations involved in
describing the deals are. The risk with Anders' method being that you
could end up having to code/maintain dozens of mini-solvers with
case-specific heuristics. As not having them and relying on exhaustive
search could leave you high and dry if you have a high number of deal
combinations (even in trivial cases).
For instance if your deals are:
- Get 3 A for the price of 2 A
- Get 2 A + B for the price of 2 A
If the amount of A and B you need is less than a dozen, an exhaustive
search of all combinations will succeed. But if the amount you need are
in the thousandths, an exhaustive search would stall, even though the
problem is then dead simple (for a human).
With a LP approach you would be able to narrow it down to the relevant
handful of cases directly (mostly a matter of rounding one way or
another), whatever the amounts involved.
Eric
 

Re: Looking for an algorithm

Hi, first of all you need to define your criteria and your results.
Well there are actually two ways to approach this depending on how complex
you want it.
1. Create 3 tables (or similar structures) OFFER, CRITERIA, RESULTS with
sample structure:
OFFER
ID*
NAME
CRITERIA
OFFER_ID*
PRODUCT_ID*
MINQTY
MAXQTY
LISTPRICE
RESULTS
OFFER_ID
PRODUCT_ID
DISCOUNTTYPE (monetary, percentage,unitprice)
DISCOUNT
With the above set of structure you can supports all the scenarios you
describe. DiscountType refers to what you want the discount to be.
Monetary: 10$ off
Percentage: 10% off
Unitprice: 2.5$ per unit
Whatever you do, at the end you will have for example 2 products and a final
price. You can use the weighted average algorithm to proportionally reduce
the price of every item.
"Scout" <XXXX@XXXXX.COM>writes
Quote
Hi,
I have a specific problem to solve, but I can not think of an
appropriate algorithm. Can you suggest anything?

The problem manifests itself in many ways, any or all of which could
overlap.

The simplest way to describe it is: Buy 1 get one free (or bogof).

If you buy 2 cans of soda, you get the second for $0.

If you buy 3 cans, 1 is free. If you buy 4 cans, 2 are free.

There's also a need to set a limit (e.g. 10) buy 30 cans get 10 free,
buy 40 cans, you still get only 10 free.

So far, so simple.

Now if you introduce another deal which says "Buy a can of soda and a
can of pineapple slices, get the slices for free" what should happen
when the can of soda is $1, the slices are $2 and you buy 2 cans of soda
and 1 can of slices. Do you pay $1 each for the 2 cans of soda and get
the slices free (total cost $2) or $1 for 1 can of soda, $2 for the
slices and get the 2nd can of soda free (total cost $3).

The one rule I have is that if you could do a better deal buy buying
the items separately, then that is how the deal should work when you buy
them all together.

To further complicate matters, there could be other deals in place
that say "Buy more than 3 cans of soda, and get all of them for 10%
off" or "Buy more than 2 cans of pineapple slices and get them for $1.50
each".

In any particular sale, there could be any of about 250,000 product
lines, with any of 5,000 different deals set up, and the code has to
figure out the BEST way of grouping them together so that the customer
gets the best result from all of the possible deals, and it has to do
this INSTANTLY.

To my mind, it looks like the classic travelling salesman problem, but
where both the origin and destination are unknown.

The actual set of circumstances is even more complex than what I have
described here, but it comes down to trying to work out each deal where
1 deal could steal a qualifying item from another deal (thereby
invalidating the second deal) or vice-versa, but I still need the
optimal solution.

Any suggestions for appropriate data structures or algorithms will be
much appreciated.

Scout
 

Re: Looking for an algorithm

Forgot to mention that the second way would be to add vbscript support to
you applicaiton and a whole bunch of IF's
 

Re: Looking for an algorithm

Eric Grange writes:
Quote
For instance if your deals are:
- Get 3 A for the price of 2 A
- Get 2 A + B for the price of 2 A
If the amount of A and B you need is less than a dozen, an exhaustive
search of all combinations will succeed. But if the amount you need are
in the thousandths, an exhaustive search would stall, even though the
problem is then dead simple (for a human).
True.
Quote
With a LP approach you would be able to narrow it down to the relevant
handful of cases directly (mostly a matter of rounding one way or
another), whatever the amounts involved.
Not necessarily. There might be cases where you can not independently
choose between some 20 or more discounts. Even if you have been able to
determine that discount D1 is to be applied either 3 times or 4 times,
discount D2 either 2 times or 3 times, ... and discount D20 either 0
times or 1 time, you might still have ended up with thousands or in
worst case over a million different combinations, depending on how the
discounts depend on each other.
 

Re: Looking for an algorithm

Scout:
You might want to state if there is a limited budget ... Knapsack
Problem (How many discrete units of something can I fit in the container
-- knapsack) -- which can be in the NP class if the problem is large
enough. (Integer quantities)
This looks like a Cost problem where you are trying to figure out the
most cost effective purchasing scheme -- or are you trying to move the
maximum amount of inventor, or generate highest revenues?
You might also want to state the size of the problem...
You did say n deals? Is that correct? If so it is in the NP class of
problem and I recommend the CRC handbook "Algorithms and Theory of
Computation".
NP = non-polynomial time....
I leave it to you to look at the variations.
In Scheduling Theory you try to write and "Objective Function" -- i.e.
-- what is your objective? Without a goal it is tough to solve...
e.g.
Minimize Cost
Maximize Sales
Maximize units Sold
Maximum units for minimum cost...
The you may be able to "soften" the problem and come up with an
approximation function...
In the NP class -- you test for whether a generated solution works. You
cannot write a function that generates a known working solution. (That's
what makes it NP -- hard complete or otherwise...) So most of the
methods involve writing a algorithm which tends to be more likely to
generate a solution which is more likely to "test good".
In other words I don't think any of us have a clue as to the problem you
are trying to solve...
Scout writes:
Quote
Hi,
I have a specific problem to solve, but I can not think of an
appropriate algorithm. Can you suggest anything?

The problem manifests itself in many ways, any or all of which could
overlap.

The simplest way to describe it is: Buy 1 get one free (or bogof).

If you buy 2 cans of soda, you get the second for $0.

If you buy 3 cans, 1 is free. If you buy 4 cans, 2 are free.

There's also a need to set a limit (e.g. 10) buy 30 cans get 10 free,
buy 40 cans, you still get only 10 free.

So far, so simple.

Now if you introduce another deal which says "Buy a can of soda and a
can of pineapple slices, get the slices for free" what should happen
when the can of soda is $1, the slices are $2 and you buy 2 cans of soda
and 1 can of slices. Do you pay $1 each for the 2 cans of soda and get
the slices free (total cost $2) or $1 for 1 can of soda, $2 for the
slices and get the 2nd can of soda free (total cost $3).

The one rule I have is that if you could do a better deal buy buying
the items separately, then that is how the deal should work when you buy
them all together.

To further complicate matters, there could be other deals in place
that say "Buy more than 3 cans of soda, and get all of them for 10%
off" or "Buy more than 2 cans of pineapple slices and get them for $1.50
each".

In any particular sale, there could be any of about 250,000 product
lines, with any of 5,000 different deals set up, and the code has to
figure out the BEST way of grouping them together so that the customer
gets the best result from all of the possible deals, and it has to do
this INSTANTLY.

To my mind, it looks like the classic travelling salesman problem, but
where both the origin and destination are unknown.

The actual set of circumstances is even more complex than what I have
described here, but it comes down to trying to work out each deal where
1 deal could steal a qualifying item from another deal (thereby
invalidating the second deal) or vice-versa, but I still need the
optimal solution.

Any suggestions for appropriate data structures or algorithms will be
much appreciated.

Scout
--
Will R
PMC Consulting
 

Re: Looking for an algorithm

WillR writes:
Quote
In the NP class -- you test for whether a generated solution works. You
cannot write a function that generates a known working solution. (That's
what makes it NP -- hard complete or otherwise...)
Not exactly. You can very well write a function that solves a NP hard
problem: Exhaustive search is the trial example. The only thing is that
it will execute in non-polynomial time or require non-polynomial amounts
of data.
Furthermore, you can write a function that solves an NP hard problem in
P time just as long as you have made all the right pre-calculations
(i.e. the function utilizes a NP large table of relevant data you have
generated in advance).
 

Re: Looking for an algorithm

Henrick Hellström [StreamSec] writes:
Quote
WillR writes:
>In the NP class -- you test for whether a generated solution works.
>You cannot write a function that generates a known _(optimum)_ working solution.
>(That's what makes it NP -- hard complete or otherwise...)

Not exactly. You can very well write a function that solves a NP hard
problem: Exhaustive search is the trial example.
If you can solve it by exhaustive search then it is a small problem
space and doesn't qualify... :-)
Quote
The only thing is that
it will execute in non-polynomial time
i.e unsolvable.... sufficient condition
Quote
or require non-polynomial amounts
of data.
Not sure what that means... :-)
But regardless -- Then it isn't solved is it? :-)
Quote
Furthermore, you can write a function that solves an NP hard problem in
P time just as long as you have made all the right pre-calculations
That is an approximation -- in my book any way. Or the problem isn't
within your definition or mine of an NP Hard Problem. :-)
Quote
(i.e. the function utilizes a NP large table of relevant data you have
generated in advance).
I think we are saying much the same thing... But the definitions in my
reference books say what I wrote.
However, let's be specific. If a problem is NP-Hard (Or whatever) we
cannot know if the solution is optimal -- we can only know that it is
_a_ solution. All of the things that you have mentioned create _trial_
solutions. Only by comparison to other solutions do you know which is
the best -- but none of them may be optimal or close to optimal --
unless you can derive an approximation algorithm (or function if you
will) that allows you to determine the bounds of an optimal solution.
You can write a function (algorithm) that generates a _Possible_
solution -- that you must test to see if it meets the criteria of the
required solution.
Of course there are many methods to "solve" NP Hard problems -- but what
you have to keep in mind is that they are approximations of solutions --
or a subset based on restrictions of the problem space.
When we go back to the definition it states that the problem cannot be
solved in "Polynomial Time" -- i.e. in any useful time span.
That is why I suggested that he be quite specific as to the "Objective
Function" and the problem "Space" -- when the problem is correctly
classified then perhaps some _useful_ advice can be generated.
Perhaps the fellow should get a copy of the "Ready to Run" algorithms
Sorry for the Long URL
www.chapters.indigo.ca/books/item/books-978047125400/0471254002/Ready+To+Run+Delphi+30+Algorithms+Time+Saving+Blueprints+For
Regardless -- we're pronging... :-))
--
Will R
PMC Consulting
 

Re: Looking for an algorithm

On Mon, 7 Aug 2006 19:14:10 +1200, Scout <XXXX@XXXXX.COM>writes:
Quote
Hi,
I have a specific problem to solve, but I can not think of an
appropriate algorithm. Can you suggest anything?
Assign each possible deal a deal #, record these deal #'s on all items
that participate in the deal. As you get items retrieve the deal data
and have it available in memory for calculation. As you bring a deal
into memory record the maximum amount the deal could save the
customer.
For each deal # on your list use it to pull out a linked set of deals.
These sets should be quite small and readily subject to brute force if
you're careful about how you handle quantities. The deal on soda +
slices has no connection to the deal on chips + beer, you can solve
the problems independantly.
I was going to suggest taking the biggest values first but this
doesn't work. Counterexample: A + B saves $1. B + C saves $1.50. C
+ D saves $1.
 

Re: Looking for an algorithm

On Mon, 7 Aug 2006 13:03:54 -0400, "Wayne Niddery [TeamB]"
<XXXX@XXXXX.COM>writes:
Quote
- find all non-cumulative deals that *could* be applied based on the
products purchased (ignore qty).
- psuedo-apply each to find out the savings it would provide, then order
descending by those savings
- apply each in turn, removing the product quantity each application applies
to. As this is done, it might result in further deals no longer being
applicable, but that is alright, customer has already got best deal for
those particular items.

- now repeat the above 3 steps on any applicable deals that are allowed to
be cumulative.
I've already found a case that breaks this. The right answer might
skip the best deal.
 

Re: Looking for an algorithm

WillR writes:
Quote
>Not exactly. You can very well write a function that solves a NP hard
>problem: Exhaustive search is the trial example.

If you can solve it by exhaustive search then it is a small problem
space and doesn't qualify... :-)
Of course it does. NP only means that the running time of the algorithm
depends exponentially or sub exponentially on some parameter. If this
parameter is bounded in a particular case, the algorithm might be
practical even though it is O(2^n) on that parameter (or whatever).
In the case of the OP for instance, a combination of linear equation
solving and exhaustive search might be practically feasible if certain
assumption can be made about the discounts that are to be entered. Such
as: There will at no time be more than 10 deals that involve more than
one product, etc.
Quote
>The only thing is that it will execute in non-polynomial time

i.e unsolvable.... sufficient condition
Wrong. O(2^n) is non-polynomial, but if n is small it is perfectly
feasible. The difference between an O(n) algorithm and an O(2^n)
algorithm is that the latter grows unfeasible much faster, but you can't
say if either is "unsolvable" or not unless you know the bounds of n.
Quote
>or require non-polynomial amounts of data.

Not sure what that means... :-)
It means that you might theoretically calculate all solutions to the
problem in advance and store them in a hash table. The actual algorithm
would then have O(log(n)) running time.
 

Re: Looking for an algorithm

"John Herbster" <herb-sci1_at_sbcglobal.net>writes
Quote
"Scout" <XXXX@XXXXX.COM>wrote
>I have a specific problem to solve, but I can not think of an
>appropriate algorithm. Can you suggest anything? ...

Scout,
Have you tried the tried the forum
borland.public.algorithms
This is a sure sign that I am psychic.
I knew this was coming.
--
Thanks,
Brad.
 

Re: Looking for an algorithm

Henrick Hellström [StreamSec] writes:
Quote
WillR writes:
>>Not exactly. You can very well write a function that solves a NP hard
>>problem: Exhaustive search is the trial example.
>
>If you can solve it by exhaustive search then it is a small problem
>space and doesn't qualify... :-)

Of course it does. NP only means that the running time of the algorithm
depends exponentially or sub exponentially on some parameter. If this
parameter is bounded in a particular case, the algorithm might be
practical even though it is O(2^n) on that parameter (or whatever).
reduction of search space -- I think that is what I said -- so glad we
agree on that. Think you have said that as well.
Quote
In the case of the OP for instance, a combination of linear equation
solving and exhaustive search might be practically feasible if certain
assumption can be made about the discounts that are to be entered. Such
as: There will at no time be more than 10 deals that involve more than
one product, etc.
Reduction of search space -- agreed -- that works. But since we still
don't even know what the problem is... it is a little tough to offer advice.
Quote
>>The only thing is that it will execute in non-polynomial time
>
>i.e unsolvable.... sufficient condition

Wrong. O(2^n) is non-polynomial, but if n is small it is perfectly
feasible. The difference between an O(n) algorithm and an O(2^n)
algorithm is that the latter grows unfeasible much faster, but you can't
say if either is "unsolvable" or not unless you know the bounds of n.


>>or require non-polynomial amounts of data.
>
>Not sure what that means... :-)

It means that you might theoretically calculate all solutions to the
problem in advance and store them in a hash table.
That's an interesting thought... How would you do that for this type of
problem?
Quote
The actual algorithm
would then have O(log(n)) running time.
Assuming that you could calculate all the possibilities for an NP Hard
problem -- or did you mean after you did the above -- a search space
reduction?
And I think you mean the approximation algorithm -- not the actual (NP
Hard) algorithm. And again I am assuming the "actual" means "original".
Anyway tough to discuss this without knowing the problem...
--
Will R
PMC Consulting
 

Re: Looking for an algorithm

WillR writes:
Quote
>It means that you might theoretically calculate all solutions to the
>problem in advance and store them in a hash table.

That's an interesting thought... How would you do that for this type of
problem?

>The actual algorithm would then have O(log(n)) running time.


Assuming that you could calculate all the possibilities for an NP Hard
problem -- or did you mean after you did the above -- a search space
reduction?
The way I read the OP there will automatically be a "search space
reduction" at the time the products, prices and discounts are entered
into the system. The most important requirement (as far as I understand)
is that the implementation for customer check out must be blinking fast.
If it is OK to let the back office server run some pre computations for
one or two hours after a discount has been entered, it might be possible
to calculate the solution to all decision problems that would otherwise
take one or two seconds at customer check out. This would reduce the
customer check out algorithm to linear equation solving plus a table
lookup, instead of linear equation solving plus exhaustive search.