KBranchingScheme

class KBranchingScheme : public KAutoExternalObject<KBranchingScheme, KBranchingScheme_I>, public KPtrArray<KBranchingScheme>

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.

See

KAssignAndForbid KSplitDomain KSettleDisjunction KProbe

Since

2016.1

Subclassed by KAssignAndForbid, KAssignVar, KBranchingSchemeGroupSerializer, KFloatVarBranchingScheme, KIntVarBranchingScheme, KIntervalDomain, KParallelBranchingScheme, KProbe, KProbeDisjunction, KSettleDisjunction, KSplitDomain, KSplitNumDomain, KTaskSerializer

Public Functions

KBranchingScheme()

Constructor.

KBranchingScheme(KProblem *problem)

Constructor with a given problem.

KProblem *getProblem() const

Return the current problem.

virtual void *selectNextBranchingObject()

Select the next object (variable in general) to branch on when one branch has been explored.

virtual bool finishedBranching(void *branchingObject, 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

virtual void *getNextBranch(void *branchingObject, void *branchingInformation, int currentBranchNumber)

Return the next branch to explore

Parameters
  • branchingObject – the branching object

  • branchingInformation – the branching information

  • currentBranchNumber – the current branch number

virtual void goDownBranch(void *branchingObject, 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

virtual void goUpBranch(void *branchingObject, 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

virtual void freeAllocatedObjectsForBranching(void *branchingObject, 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

virtual void printName() const

Pretty printing of the branching scheme.

virtual const char *getName() const

Return the name of the branching scheme.

virtual std::string getGoDownDescription(void *branchingObject, void *branchingInformation, int currentBranchNumber)

Return a string representation of the branching decision.