Heuristic

[Nathan Rice]

I solve optimization problems like this all the time using branch and bound.
Just arrange the possible scenarios into a state space tree, (ideally
ordered by lowest average cost supplier) then prune any branch where the
best case scenario given supplier cost plus shipping cost summed over all
remaining orders is greater than your current best total cost.  You can make
it pretty fast in python if you implement memoization of supplier
fulfillment costs for orders.  All you need to do is write a depth first
search algorithm (stack based, not recursive), a best case predictor for a
single order fulfillment (which is summed over all unfulfilled orders) and
an actual cost for order fulfillment function.  It's really easy to put
together, and tends to work quite well.

On Fri, Jun 25, 2010 at 7:24 AM, Marcos <marcosruapuga at gmail.com> wrote:

> On 25 jun, 04:00, MRAB <pyt... at mrabarnett.plus.com> wrote:
> > Terry Reedy wrote:
> > > On 6/24/2010 9:13 PM, Marcos wrote:
> > >> I have a store, so I want to maximize the profit. I have all the
> > >> suppliers with diferent prices, some providers can send products to a
> > >> client an others not, this has a plus price. Some providers has a
> > >> discount over the tansport if a quantity is reached.
> >
> > >> Sometimes its better to me receive the order and resend to the client
> > >> if I have a transport discount.
> >
> > >> Not all the suppliers has all products for a order.
> >
> > >> So I want to create a function which I can pass the data, and
> > >> generates all the possibilities so I can find the maximum profit.
> >
> > >> Have I to use heuristics? Do you know some examples?.
> >
> > > You would not use a heuristic to generate all possibilities. You might
> > > use one to *avoid* doing that, and still get a good, not necessarily
> > > optimal, answer.
> >
> > True. Basically there are two ways of approaching the problem. One is to
> > try all the combinations, which will guarantee that you'll find the best
> > solution, but if there are an enormous number of combinations then that
> > could take a very long time. The other way is to use a heuristic to get
> > an reasonable solution in an reasonable time. It's a trade-off.
> >
> >  > Wikipedia has an general entry on 'heuristic'.
> >  > Algorithm books often specifically discuss heuristic algorithms.
>
> Do you know it there is some way to generate all the scenario
> possibilities?. So I Can put an array an data an generate all. I have
> the lack of repeated elements that I cant solve.
>
> Thanks.
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100625/0066d29e/attachment.html>