设为首页
收藏本站
网站地图
|
English
|
公务邮箱
About the library
Background
History
Leadership
Organization
Readers' Guide
Opening Hours
Collections
Help Via Email
Publications
Electronic Information Resources
A unified framework for partial and hybrid search methods in constraint programming
详细信息
查看全文
作者:
Simon de Givry and
Laurent
Jeannin
关键词:
Design
;
Languages
;
Constraint programming
;
Combinatorial optimization
;
Search strategies
;
Tree search
;
Large neighborhood search
刊名:Computers and Operations Research
出版年:2006
出版时间:October 2006
年:2006
卷:33
期:10
页码:2805-2833
全文大小:367 K
文摘
We present a library called
for the design of complex tree search algorithms in constraint programming (CP). We separate the description of a search algorithm into three parts: a refinement-based search scheme that defines a complete search tree, a set of conditions for visiting nodes that specifies a parameterized partial exploration, and a strategy for combining several partial explorations. This library allows the expression of most of the partial, i.e. nonsystematic backtracking, search methods, and also a specific class of hybrid local/global search methods called large neighborhood search, which are very naturally suited to CP. Variants of these methods are easy to implement with the
primitives. We demonstrate the expressiveness and efficiency of the library by solving a satellite mission management benchmark that is a mix between a traveling salesman problem with time windows and a Knapsack problem. Several partial and hybrid search methods are compared. Our results dramatically outperform CP approaches based on classical depth-first search methods.
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via
email
.