Board index » delphi » Re: Looking for an algorithm
Tom Corey
Delphi Developer |
Tom Corey
Delphi Developer |
Re: Looking for an algorithm2006-08-07 11:37:34 PM delphi205 Scout writes: QuoteThis is not for Walmart. They don't even exist where I push my |
Henrick Hellström [StreamSec]
Delphi Developer |
2006-08-07 11:45:25 PM
Re: Looking for an algorithm
Eric Grange writes:
QuoteTrue though IME in practice the reduction of the solution space the LP 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? |
indy
Delphi Developer |
2006-08-08 12:19:45 AM
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 |
Eric Grange
Delphi Developer |
2006-08-08 12:26:20 AM
Re: Looking for an algorithmQuoteSure, but assuming that we are not talking about millions of product 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 |
indy
Delphi Developer |
2006-08-08 12:31:46 AM
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 QuoteHi, |
indy
Delphi Developer |
2006-08-08 12:36:43 AM
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 |
Henrick Hellström [StreamSec]
Delphi Developer |
2006-08-08 01:17:21 AM
Re: Looking for an algorithm
Eric Grange writes:
QuoteFor instance if your deals are: QuoteWith a LP approach you would be able to narrow it down to the relevant 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. |
WillR
Delphi Developer |
2006-08-08 03:44:41 AM
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: QuoteHi, PMC Consulting |
Henrick Hellström [StreamSec]
Delphi Developer |
2006-08-08 05:48:24 AM
Re: Looking for an algorithm
WillR writes:
QuoteIn the NP class -- you test for whether a generated solution works. You 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). |
WillR
Delphi Developer |
2006-08-08 06:11:33 AM
Re: Looking for an algorithm
Henrick Hellström [StreamSec] writes:
QuoteWillR writes: QuoteThe only thing is that Quoteor require non-polynomial amounts QuoteFurthermore, you can write a function that solves an NP hard problem in Quote(i.e. the function utilizes a NP large table of relevant data you have 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 |
Loren Pechtel
Delphi Developer |
2006-08-08 06:32:04 AM
Re: Looking for an algorithm
On Mon, 7 Aug 2006 19:14:10 +1200, Scout <XXXX@XXXXX.COM>writes:
QuoteHi, 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. |
Loren Pechtel
Delphi Developer |
2006-08-08 06:32:04 AM
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 |
Henrick Hellström [StreamSec]
Delphi Developer |
2006-08-08 06:48:15 AM
Re: Looking for an algorithm
WillR writes:
Quote>Not exactly. You can very well write a function that solves a NP hard 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 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. would then have O(log(n)) running time. |
Brad White
Delphi Developer |
2006-08-08 07:09:02 AM
Re: Looking for an algorithm
"John Herbster" <herb-sci1_at_sbcglobal.net>writes
Quote"Scout" <XXXX@XXXXX.COM>wrote -- Thanks, Brad. |
WillR
Delphi Developer |
2006-08-08 07:22:01 AM
Re: Looking for an algorithm
Henrick Hellström [StreamSec] writes:
QuoteWillR writes: QuoteIn the case of the OP for instance, a combination of linear equation Quote>>The only thing is that it will execute in non-polynomial time QuoteThe actual algorithm 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 |
Henrick Hellström [StreamSec]
Delphi Developer |
2006-08-08 07:45:18 AM
Re: Looking for an algorithm
WillR writes:
Quote>It means that you might theoretically calculate all solutions to the 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. |