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

A KSolver object must be associated to a specific problem. Here is how we can declare and create a KSolver which will be associated to our problem :
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.

Multi-threaded 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

KProblem

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.

See

MaxNumberOfNodes

enumerator SearchLimitedBySolutions

Search has been limited by maximum number of solutions found.

See

MaxNumberOfSolutions

enumerator SearchLimitedByDepth

Search has been limited by maximal tree search depth.

See

MaxDepth

enumerator SearchLimitedByTime

Search has been limited by time.

See

MaxComputationTime

enumerator SearchLimitedByBacktracks

Search has been limited by maximum number of backtracks.

See

MaxNumberOfBackTracks

enumerator SearchLimitedByNodesBetweenSolutions

Search has been limited by maximum nodes between two solutions.

See

MaxNumberOfNodesBetweenSolutions

enumerator SearchLimitedByUser

Search has been limited by user.

enum ToleranceLimitAttrib

Tolerance limits attributes

Values:

enumerator ToleranceLimitUnreached

Tolerance limit has not been reached.

enumerator OptimalityToleranceReached

Optimality absolute tolerance has been reached.

See

OptimalityTolerance

enumerator OptimalityRelativeToleranceReached

Optimality relative tolerance has been reached.

See

OptimalityRelativeTolerance

enum IntAttrib

Integer attributes

Values:

enumerator NumberOfNodes

Number of nodes explored.

enumerator Depth

Depth of the search tree.

enumerator SearchLimitReached

Limit reached during resolution.

See

SearchLimitAttrib

enumerator ToleranceLimitReached

Tolerance limit reached during resolution.

See

ToleranceLimitAttrib

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.

enum DblAttrib

Double attributes

Values:

enumerator ComputationTime

Total computation time.

enumerator BestBound

Best bound on the optimal solution.

enumerator CallBackTime

Time spent in callbacks.

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 n-ary search on objective interval (available for multi-threaded optimization only).

enumerator NumberOfSolutionBetweenRestarts

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

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).

Public Functions

KSolver()

Default constructor

KSolver(KProblem &problem)

Constructor

Parameters

problem – the problem to solve

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

KSolver(const KSolver &toCopy)

CopyConstructor

virtual ~KSolver()

Destructor

KProblem *getProblem() const

Get the KProblem instance

int solve()

Search for a solution to the problem

See

IntControl DblControl

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

NumberOfSolutionBetweenRestarts)

See

OptimizationAlgorithm)

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

IntAttrib

Parameters

attrib – the integer attribute to retrieve

double getDblAttrib(KSolver::DblAttrib attrib)

Return a double attribute of the solver.

See

DblAttrib

Parameters

attrib – the double attribute to retrieve

int getIntControl(KSolver::IntControl control)

Return the value of an int control

See

IntControl

Parameters

control – integer control to retrieve

double getDblControl(KSolver::DblControl control)

Return the value of a double control

See

DblControl

Parameters

control – double control to retrieve

void setIntControl(KSolver::IntControl control, int value)

Set the value of an int control

See

IntControl

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

DblControl

Parameters
  • control – tjhe double control to set

  • value – value of the control

void setNodeFunctionPtr(KalisCallBackFunctionPtr ptr, void *param)

Deprecated:
Set the node explored function ptr
See

setSolverEventListener

Parameters
  • ptr – function pointer

  • param – user parameter passed to the function when called

void setBranchFunctionPtr(KalisCallBackFunctionPtr ptr1, KalisCallBackFunctionPtr ptr2, void *param)

Deprecated:
Set the branch explored function ptr (called each time a branch is explored)
See

setSolverEventListener

Parameters
  • ptr – function pointer

  • param – user parameter passed to the function when called

void setBranchingSchemeFunctionPtr(KalisCallBackFunctionPtr ptr1, void *param)

Deprecated:
Set the Branching scheme switch function ptr
See

setSolverEventListener

Parameters
  • ptr – function pointer

  • param – user parameter passed to the function when called

void setSolutionFunctionPtr(KalisCallBackFunctionPtr ptr, void *param)

Deprecated:
Set the solution function ptr (called each time a solution is found)
See

setSolverEventListener

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

See

KSolverEventListener

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