KSolver¶

class KSolver¶
KSolver is the main class for solving problems defined in a KProblem instance.
Once the problem has been fully built, we can begin to look for solutions. For this, the main class to be used is KSolver, which allows us to :
look for one solution
look for all solutions
look for another solution when we already know some of them
look for the optimal solution according to the problem objective
KSolver mySolver(myProblem);
When performing its solving functionalities, our object mySolver will store all solutions in the myProblem object. Retrieving these solutions and working on them is the subject of the next section.
In order to find only one solution to our problem, we would write:
mySolver.solve();
The solve() method looks for any valid solution and stores it in the associated KProblem object.
In order to fine all solutions to the problem, we would write :
mySolver.findAllSolutions();
The findAllSolutions() method searches for all solutions of the problem and stores them in the associated KProblem object.
When the problem is too large, it can be very time consuming to search for all solutions. If one needs to obtain more than one unique solution, then he should use the KSolver findNextSolution() method. For example :
for (int solutionIndex = 0; solutionIndex < 5; ++solutionIndex) mySolver.findNextSolution(); mySolver.endLookingForSolution();
The findNextSolution() method searches for the next solution and stop in a restartable state. To go back to the state before search, it is necessary to call the endLookingForSolution() method after the successive calls to findNextSolution().
In order to find the optimal solution to the problem, we would write:
mySolver.optimize();
The optimize() method searches for the optimal solutions according to the problem objective and stores it in the associated KProblem object.
In order to fine tune the search, one may set integer or double control parameters using the setIntControl() and setDblControl() methods.
Statistics on the search can be obtained using the getIntAttrib() and getDblAttrib() methods.
Multithreaded search is automatically activated provided that the KProblem object holds multiple problem instances and that the KSolver::NumberOfThreads control parameter is greater than 1.
 See
 Version
2016.1
Public Types

enum SearchLimitAttrib¶
Search limit attributes
Values:

enumerator SearchLimitUnreached¶
Search has not been limited.

enumerator SearchLimitedByNodes¶
Search has been limited by maximum number of nodes explored.

enumerator SearchLimitedBySolutions¶
Search has been limited by maximum number of solutions found.

enumerator SearchLimitedByTime¶
Search has been limited by time.

enumerator SearchLimitedByBacktracks¶
Search has been limited by maximum number of backtracks.

enumerator SearchLimitedByNodesBetweenSolutions¶
Search has been limited by maximum nodes between two solutions.

enumerator SearchLimitedByUser¶
Search has been limited by user.

enumerator SearchLimitUnreached¶

enum ToleranceLimitAttrib¶
Tolerance limits attributes
Values:

enumerator ToleranceLimitUnreached¶
Tolerance limit has not been reached.

enumerator OptimalityToleranceReached¶
Optimality absolute tolerance has been reached.

enumerator OptimalityRelativeToleranceReached¶
Optimality relative tolerance has been reached.

enumerator ToleranceLimitUnreached¶

enum IntAttrib¶
Integer attributes
Values:

enumerator NumberOfNodes¶
Number of nodes explored.

enumerator Depth¶
Depth of the search tree.

enumerator SearchLimitReached¶
Limit reached during resolution.

enumerator ToleranceLimitReached¶
Tolerance limit reached during resolution.

enumerator Backtracks¶
Number of backtracks.

enumerator TotalPropagationTime¶
Total time elapsed during propagation.

enumerator LastCallPropagationTime¶
Time elapsed during last propagation.

enumerator TotalPropagationIter¶
Total fix point iterations for propagation.

enumerator LastCallPropagationIter¶
Fix point iterations during last propagation.

enumerator MaxReachedDepth¶
Maximum depth reached during search.

enumerator NumberOfNodes¶

enum DblAttrib¶
Double attributes
Values:

enumerator ComputationTime¶
Total computation time.

enumerator BestBound¶
Best bound on the optimal solution.

enumerator CallBackTime¶
Time spent in callbacks.

enumerator ComputationTime¶

enum IntControl¶
Integer controls
Values:

enumerator MaxNumberOfNodes¶
Maximum number of nodes to explore.

enumerator MaxNumberOfSolutions¶
Maximum number of solutions to find.

enumerator MaxDepth¶
Maximum depth of the search tree.

enumerator MaxNumberOfBackTracks¶
Maximum number of backtracks during search.

enumerator StatsPrinting¶
Print search statistics each KSolver::StatsPrinting seconds (at max).

enumerator CheckSolutionStatus¶
Check each solution for validity.

enumerator MaxNumberOfNodesBetweenSolutions¶
Maximum number of nodes between two succesive solutions.

enumerator NumberOfThreads¶
Number of threads to be used during search. This control parameter is automatically limited by the number of instances in the KProblem object.

enumerator OptimizationAlgorithm¶
Algorithm used for optimization: less or equal to 0 (default) for branch and bound, 1 for binary search on objective interval, 2 for nary search on objective interval (available for multithreaded optimization only).

enumerator NumberOfSolutionBetweenRestarts¶
Number of solutions between search restarts : less or equal to 0 (default) for no restarts.

enumerator MaxNumberOfNodes¶

enum DblControl¶
Double controls
Values:

enumerator MaxComputationTime¶
Maximum computation time.

enumerator OptimalityTolerance¶
Absolute optimality tolerance (default value: 0.000001 for continuous objective, 1 for integer objective).

enumerator OptimalityRelativeTolerance¶
Relative optimality tolerance (default value: 0.000001 for continuous objective, 0 for integer objective).

enumerator MaxComputationTime¶
Public Functions

KSolver()¶
Default constructor

KSolver(KProblem &problem, KBranchingSchemeArray &branchingSchemeArray)¶
Constructor
 Parameters
problem – the problem to solve
branchingSchemeArray – the resolution strategy used during branch and bound to solve the problem

virtual ~KSolver()¶
Destructor

int solve()¶
Search for a solution to the problem
 Returns
0 if no solution was found, 1 otherwise

int findAllSolutions()¶
Search for all solutions to the problem
 See
IntControls DblControls
 Returns
number of solutions found

int findNextSolution()¶
Start looking for a solution to the problem or look for a new one
 See
IntControls DblControls
 Returns
0 if no solution was found

int endLookingForSolution()¶
Stop looking for solutions and restore the state before search

int optimize(const bool optimizeWithRestart = false, const bool dichotomicSearch = false)¶
Search for an optimal solution to the problem.
 See
 See
 See
IntControls DblControls
 Parameters
optimizeWithRestart – boolean indicating if the search has to be restarted after finding a solution (
dichotomicSearch – boolean indicating the type of search (linear or dichotomic) to optimize the objective variable (
 Returns
0 if no solution was found

int getIntAttrib(KSolver::IntAttrib attrib)¶
Return a integer attribute of the solver.
 See
 Parameters
attrib – the integer attribute to retrieve

double getDblAttrib(KSolver::DblAttrib attrib)¶
Return a double attribute of the solver.
 See
 Parameters
attrib – the double attribute to retrieve

int getIntControl(KSolver::IntControl control)¶
Return the value of an int control
 See
 Parameters
control – integer control to retrieve

double getDblControl(KSolver::DblControl control)¶
Return the value of a double control
 See
 Parameters
control – double control to retrieve

void setIntControl(KSolver::IntControl control, int value)¶
Set the value of an int control
 See
 Parameters
control – the int control to set
value – the value of the control

void setDblControl(KSolver::DblControl control, double value)¶
Set the value of a double control
 See
 Parameters
control – tjhe double control to set
value – value of the control

void setNodeFunctionPtr(KalisCallBackFunctionPtr ptr, void *param)¶
 Deprecated:
 Parameters
ptr – function pointer
param – user parameter passed to the function when called

void setBranchFunctionPtr(KalisCallBackFunctionPtr ptr1, KalisCallBackFunctionPtr ptr2, void *param)¶
 Deprecated:
 Parameters
ptr – function pointer
param – user parameter passed to the function when called

void setBranchingSchemeFunctionPtr(KalisCallBackFunctionPtr ptr1, void *param)¶
 Deprecated:
 Parameters
ptr – function pointer
param – user parameter passed to the function when called

void setSolutionFunctionPtr(KalisCallBackFunctionPtr ptr, void *param)¶
 Deprecated:
 Parameters
ptr – function pointer
param – user parameter passed to the function when called

void setSolverEventListener(KSolverEventListener *listener)¶
Set the solver event listener for tracking and controlling the search

void useShaving(bool use)¶
Set shaving activation flag

bool getUseShaving()¶
Return the shaving activation flag

KBranchingScheme getCurrentBranchingScheme()¶
Return the current branching scheme

KVariableSelector getCurrentVariableSelector()¶
Return the current variable selector

KValueSelector getCurrentValueSelector()¶
Return the current value selector

void *getCurrentBranchingObject()¶
Return a pointer to the current branching object

void printStats(std::ostream &fout)¶
Pretty printing of resolution statistics

void setBranchingSchemeArray(KBranchingSchemeArray &branchingSchemeArray, int solverInstance = 1)¶
Sets the branching scheme array

KBranchingSchemeArray *getDefaultBranchingSchemeArray()¶
Return the default branching scheme array

void addRelaxationSolver(KLinearRelaxationSolver *solver, bool initDefaultBranchingScheme = false)¶
Add a relaxation solver

void setUseReducedCostFixing(bool flag)¶
Use reducing cost fixing

bool localOptimization()¶
Do a local optimization