META’18 will held at Marrakech in Morocco on the Oct 27-31 2018. Renaud De Landtsheer Expert Research Engineer at CETIC will present: Efficient Generic Support for Global Routing Constraints in Constraint-Based Local Search Frameworks
META is one of the most popular conference focusing in the area of metaheuristics and their applications. As in the previous six editions, META’2018 will provide an opportunity to the international research community in metaheuristics for optimization and machine learning to discuss recent research results, to develop new ideas and collaborations, and to meet researchers from diverse countries in a friendly and excellent atmosphere.
Global constraint are very popular mechanism in local search because they achieve very good complexity, notably for routing problems. Our concern is on building generic re-usable framework for local search and builds on the concept of Constraint-Based Local Search. We showed how to embed global constraints for routing into CBLS framework, thanks to an extension of this framework, namely a variable of type \sequence of integers".
Developing a global constraint for our framework still requires two things. First designing a differentiation algorithm, then embedding this algorithm into the targeted framework. In this paper we identify a generic stereotype of differentiation used by global constraints and propose a generic support for this stereotype. The stereotype is an algebraic group. Our generic framework is basically an abstract class with the place holders for this algebraic group. Once this class is properly extended, it gives rise to a fully usable and efficient global constraint featuring some form differentiation. Our framework is illustrated on classical examples as well as on an intricate global constraint for vehicle capacity.
View online : META’2018