[rules-users] Existence of feasible solution for planner problem

[ge0ffrey]

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-planner-problem-tp3918673p3919695.html
Sent from the Drools: User forum mailing list archive at Nabble.com.