Class PropagationGuidedNeighborhood

  • All Implemented Interfaces:
    INeighbor
    Direct Known Subclasses:
    ReversePropagationGuidedNeighborhood

    public class PropagationGuidedNeighborhood
    extends Object
    implements INeighbor
    A Propagation Guided LNS

    Based on "Propagation Guided Large Neighborhood Search", Perron et al. CP2004.

    Since:
    08/04/13
    Author:
    Charles Prud'homme
    • Field Detail

      • n

        protected final int n
        Number of variables
      • vars

        protected final IntVar[] vars
        Array of variables to consider in a fragment
      • bestSolution

        protected final int[] bestSolution
        Last solution found, wrt vars
      • dsize

        protected int[] dsize
        Domain size of each variable in vars
      • rd

        protected Random rd
        For randomness
      • fgmtSize

        protected int fgmtSize
        Intial size of the fragment
      • listSize

        protected int listSize
        Number of variables modified through propagation to consider while computing the neighbor
      • epsilon

        protected double epsilon
        Restriction parameter
      • logSum

        protected double logSum
        Logarithmic cardinality of domains
      • all

        protected int[] all
        Store the modified variables
      • candidates

        protected List<Integer> candidates
        Store the variable elligible for propagation
      • fragment

        protected BitSet fragment
        Indicate which variables are selected in a fragment
      • mModel

        protected Model mModel
        Reference to the model
    • Constructor Detail

      • PropagationGuidedNeighborhood

        public PropagationGuidedNeighborhood​(IntVar[] vars,
                                             int fgmtSize,
                                             int listSize,
                                             long seed)
        Create a propagation-guided neighbor for LNS
        Parameters:
        vars - set of variables to consider
        fgmtSize - initial size of the fragment
        listSize - number of modified variable to store while propagating
        seed - for randomness
    • Method Detail

      • isSearchComplete

        public boolean isSearchComplete()
        Specified by:
        isSearchComplete in interface INeighbor
        Returns:
        true iff the search is in a complete mode (no fixed variable)
      • recordSolution

        public void recordSolution()
        Description copied from interface: INeighbor
        Record values of decision variables to freeze some ones during the next LNS run
        Specified by:
        recordSolution in interface INeighbor
      • loadFromSolution

        public void loadFromSolution​(Solution solution)
        Description copied from interface: INeighbor
        Load a solution and record it
        Specified by:
        loadFromSolution in interface INeighbor
        Parameters:
        solution - a solution to record
      • fixSomeVariables

        public void fixSomeVariables​(DecisionPath decisionPath)
        Description copied from interface: INeighbor
        Freezes some variables in order to have a fast computation. The fixed variables are declared as decisions in the decision path.
        Specified by:
        fixSomeVariables in interface INeighbor
        Parameters:
        decisionPath - the decision path in which declaring variable to freeze
      • selectVariable

        protected int selectVariable()
        Returns:
        a variable id in vars to be part of the fragment
      • restrictLess

        public void restrictLess()
        Description copied from interface: INeighbor
        Use less restriction at the beginning of a LNS run in order to get better solutions Called when no solution was found during a LNS run (trapped into a local optimum)
        Specified by:
        restrictLess in interface INeighbor
      • init

        public void init()
        Description copied from interface: INeighbor
        Initialize this neighbor
        Specified by:
        init in interface INeighbor