Re: [rules-users] Existence of feasible solution for planner problem
YuraK wrote
I'm new in Drools Planner. I'm investigating the Hospital bed planning
(PAS - Patient admission scheduling) problem,
I'm interesting about an existence of feasible solution for the current
problem.
The idea is follow:
1) Doctor/User is sending a request (booking bed for patient). The drools
planner application is checking if the feasible solution still exists
after the adding of new problem facts.
- if solution exists then user will retrieve a response that the request
has been handled by the application
- if solution doesn't exist then user will retrieve a response that the
request can't be handled by the application
2) At the end of day the main optimization procedure is running by Drools
Planner and all user retrieve the detail messages about the booked bed in
the hospital (e.g information about the bed location).
*Does it possible to check somehow (at the first stage) if the feasible
solution exists (all hard and soft constraints are satisfied) without
running the main(general) optimization procedure and spending a lot of
time for the getting response ?
No, the problem is NP complete, which means that no algorithm in the world
today can guarantee that a feasible solution exists for an arbitrary dataset
in reasonable time.
More info for this old, 1 billion dollar question:
http://en.wikipedia.org/wiki/P_versus_NP_problem
But that doesn't mean we can't answer that question fast with good accuracy:
1) Run planner in real-time. See last part of this video:
http://vimeo.com/25902052
2) Add new data as soon as it comes in
3a) If the real-time planner finds a feasible solution, notify the user that
it's ok. Like in the video, this should be in milliseconds on seconds. There
are no false positives.
3b) If the real-time planner doesn't find a feasible solution in 5 seconds,
notify the user that it's not ok. This might be a false negative, but if
you'd let a human planner do the same task, he would output far more false
negatives.
YuraK wrote
*I want to avoid the situation when the user send the request and waiting
a lot for the response if the request has been accepted by the
application.
*Does it possible to solve the problem via termination conditions?*
For example: after some steps of drools planner (e.g. 1000 steps) the
score is still not a zero (not all conditions are satisfied) then can i be
sure that feasible solution doesn't exists?
No (see wikipedia link above). No algorithm today will be able to answer
that with 100% accuracy in reasonable time as the problem scales out. But
given some time, planner can easily get to a 99% accuracy. How much time?
That depends on your use case: Use Planner's Benchmarker toolkit to prove by
sampling that you have such an accuracy.
YuraK wrote
I will be appreciated if somebody provides some similar examples or ideas
how to handle this situation.
Thanks.
--
View this message in context:
http://drools.46999.n3.nabble.com/Existence-of-feasible-solution-for-plan...
Sent from the Drools: User forum mailing list archive at Nabble.com.