Carnegie Mellon University
Browse
A Search-Infer-and-Relax Framework for Integrating Solution Metho.pdf.pdf' (131.99 kB)

A Search-Infer-and-Relax Framework for Integrating Solution Methods

Download (131.99 kB)
journal contribution
posted on 2012-01-01, 00:00 authored by John N. Hooker
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.

History

Publisher Statement

All Rights Reserved

Date

2012-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC