______________________________________________________________________
Date:  Thursday 19 August 2015
Time:  15:15
Venue: Room 1212, House 1, ITC, Polacksbacken, Uppsala University
______________________________________________________________________

                      Conflict Ordering Search

 Renaud Hartert (http://becool.info.ucl.ac.be/members/renaud-hartert)

                Université catholique de Louvain, Belgium

This presentation introduce a new generic scheme to guide backtrack
search, called Conflict Ordering Search (COS), that reorders variables
on the basis of conflicts that happen during search. Similarly to
generalized Last Conflict (LC) [Lec09], our approach remembers the
last variables on which search decisions failed. Importantly, the
initial ordering behind COS is given by a specified variable ordering
heuristic, but contrary to LC, once consumed, this first ordering is
forgotten, which makes COS conflict-driven. Our preliminary
experiments show that COS -- although simple to implement and
parameter-free -- is competitive with specialized searches on
scheduling problems. We also show that our approach fits well within a
restart framework, and can be enhanced with a value ordering heuristic
that selects in priority the last assigned values.
______________________________________________________________________

Directions: http://www.polacksbacken.uu.se/Find_us/