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, KIntervalDomain, KIntVarBranchingScheme, 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.