tag:blogger.com,1999:blog-5869426.post440513861490213183..comments2020-06-04T13:40:30.612+01:00Comments on Drools & jBPM: Local search 101 (Geoffrey De Smet)Mark Proctorhttp://www.blogger.com/profile/03304277188725220501noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-5869426.post-40595871984688744852009-11-18T08:14:05.953+00:002009-11-18T08:14:05.953+00:00Hi! which package can be used to solve Patient Adm...Hi! which package can be used to solve Patient Admission SchedulingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-5869426.post-62985166042071499322008-08-06T02:11:00.000+01:002008-08-06T02:11:00.000+01:00Hello!Hi..anyone can help me to write a tabu searc...Hello!Hi..anyone can help me to write a tabu search code for MAX-2-SAT problem with large variables.<BR/>Thank you.<BR/>Urgent!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5869426.post-31894297654878557682007-06-20T19:00:00.000+01:002007-06-20T19:00:00.000+01:00Here's some code which might be able to do 2) dirt...Here's some code which might be able to do 2) dirty move checking:<BR/><BR/><BR/><BR/>class Tower {<BR/> int y;<BR/>}<BR/><BR/>// assert 8 towers, starting all with y = 0;<BR/>...<BR/><BR/>// score calculation<BR/>query twoTowersWithSameY<BR/> Tower($id : id, $y : y);<BR/> Tower(id > $id, y == $y);<BR/>end<BR/><BR/>class TowerMove {<BR/> Tower t;<BR/> int y;<BR/>}<BR/><BR/>// Generate the moves with drools<BR/>rule moveGenerator<BR/> when<BR/> $y >= 0;<BR/> $y < 8;<BR/> $tower : Tower(y != $y);<BR/> then<BR/> assertLogical(new TowerMove ($tower, $y));<BR/>end<BR/><BR/>I pick a move which I do, which becomes $lastMove,<BR/>which changes one of the tower.y's to a new number (between 0 and 8).<BR/><BR/>ok, now I 'd like a really special rule to detect dirty moves:<BR/>moves which score calculation is dirty.<BR/>I know the $lastMove, so I can put that into a global variable.<BR/>(note: $lastMove should actually be $lastUndoMove)<BR/><BR/>rule twoTowersWithSameYDirty<BR/> when<BR/> $move : Move(id != $lastMove.id);<BR/> $move.tower.y == $lastMove.tower.y<BR/> OR $move.tower.y == $lastMove.y<BR/> OR $move.y == $lastMove.tower.y<BR/> OR $move.y == $lastMove.tower.y<BR/> then<BR/> assertLogical(new Dirty($move));<BR/>endGeoffrey De Smethttps://www.blogger.com/profile/10118333179703404539noreply@blogger.comtag:blogger.com,1999:blog-5869426.post-45225105895978031832007-06-20T18:56:00.000+01:002007-06-20T18:56:00.000+01:00LDS doesn't look like a local search (as far as I ...LDS doesn't look like a local search (as far as I understand it now), so that will be hard. Nevertheless it would be interesting to see a LdsSolver one day, which can reuse some of the concepts already in the framework, such as using drools for score evaluation.<BR/><BR/>I share your concerns about evaluating all moves for each step.<BR/>TTP10 already has 1.5k I believe. I am currently investigating 2 ways of avoiding that:<BR/>1) only evaluate a subset of the moves (and possibly also re-evaluate the top 20 unmade moves of all time)<BR/>2) only evaluate the moves of which the score delta it represents has changed with the last step. (code name "holy grail of localsearch":)<BR/><BR/>I am mainly focusing on 1) for now, as 2) is ok for NTowers or NQueens, but difficult as hell for anything more complicated.Geoffrey De Smethttps://www.blogger.com/profile/10118333179703404539noreply@blogger.comtag:blogger.com,1999:blog-5869426.post-37583142324025552702007-06-18T06:44:00.000+01:002007-06-18T06:44:00.000+01:00I'm thinking of search strategies like Limited Dis...I'm thinking of search strategies like Limited Discrepancy Search. Choco talks about how you would do it using their library.<BR/> http://choco-solver.net/index.php?title=User_guide#LDS_.28Limited_discrepancy_search.29<BR/><BR/>I might be asking too much to think that Taseree would be a general search engine when you've billed it as a local search engine. One thing that concerns me (with respect to my problem domain) is that all moves must be enumerated, then the best one is chosen. This is clearly thinking locally, not globally. Plus, I anticipate having ~6K possible moves, and although the computation time should be in evaluating the moves, I'm thinking there might be a lot in just making those large lists of moves.<BR/><BR/>Can you say more about the intended use cases of Taseree?Kenhttps://www.blogger.com/profile/11583717134076863159noreply@blogger.comtag:blogger.com,1999:blog-5869426.post-55894425394430857332007-06-15T15:23:00.000+01:002007-06-15T15:23:00.000+01:00In which way would you like to guide the search?Cu...In which way would you like to guide the search?<BR/>Currently the local search implementation tries every move at every step, but I investigating several ways to avoid that:<BR/>- only check a portion of the moves each step, along with the top20 of the last step<BR/>- only recalculate "dirty moves", but I am still looking into ways of detecting those.Geoffrey De Smethttps://www.blogger.com/profile/10118333179703404539noreply@blogger.comtag:blogger.com,1999:blog-5869426.post-73078157902478288592007-06-14T02:15:00.000+01:002007-06-14T02:15:00.000+01:00I find this very exciting! I've worked a little w...I find this very exciting! I've worked a little with Choco (http://choco.sourceforge.net) but I've had problems wrapping my head around their abstractions. I came across your blog entry because I was thinking of using JBoss Rules to infer Choco constraints from my domain model (e.g. if a person is male, then x must be between 800 and 1800.) Now it looks like maybe I can do it in one system!<BR/><BR/>I'm curious to see how flexible Taseree is in allowing me to guide the search. I am attempting a large problem with thousands of variables and tens of constraints. I think I'll need to bring in a lot of domain heuristics to solve the problem.Kenhttps://www.blogger.com/profile/11583717134076863159noreply@blogger.comtag:blogger.com,1999:blog-5869426.post-15128663443088092412007-06-09T11:41:00.000+01:002007-06-09T11:41:00.000+01:00BTW, if anyone is attempting to test Taseree in it...BTW, if anyone is attempting to test Taseree in it's current state from svn, note that only the SmartTravelingTournament example currently the works out-of-the-box. I am doing some shotgun surgery and only focusing on that example at the moment.<BR/>Also, you might need to use the latest Drools 4.x snapshot.Geoffrey De Smethttps://www.blogger.com/profile/10118333179703404539noreply@blogger.com