A unified framework for partial and hybrid search methods in constraint programming

DOI10.1016/J.COR.2005.01.012MaRDI QIDQ2489124zbMATH OpenOpenAlexFDO

Authors Simon de Givry, L. Jeannin

Publication date 16 May 2006

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://hal.inrae.fr/hal-02659665/file/A%20unified%20framework%20for%20partial%20and%20hybrid%20search%20methods%20in%20constraint%20programming_1.pdf

zbMATH Keywords

Combinatorial optimizationConstraint programmingDesignLanguagesLarge neighborhood searchSearch strategiesTree search

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Review text

We present a library called ToOLS 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 ToOLS 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.

Recommendations

• Constraint Programming and Local Search Hybrids
• A constraint programming framework for local search methods
• Hybrid Algorithms in Constraint Programming
• Combining local and global search in a constraint programming environment
• Logic Programming
• Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes
• A new approach to partial constraint satisfaction problems

Cites work

• A Computational Study of the Job-Shop Scheduling Problem
• A constraint programming framework for local search methods
• A decomposition-based implementation of search strategies
• Algorithm portfolios
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Branch and Infer: A Unifying Framework for Integer and Finite Domain Constraint Programming
• CLAIRE: combining sets, search and rules to better express algorithms
• Combining VNS with constraint programming for solving anytime optimization problems
• Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems
• Heuristics for large constrained vehicle routing problems
• scientific article; zbMATH DE number 2084747 (Why is no real title available?)
• scientific article; zbMATH DE number 1406246 (Why is no real title available?)
• Localizer
• Phase transitions and the search problem
• Real-time heuristic search
• SALSA: a language for search algorithms
• Search and strategies in OPL
• Solving various weighted matching problems with constraints
• Using constraint-based operators to solve the vehicle routing problem with time windows
• Variable neighborhood decomposition search
• Variable neighborhood search

Cited in

(4)

• MCS---a new algorithm for multicriteria optimisation in constraint programming
• The DeltaUp constraint solver: Minimizing the number of method selections in DeltaBlue
• Valued constraint satisfaction problems
• Nondeterministic control for hybrid search

Describes a project that uses

Uses Software

• Choco
• Localizer
• OPL
• BL data set
• CLAIRE
• ToOLS

This page was built for publication: A unified framework for partial and hybrid search methods in constraint programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489124)