Just to complete my first ideas:
Once you have your time partition in slots, and ads assigned in them
in an obvious way, you can use drools-planner to optimize on more
complex criteria / contraints with a simple swap move.
You can then handle preference in times for ads, or forbid some ads
chains ("don't pepsi just next coca-cola" or more generally do not
put "same domain" ads together) or anything else ...
Contraints programming could be great for that too, but far less
expressive as rules can be...
Of course all of this suppose that the "100% sold" amount of click
is a constant ...
Le 31/12/2010 12:23, Vincent Legendre a écrit :
Hi,
If I understand well :
- you have only one ad at a time, displayed at least 10 minutes
and at most 60 minutes, and I suppose that ads cannot be
fractionned.
- ads can be ordered by their "value" for one click
The main objective is to maximize the total number of valuated
clicks, e.g. "fill" the most valuable ads with clicks,
So the problem is finding some good time partition in "living"
periods for the most valuable ads as possible.This tends to put
the most valuable ads in peaks, then continue to the next, find a
remaining peak, etc etc ... But the problem not so obvious if
because of min/max bound on the "living" periods.
The question is :
- do you have other constraints/criteria (preferences of ads in
time, forbidden ad chains ...)
To try to anser to your question, my feeling is that a local
solver may be really good only if you first build a initial
solution that is not so bad. Otherwise, as I suppose you have real
big datasets, it may be too slow. You may have to decompose your
problem first (by day), then redo a global optimization on
agregated solution.
Try to think about what your moves can be :
- for instance, it could be a simple swap. If your amount of
"100% sold" clicks is constant, if will only move the two ads. For
that, it is easy to predict the gain of this move
- but I guess you will also need a time-shifting move (move
this ad for 5 minutes before), and this one will be tricky ...
If your amount of "100% sold" clicks is constant, may be you can
partition your time in slots (of 10 minutes min), and assign tasks
sequentially in them. This way you don't need any more
optimisation ...
Le 30/12/2010 23:13, Dave Wellman a écrit :
All,
Maybe someone could offer some smart pointers on how to best
setup a drools planning project where I am trying to optimize ad
display.
The project game plan is:
* At any one time there is only one ad in play across all 4K+
sites.
* Ads are scored and ranked by value and potential of generating
a click. We know what ad is the most valuable down to the
least.
* Each of the 10,080 minutes in a week is scored by how much
traffic is seen at that minute. (the curve is a predictable 7
peak mountain. Each peak is variable but around 2:00 PM EST
with the biggest peak on Thursday and lowest on Sunday. Valleys
are around 3:00 am. A small hemigog around 10:00 and 12:00
weekdays.
* Each ad is "in play" from between 10 to 60 minutes. Meaning
that one ad is displayed across all properties for at least 10
minutes and a most 60.
* Once a add gets a certain number of clicks it is "100% sold"
and then removed from the queue. If an ad is sold before the 60
minutes is up it is removed and the next ad in line take its
place. If it is under 10 minutes it will stay in play and
continue to be "sold" until the first 10 minutes is up.
Is drools scheduler the right tool for this job or could you
suggest something better?
Thank you for any insights you all have.