×

zbMATH — the first resource for mathematics

A search-infer-and-relax framework for integrating solution methods. (English) Zbl 1133.68430
Barták, Roman (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems.; Second international conference, CPAIOR 2005, Prague, Czech Republic, May 31 – June 1, 2005. Refereed proceedings. Berlin: Springer (ISBN 978-3-540-26152-0/pbk). Lecture Notes in Computer Science 3524, 243-257 (2005).
Summary: We present an algorithmic framework for integrating solution methods that is based on search, inference, and relaxation and their interactions. We show that the following are special cases: branch and cut, CP domain splitting with propagation, popular global optimization methods, DPL methods for SAT with conflict clauses, Benders decomposition and other nogood-based methods, partial-order dynamic backtracking, various local search metaheuristics, and GRASPs (greedy randomized adaptive search procedures). The framework allows elements of different solution methods to be combined at will, resulting in a variety of integrated methods. These include continuous relaxations for global constraints, the linking of integer and constraint programming via Benders decomposition, constraint propagation in global optimization, relaxation bounds in local search and GRASPs, and many others.
For the entire collection see [Zbl 1131.68003].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Software:
Chaff; SIMPL
PDF BibTeX XML Cite
Full Text: DOI