Re: [eclipse-users] Implementing constraint propagation in Local Search

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.

Olli