local_search.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_LOCAL_SEARCH_HPP
#define PAAL_LOCAL_SEARCH_HPP

#include "local_search_concepts.hpp"

#include "paal/utils/fusion_algorithms.hpp"
#include "paal/utils/infinity.hpp"
#include "paal/data_structures/components/component_traits.hpp"

#include <boost/fusion/include/vector.hpp>
#include <boost/range/algorithm/max_element.hpp>

#include <utility>
#include <algorithm>
#include <functional>

namespace paal {
namespace local_search {

namespace detail {
    template <typename Delta>
    bool positive_delta(Delta && d) {
        return d > typename std::decay<Delta>::type{};
    }
}

struct find_positive_predicate {

    template <typename componentsAndSolution>
    bool operator()(componentsAndSolution &compsAndSol) const {
        auto &solution = compsAndSol.second;
        auto &comps = compsAndSol.first;
        auto && adjustmentSet = comps.template call<GetMoves>(solution);

        for (auto && move : adjustmentSet) {
            if (detail::positive_delta(comps.template call<Gain>(solution, move))) {
                if (comps.template call<Commit>(solution, move)) {
                    return true;
                }
            }
        }

        return false;
    }
};

struct first_improving_strategy {
    template <typename SearchJoin> bool operator()(SearchJoin &join) const {
        return m_satisfy(m_pred, join);
    }

  private:
    find_positive_predicate m_pred;
    data_structures::Satisfy m_satisfy;
};

struct max_functor {

    template <typename componentsAndSolution, typename AccumulatorFunctor,
              typename AccumulatorData, typename Continuation>
    bool operator()(componentsAndSolution &compsAndSol,
                    AccumulatorFunctor accumulatorFunctor,
                    AccumulatorData accumulatorData,
                    Continuation continuation) const {
        auto &comps = compsAndSol.first;
        auto &solution = compsAndSol.second;
        auto && adjustmentSet = comps.template call<GetMoves>(solution);

        //thanks to this checks move doesn't have to be default constructible
        if (boost::empty(adjustmentSet)) {
            return continuation(accumulatorFunctor, accumulatorData);
        }

        auto maxMove = *std::begin(adjustmentSet);
        auto maxGain = comps.template call<Gain>(solution, maxMove);

        for (auto && move : boost::make_iterator_range(
                 ++std::begin(adjustmentSet), std::end(adjustmentSet))) {
            auto gain = comps.template call<Gain>(solution, move);
            if (gain > maxGain) {
                maxMove = move;
                maxGain = gain;
            }
        }

        if (maxGain > accumulatorData) {
            auto commit = std::bind(std::ref(comps.template get<Commit>()),
                                    std::ref(solution), maxMove);
            return continuation(commit, maxGain);
        } else {
            return continuation(accumulatorFunctor, accumulatorData);
        }
    }
};

struct best_improving_strategy {
    template <typename SearchJoin> bool operator()(SearchJoin &join) const {
        return m_fold(m_fun, utils::always_false{}, 0, join);
    }

  private:
    max_functor m_fun;
    data_structures::polymorfic_fold m_fold;
};

struct best_strategy {
    template <typename SearchJoin> bool operator()(SearchJoin &join) const {
        return m_fold(m_fun, utils::always_false{}, minus_infinity{}, join);
    }

  private:
    max_functor m_fun;
    data_structures::polymorfic_fold m_fold;
};

namespace detail {

template <typename Solution, typename... SearchComponentsPack>
struct local_search_concepts;

template <typename Solution, typename SearchComponents,
          typename... SearchComponentsPack>
struct local_search_concepts<
    Solution, SearchComponents,
    SearchComponentsPack...> : public local_search_concepts<
    Solution, SearchComponentsPack...> {
    BOOST_CONCEPT_ASSERT(
        (concepts::search_components<SearchComponents, Solution>));
};

template <typename Solution> struct local_search_concepts<Solution> {};

} 

template <typename SearchStrategy, typename ContinueOnSuccess,
          typename ContinueOnFail, typename Solution, typename... components>
bool local_search(Solution &solution, SearchStrategy searchStrategy,
                  ContinueOnSuccess succ, ContinueOnFail fail,
                  components... comps) {
    detail::local_search_concepts<Solution, components...> concepts;
    boost::ignore_unused_variable_warning(concepts);

    using search_components_v =
        boost::fusion::vector<std::pair<components, Solution &>...>;

    search_components_v search_comps(
        std::pair<components, Solution &>(std::move(comps), solution)...);

    bool success{ false }, ret{ false };

    while ((success = searchStrategy(search_comps)) || fail(solution)) {
        ret |= success;
        if (success && !succ(solution)) {
            break;
        }
    }
    return success | ret;
}

template <typename Solution, typename... components>
bool first_improving(Solution &solution, components... comps) {
    return local_search(solution, first_improving_strategy{},
                        utils::always_true{}, utils::always_false{},
                        std::move(comps)...);
}

template <typename Solution, typename... components>
bool best_improving(Solution &solution, components... comps) {
    return local_search(solution, best_improving_strategy{},
                        utils::always_true{}, utils::always_false{},
                        std::move(comps)...);
}

template <typename Solution, typename ContinueOnSuccess, typename... components>
bool best(Solution &solution, ContinueOnSuccess on_success,
          components... comps) {
    return local_search(solution, best_strategy{}, std::move(on_success),
                        utils::always_false{}, std::move(comps)...);
}

} // local_search
} // paal

#endif // PAAL_LOCAL_SEARCH_HPP