David Tian wrote: > Hi, > I am trying to combine local search with constraint propagation (LS+CP) so that > after an value-update of a variable, constraint propagation will be trigerred. > The parts on the Repair Lib in the manuals do not seem to mention how to do it > using the Repair lib. I am just wondering is there any examples of LS+CP in > ECLiPSe? > > Many thanks, > David Hi David, Yes there have been quite a lot of Eclipse implementations for LS hybrid algorithms where the neighbourhood operator does CP propagation as well as CP search. One way is to use the repair library as you tried. In addition to the manual http://eclipse.crosscoreop.com/doc/libman/libman.html, take a look at the tutorial as well: http://eclipse.crosscoreop.com/doc/tutorial/index.html But in addition to the repair library you can implement LS+CP hybrids in other ways too, eg by setting up the constraint model separately, but maintaining the LS assignments elsewhere. When you want to trigger the propagation, you instatiate the actual problem variables with the LS assignment values. (Then you may want to store the result and/or other information elsewhere, but you must backtrack all the instatiations to be able to use the constraint model at later LS steps.) With Eclipse you can do lots of different variations of this kind of hybrids, e.g. instantiating just some variables per LS step and letting CP (or other) search to label the remaining variables. You may also want to rethink the constraint model whether it makes sense in the first place to trigger heavy propagation at each LS search step, or you can even decompose the algorithm further such that LS+CP solves a sub-problem containing just some of the constraints. Anyway, it's all very problem specific and depends on what you are looking for. There are dozens and dozens of papers about all kinds of local search hybrids from past 15 years, including the type you are investigating - you may find good examples for your problem. OlliReceived on Mon Feb 12 2007 - 01:49:43 CET
This archive was generated by hypermail 2.3.0 : Wed Sep 25 2024 - 15:13:20 CEST