KIntVarBranchingScheme¶

class KIntVarBranchingScheme : public 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.

See: KBranchingScheme KFloatVarBranchingScheme KAssignAndForbidd KSplitDomain KSettleDisjunction KProbe
Since: 2016.1

Public Functions

KIntVarBranchingScheme()¶: Constructor.

KIntVarBranchingScheme(KProblem *problem)¶: Constructor with KProblem.

KIntVarBranchingScheme(const KIntVarBranchingScheme &toCopy)¶: Copy constructor.

virtual KIntVar *selectNextBranchingVar()¶: Select the next KIntVar to branch on when one branch has been explored

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

virtual int *getNextBranch(KIntVar *branchingObject, int *branchingInformation, int currentBranchNumber)¶

Return the next branch

Parameters

branchingObject – the branching object
branchingInformation – the branching information
currentBranchNumber – the current branch number

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

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

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

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 std::string getGoDownDescription(void *branchingObject, void *branchingInformation, int currentBranchNumber)¶: Return a string representation of the branching decision.