Class KBranchingScheme

  • Direct Known Subclasses:
    KAssignAndForbid, KAssignVar, KBranchingSchemeGroupSerializer, KFloatVarBranchingScheme, KIntervalDomain, KIntVarBranchingScheme, KParallelBranchingScheme, KProbe, KProbeDisjunction, KSettleDisjunction, KSplitDomain, KSplitNumDomain, KTaskSerializer

    public class KBranchingScheme
    extends java.lang.Object
    Abstract class defining branching schemes.
    Search is made thanks to a tree search algorithm. At each node, propagation
    is made and if no solution exists, Artelys Kalis needs to split your problem
    in smaller subproblems covering (or not) all the initial problem. This
    partition is made following a branching scheme.

    Different types of branching schemes exist. For example, a classical way is
    to choose a variable which has not been instantiated so far and to build a
    sub-problem for each remaining value in the variable's domains, this
    sub-problem being the original problem where the variable has been
    instantiated to this value. And then, you can continue the search with these
    new nodes.

    Choosing the right branching schemes to be used with your particular problem
    could greatly improve the performance of the tree search. Artelys Kalis
    allows you to choose between many classical branching schemes provided with
    the library and to easily program yourself the more specialized branching
    schemes that you suppose to be useful for your own problems.

    Since:
    2016.1
    See Also:
    KSplitDomain KSettleDisjunction KProbe
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected boolean swigCMemOwn  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean _finishedBranching​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation, int currentBranchNumber)
      Return true IFF branching is completed on one specific branch of the
      branch and bound.

      void _freeAllocatedObjectsForBranching​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation)
      This method is called upon finishing branching for the current node and
      allows freeing objects created at the current node.

      com.artelys.kalis.SWIGTYPE_p_void _getNextBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation, int currentBranchNumber)
      Return the next branch to explore

      void _goDownBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation, int currentBranchNumber)
      This method is called once a branch has been selected and a decision must
      be taken.

      void _goUpBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation, int currentBranchNumber)
      This method is called upon backtrack on a specific branch

      com.artelys.kalis.SWIGTYPE_p_void _selectNextBranchingObject()
      Select the next object (variable in general) to branch on when one branch
      has been explored.
      void delete()  
      protected void finalize()  
      KBranchingScheme getCopyPtr()  
      protected static long getCPtr​(KBranchingScheme obj)  
      com.artelys.kalis.SWIGTYPE_p_std__string getGoDownDescription​(com.artelys.kalis.SWIGTYPE_p_void branchingObject, com.artelys.kalis.SWIGTYPE_p_void branchingInformation, int currentBranchNumber)
      Return a string representation of the branching decision
      KBranchingScheme getInstanceCopyPtr​(KProblem problem)  
      java.lang.String getName()
      Return the name of the branching scheme
      KProblem getProblem()
      Return the current problem
      void printName()
      Pretty printing of the branching scheme
      void setSolver_I_ptr​(com.artelys.kalis.SWIGTYPE_p_KSolver_I solver_I)  
      protected void swigDirectorDisconnect()  
      void swigReleaseOwnership()  
      void swigTakeOwnership()  
      • Methods inherited from class java.lang.Object

        clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • swigCMemOwn

        protected transient boolean swigCMemOwn
    • Constructor Detail

      • KBranchingScheme

        protected KBranchingScheme​(long cPtr,
                                   boolean cMemoryOwn)
      • KBranchingScheme

        public KBranchingScheme()
        Constructor
      • KBranchingScheme

        public KBranchingScheme​(KProblem problem)
        Constructor with a given problem
      • KBranchingScheme

        public KBranchingScheme​(com.artelys.kalis.SWIGTYPE_p_KBranchingScheme_I branchingScheme)
    • Method Detail

      • finalize

        protected void finalize()
        Overrides:
        finalize in class java.lang.Object
      • delete

        public void delete()
      • swigDirectorDisconnect

        protected void swigDirectorDisconnect()
      • swigReleaseOwnership

        public void swigReleaseOwnership()
      • swigTakeOwnership

        public void swigTakeOwnership()
      • getProblem

        public KProblem getProblem()
        Return the current problem
      • _selectNextBranchingObject

        public com.artelys.kalis.SWIGTYPE_p_void _selectNextBranchingObject()
        Select the next object (variable in general) to branch on when one branch
        has been explored.
      • _finishedBranching

        public boolean _finishedBranching​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                          com.artelys.kalis.SWIGTYPE_p_void branchingInformation,
                                          int currentBranchNumber)
        Return true IFF branching is completed on one specific branch of the
        branch and bound.

        Parameters:
        branchingObject - the branching object
        branchingInformation - the branching information
        currentBranchNumber - the current branch number
      • _getNextBranch

        public com.artelys.kalis.SWIGTYPE_p_void _getNextBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                                                com.artelys.kalis.SWIGTYPE_p_void branchingInformation,
                                                                int currentBranchNumber)
        Return the next branch to explore

        Parameters:
        branchingObject - the branching object
        branchingInformation - the branching information
        currentBranchNumber - the current branch number
      • _goDownBranch

        public void _goDownBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                  com.artelys.kalis.SWIGTYPE_p_void branchingInformation,
                                  int currentBranchNumber)
        This method is called once a branch has been selected and a decision must
        be taken.

        Parameters:
        branchingObject - the branching object
        branchingInformation - the branching information
        currentBranchNumber - the current branch number
      • _goUpBranch

        public void _goUpBranch​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                com.artelys.kalis.SWIGTYPE_p_void branchingInformation,
                                int currentBranchNumber)
        This method is called upon backtrack on a specific branch

        Parameters:
        branchingObject - the branching object
        branchingInformation - the branching information
        currentBranchNumber - the current branch number
      • _freeAllocatedObjectsForBranching

        public void _freeAllocatedObjectsForBranching​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                                      com.artelys.kalis.SWIGTYPE_p_void branchingInformation)
        This method is called upon finishing branching for the current node and
        allows freeing objects created at the current node.

        Parameters:
        branchingObject - the branching object
        branchingInformation - the branching information
      • printName

        public void printName()
        Pretty printing of the branching scheme
      • getName

        public java.lang.String getName()
        Return the name of the branching scheme
      • getGoDownDescription

        public com.artelys.kalis.SWIGTYPE_p_std__string getGoDownDescription​(com.artelys.kalis.SWIGTYPE_p_void branchingObject,
                                                                             com.artelys.kalis.SWIGTYPE_p_void branchingInformation,
                                                                             int currentBranchNumber)
        Return a string representation of the branching decision
      • setSolver_I_ptr

        public void setSolver_I_ptr​(com.artelys.kalis.SWIGTYPE_p_KSolver_I solver_I)