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.

enumerator ClearExistingSolutions¶: Control to clear or not the existing solutions before an optimization: 1 for yes (default), 0 for no.

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