Propagation guided large neighborhood search
作者： Laurent Perron , Paul Shaw , Vincent Furnon
DOI: 10.1007/978-3-540-30201-8_35
关键词: Mathematics 、 Solver 、 Constraint programming 、 Algorithm 、 Large neighborhood search 、 Constraint satisfaction
摘要: In this article, we explore how neighborhoods for the Large Neighborhood Search (LNS) framework can be automatically defined by volume of propagation our Constraint Programming (CP) solver. Thus build non trivial which will not reduced to zero and whose size close a parameter search. Furthermore, looking at history domain reductions, are able deduce even better neighborhoods. This idea is validated numerous experiments with car sequencing problem. The result powerful completely automatic method that beat hand-written both in term performance stability. fact first time us generic code than one.
springer.com
sci-hub.se 参考文章(13)
Philippe Refalo, Impact-based search strategies for constraint programming principles and practice of constraint programming. pp. 557- 571 ,(2004) , 10.1007/978-3-540-30201-8_41
Laurent Perron, Paul Shaw, Combining Forces to Solve the Car Sequencing Problem Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. pp. 225- 239 ,(2004) , 10.1007/978-3-540-24664-0_16
Claude Le Pape, Laurent Perron, Jean-Charles Régin, Paul Shaw, None, Robust and Parallel Solving of a Network Design Problem principles and practice of constraint programming. pp. 633- 648 ,(2002) , 10.1007/3-540-46135-3_42
Emilie Danna, Laurent Perron, Structured vs. unstructured large neighborhood search: a case study on job-shop scheduling problems with earliness and tardiness costs principles and practice of constraint programming. pp. 817- 821 ,(2003) , 10.1007/978-3-540-45193-8_59
Alain Chabrier, Emilie Danna, Claude Le Pape, Laurent Perron, None, Solving a Network Design Problem Annals of Operations Research. ,vol. 130, pp. 217- 239 ,(2004) , 10.1023/B:ANOR.0000032577.81139.84
Laurent Michel, Pascal Van Hentenryck, A constraint-based architecture for local search Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications - OOPSLA '02. ,vol. 37, pp. 83- 100 ,(2002) , 10.1145/582419.582430
David Applegate, William Cook, A Computational Study of the Job-Shop Scheduling Problem Informs Journal on Computing. ,vol. 3, pp. 149- 156 ,(1991) , 10.1287/IJOC.3.2.149
Joseph Adams, Egon Balas, Daniel Zawack, The Shifting Bottleneck Procedure for Job Shop Scheduling Management Science. ,vol. 34, pp. 391- 401 ,(1988) , 10.1287/MNSC.34.3.391
Russell Bent, Pascal Van Hentenryck, A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows Transportation Science. ,vol. 38, pp. 515- 530 ,(2004) , 10.1287/TRSC.1030.0049
Jens Gottlieb, Markus Puchta, Christine Solnon, A study of greedy, local search, and ant colony optimization approaches for car sequencing problems Lecture Notes in Computer Science. ,vol. 2611, pp. 246- 257 ,(2003) , 10.1007/3-540-36605-9_23