Class KBranchingScheme

java.lang.Object
com.artelys.kalis.KBranchingScheme
Direct Known Subclasses:
KAssignAndForbid, KAssignVar, KBranchingSchemeGroupSerializer, KFloatVarBranchingScheme, KIntervalDomain, KIntVarBranchingScheme, KParallelBranchingScheme, KProbe, KProbeDisjunction, KSettleDisjunction, KSplitDomain, KSplitNumDomain, KTaskSerializer

public class KBranchingScheme extends 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
     
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
     
    Constructor
    protected
    KBranchingScheme​(long cPtr, boolean cMemoryOwn)
     
     
     
     
    Constructor with a given problem
     
    KBranchingScheme​(com.artelys.kalis.SWIGTYPE_p_KBranchingScheme_I branchingScheme)
     
  • 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
     
     
    protected static long
     
    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
     
    Return the name of the branching scheme
    Return the current problem
    void
    Pretty printing of the branching scheme
    void
    setSolver_I_ptr​(com.artelys.kalis.SWIGTYPE_p_KSolver_I solver_I)
     
    protected void
     
    void
     
    void
     

    Methods inherited from class java.lang.Object

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

    • swigCMemOwn

      protected transient boolean swigCMemOwn
  • Constructor Details

    • 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)
    • KBranchingScheme

      public KBranchingScheme(KBranchingScheme toCopy)
  • Method Details

    • getCPtr

      protected static long getCPtr(KBranchingScheme obj)
    • finalize

      protected void finalize()
      Overrides:
      finalize in class 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 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
    • getCopyPtr

      public KBranchingScheme getCopyPtr()
    • getInstanceCopyPtr

      public KBranchingScheme getInstanceCopyPtr(KProblem problem)
    • setSolver_I_ptr

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