Class MoveBinaryHBFS

  • All Implemented Interfaces:
    Move

    public class MoveBinaryHBFS
    extends MoveBinaryDFS
    A move dedicated to run an Hybrid Best-First Search[1] (HBFS) with binary decisions.

    [1]:D. Allouche, S. de Givry, G. Katsirelos, T. Schiex, M. Zytnicki, Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP, CP-2015.

    It restarts anytime a backtrack limit is reached and a new open right branch needs to be selected.

    Created by cprudhom on 02/11/2015. Project: choco.

    Since:
    02/11/2015.
    Author:
    Charles Prud'homme
    • Constructor Detail

      • MoveBinaryHBFS

        public MoveBinaryHBFS​(Model model,
                              AbstractStrategy strategy,
                              double a,
                              double b,
                              long N)
        Create a move dedicated to run an Hybrid Best-First Search[1] (HBFS) with binary decisions.
        Parameters:
        model - a model
        strategy - the search strategy to use
        a - lower bound to limit the rate of redundantly propagated decisions.
        b - upper bound to limit the rate of redundantly propagated decisions.
        N - maximum number of backtracks to not exceed when updating node recomputation parameters.
    • Method Detail

      • init

        public boolean init()
        Description copied from interface: Move
        Called before the search starts. Also initializes the search strategy.
        Specified by:
        init in interface Move
        Overrides:
        init in class MoveBinaryDFS
        Returns:
        false if something goes wrong, true otherwise
      • extend

        public boolean extend​(Solver solver)
        Description copied from interface: Move
        Performs a move when the CSP associated to the current node of the search space is not proven to be not consistent.
        Specified by:
        extend in interface Move
        Overrides:
        extend in class MoveBinaryDFS
        Parameters:
        solver - reference the solver
        Returns:
        true if an extension can be done, false when no more extension is possible.
      • repair

        public boolean repair​(Solver solver)
        Description copied from interface: Move
        Performs a move when the CSP associated to the current node of the search space is proven to be not consistent.
        Specified by:
        repair in interface Move
        Overrides:
        repair in class MoveBinaryDFS
        Parameters:
        solver - reference the solver
        Returns:
        true if a reparation can be done, false when no more reparation is possible.
      • extractOpenRightBranches

        protected void extractOpenRightBranches​(Solver solver)
        This methods extracts and stores all open right branches for future exploration
        Parameters:
        solver - reference to the solver