Class ExplainingCut

  • All Implemented Interfaces:
    INeighbor
    Direct Known Subclasses:
    ExplainingObjective

    public class ExplainingCut
    extends Object
    implements INeighbor
    a specific neighborhood for LNS based on the explanation of the cut imposed by a new solution.

    This neighborhood is specific in the sense that it needs to compute explanation after a new solution has been found. Furthermore, the fixSomeVariables method creates and applies decisions, so that the explanation recorder can infer.
    It works as follow: - on a solution: force the application of the cut together with the decision path which leads to the solution, explain the failure - then, on a call to fixSomeVariables, it selects randomly K decisions explaining the cut, and relax them from the decision path.

    Unrelated decisions are never relaxed, the idea here is to work only on the decisions which lead to a failure.

    Since:
    03/07/13

    TODO: fix some variables TODO: catch up case when the sub tree is closed and this imposes a fragment

    Author:
    Charles Prud'homme
    • Field Detail

      • mExplanationEngine

        protected IExplanationEngine mExplanationEngine
        The explanation engine that computes explanation on solution
      • random

        protected final Random random
        For randomness purpose
      • mDecisionPath

        protected List<IntDecision> mDecisionPath
        A copy of the decision path which led to the solution
      • related

        protected BitSet related
        Indicates which decisions are related to the explanation in mDecisionPath
      • unrelated

        protected BitSet unrelated
        Indicates which decisions are not related to the explanation in mDecisionPath
      • notFrozen

        protected BitSet notFrozen
        Indicates which decisions are frozen in the current fragment
      • forceCft

        protected boolean forceCft
        Indicates if the cut has already been explained
      • nbFixedVariables

        protected double nbFixedVariables
        Number of decisions to fix in the fragment
      • nbCall

        protected int nbCall
        Number of times this neighbor is called
      • mModel

        protected Model mModel
        Reference to the model
    • Constructor Detail

      • ExplainingCut

        public ExplainingCut​(Model aModel,
                             int level,
                             long seed)
        Create a neighborhood which analyses the explanation of the cut wrt decision path to focus on decisions more prone to not interact with the cut
        Parameters:
        aModel - the model
        level - the relaxing factor
        seed - a seed for randomness
    • Method Detail

      • init

        public void init()
        Description copied from interface: INeighbor
        Initialize this neighbor
        Specified by:
        init in interface INeighbor
      • 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
      • _fixVar

        protected void _fixVar()
        Regarding the explanation, pick decisions to create a 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
      • isSearchComplete

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

        protected void increaseLimit()
        Increase the relaxing limit
      • clonePath

        protected void clonePath()
        Compute the initial fragment, ie set of decisions to keep.
      • explain

        protected void explain()
        Force the failure, apply decisions to the last solution + cut => failure!