Class KIntVarBranchingScheme

java.lang.Object
com.artelys.kalis.KBranchingScheme
com.artelys.kalis.KIntVarBranchingScheme

public class KIntVarBranchingScheme extends KBranchingScheme
Abstract class for Branching scheme. 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. This branching scheme is suited for branching on KIntVar objects
only.

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

    Fields inherited from class com.artelys.kalis.KBranchingScheme

    swigCMemOwn
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
     
    Constructor
    protected
    KIntVarBranchingScheme​(long cPtr, boolean cMemoryOwn)
     
     
    Copy constructor
     
    Constructor with KProblem
  • Method Summary

    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
    Select the next object (variable in general) to branch on when one branch
    has been explored.
    void
     
    protected void
     
    boolean
    finishedBranching​(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
    Return true IFF branching is completed on one specific branch of the branch and bound

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

     
    protected static long
     
    com.artelys.kalis.SWIGTYPE_p_std__string
    getGoDownDescription​(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
     
    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
     
    com.artelys.kalis.SWIGTYPE_p_int
    getNextBranch​(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
    Return the next branch

    Return the current problem
    void
    goDownBranch​(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
    This method is called once a branch has been selected and a decision must be taken

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

    Select the next KIntVar to branch on when one branch has been explored
    protected void
     
    void
     
    void
     

    Methods inherited from class com.artelys.kalis.KBranchingScheme

    getCPtr, getName, printName, setSolver_I_ptr

    Methods inherited from class java.lang.Object

    clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • KIntVarBranchingScheme

      protected KIntVarBranchingScheme(long cPtr, boolean cMemoryOwn)
    • KIntVarBranchingScheme

      public KIntVarBranchingScheme()
      Constructor
    • KIntVarBranchingScheme

      public KIntVarBranchingScheme(KProblem problem)
      Constructor with KProblem
    • KIntVarBranchingScheme

      public KIntVarBranchingScheme(KIntVarBranchingScheme toCopy)
      Copy constructor
  • Method Details

    • getCPtr

      protected static long getCPtr(KIntVarBranchingScheme obj)
    • finalize

      protected void finalize()
      Overrides:
      finalize in class KBranchingScheme
    • delete

      public void delete()
      Overrides:
      delete in class KBranchingScheme
    • swigDirectorDisconnect

      protected void swigDirectorDisconnect()
      Overrides:
      swigDirectorDisconnect in class KBranchingScheme
    • swigReleaseOwnership

      public void swigReleaseOwnership()
      Overrides:
      swigReleaseOwnership in class KBranchingScheme
    • swigTakeOwnership

      public void swigTakeOwnership()
      Overrides:
      swigTakeOwnership in class KBranchingScheme
    • getProblem

      public KProblem getProblem()
      Description copied from class: KBranchingScheme
      Return the current problem
      Overrides:
      getProblem in class KBranchingScheme
    • selectNextBranchingVar

      public KIntVar selectNextBranchingVar()
      Select the next KIntVar to branch on when one branch has been explored
    • finishedBranching

      public boolean finishedBranching(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int 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_int getNextBranch(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
      Return the next branch

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

      public void goDownBranch(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int 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(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int 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(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int 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
    • getGoDownDescription

      public com.artelys.kalis.SWIGTYPE_p_std__string getGoDownDescription(KIntVar branchingObject, com.artelys.kalis.SWIGTYPE_p_int branchingInformation, int currentBranchNumber)
    • _selectNextBranchingObject

      public com.artelys.kalis.SWIGTYPE_p_void _selectNextBranchingObject()
      Description copied from class: KBranchingScheme
      Select the next object (variable in general) to branch on when one branch
      has been explored.
      Overrides:
      _selectNextBranchingObject in class KBranchingScheme
    • _finishedBranching

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

      Overrides:
      _finishedBranching in class KBranchingScheme
      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)
      Description copied from class: KBranchingScheme
      Return the next branch to explore

      Overrides:
      _getNextBranch in class KBranchingScheme
      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)
      Description copied from class: KBranchingScheme
      This method is called once a branch has been selected and a decision must
      be taken.

      Overrides:
      _goDownBranch in class KBranchingScheme
      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)
      Description copied from class: KBranchingScheme
      This method is called upon backtrack on a specific branch

      Overrides:
      _goUpBranch in class KBranchingScheme
      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)
      Description copied from class: KBranchingScheme
      This method is called upon finishing branching for the current node and
      allows freeing objects created at the current node.

      Overrides:
      _freeAllocatedObjectsForBranching in class KBranchingScheme
      Parameters:
      branchingObject - the branching object
      branchingInformation - the branching information
    • 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
      Overrides:
      getGoDownDescription in class KBranchingScheme
    • getCopyPtr

      public KBranchingScheme getCopyPtr()
      Overrides:
      getCopyPtr in class KBranchingScheme
    • getInstanceCopyPtr

      public KBranchingScheme getInstanceCopyPtr(KProblem problem)
      Overrides:
      getInstanceCopyPtr in class KBranchingScheme