#include <solver.hpp>
Public Member Functions | |
| Solver (const ModelBuilderType &model_builder) | |
| bool | fast_search (double &final_cost, std::vector< int > &final_solution, double timeout, Options &options) |
| bool | fast_search (double &final_cost, std::vector< int > &final_solution, double timeout) |
| bool | fast_search (double &final_cost, std::vector< int > &final_solution, std::chrono::microseconds timeout, Options &options) |
| bool | fast_search (double &final_cost, std::vector< int > &final_solution, std::chrono::microseconds timeout) |
| bool | complete_search (std::vector< double > &final_costs, std::vector< std::vector< int >> &final_solutions, Options &options) |
| bool | complete_search (std::vector< double > &final_costs, std::vector< std::vector< int >> &final_solutions) |
| std::vector< Variable > | get_variables () |
Detailed Description
template<typename ModelBuilderType>
class ghost::Solver< ModelBuilderType >
Solver is the class coding the solver itself.
To solve a problem instance, users must instanciate a Solver object, then run Solver::fast_search. This will search for a good quality solution within a given timeout. If all solutions of a problem are required, or if the optimality of the solution must be certified, then users can run Solver::complete_search instead. Notice that this will run a significantly slower search method and is only viable on small problem instances.
The unique Solver constructor needs a derived ghost::ModelBuilder object, as well as an optional boolean indicating if the solver is dealing with a permutation problem, i.e., if the solver needs to swap variable values instead of picking new values from domains.
Declaring combinatorial problems as permutation problems can lead to a huge performance boost for the solver. For this, the problem needs to be declared with all variables starting with a value that belongs to a solution.
This is typically the case for scheduling problems, for instance: imagine we want to do three tasks A, B and C. Thus, we give A as the starting value to the first variable, B to the second and C to the third. Then, instead of assigning the task A to the second variable for instance, the solver will swap tasks of the first and the second variables.
Users are invited to model as much as possible their problems as permutation problems, since it would greatly speed-up the search of solutions.
Many options compiled in a ghost::Options object can be passed to methods Solver::fast_search / Solver::complete_search, to allow for instance parallel computing, as well as parameter tweaking for local search experts.
ghost::Solver is a template class, although users should never need to instantiate the template with modern C++ compilers.
- See also
- ModelBuilder, Options
Constructor & Destructor Documentation
◆ Solver()
|
inline |
Unique constructor of ghost::Solver
- Parameters
-
model_builder a const reference to a derived ModelBuilder object. permutation_problem a boolean indicating if the solver will work on a permutation problem. False by default.
Member Function Documentation
◆ complete_search() [1/2]
|
inline |
Call Solver::complete_search with default options.
Users should favor this Solver::complete_search method if they want default options.
- Parameters
-
final_costs a reference to a vector of double to get the errors of all solutions for satisfaction problems, or their objective function value for optimization problems For satisfaction problems, a cost of zero means a solution has been found. final_solutions a reference to a vector of vector of integers, containing all solutions of the problem instance.
- Returns
- True if and only a solution of the problem exists.
◆ complete_search() [2/2]
|
inline |
Method to look for all solutions of a given CSP/COP/EF-CSP/EF-COP model.
This method returns true if at least one solution of the problem exists, and flase otherwise. It will write the error/cost of all solutions in the final_costs parameter, and all solutions themselves in the final_solutions parameter.
For a satisfaction problem (without any objective function), the error of a candidate is the sum of the error of each problem constraint (computated by Constraint::required_error). For an optimization problem, the cost is the value outputed by Objective::required_cost.
For both, the lower value the better: A satisfaction error of 0 means we have a solution to a satisfaction problem (ie, all constraints are satisfied). An optimization cost should be as low as possible: GHOST is always trying to minimize problems. If you have a maximization problem, GHOST will automatically convert it into a minimization problem.
Finally, options to change the solver behaviors (parallel runs, user-defined solution printing) can be given as a last parameter.
- Parameters
-
final_costs a reference to a vector of double to get the errors of all solutions for satisfaction problems, or their objective function value for optimization problems For satisfaction problems, a cost of zero means a solution has been found. final_solutions a reference to a vector of vector of integers, containing all solutions of the problem instance. options a reference to an Options object containing options such as parallel runs, a solution printer, etc.
- Returns
- True if and only a solution of the problem exists.
◆ fast_search() [1/4]
|
inline |
Call Solver::fast_search with default options.
- Parameters
-
final_cost a reference to a double to get the error of the best candidate or solution for satisfaction problems, or the objective function value of the best solution for optimization problems (or the cost of the best candidate if no solution has been found). For satisfaction problems, a cost of zero means a solution has been found. final_solution a reference to a vector of integers, to get values of the best candidate or solution found. timeout a double for the time budget allowed to the solver to find a solution, in microseconds.
- Returns
- True if and only if a solution has been found.
◆ fast_search() [2/4]
|
inline |
Method to quickly solve the given CSP/COP/EF-CSP/EF-COP model. Users should favor the two versions of Solver::fast_search taking a std::chrono::microseconds value as a parameter.
This method is the heart of GHOST's solver: it will try to find a solution within a limited time. If it finds such a solution, the function outputs the value true.
Here how it works: if at least one solution is found, at the end of the computation, it will write in the two first parameters final_cost and final_solution the error/cost of the best candidate or solution found and the value of each variable.
For a satisfaction problem (without any objective function), the error of a candidate is the sum of the error of each problem constraint (computated by Constraint::required_error). For an optimization problem, the cost is the value outputed by Objective::required_cost.
For both, the lower value the better: A satisfaction error of 0 means we have a solution to a satisfaction problem (ie, all constraints are satisfied). An optimization cost should be as low as possible: GHOST is always trying to minimize problems. If you have a maximization problem, GHOST will automatically convert it into a minimization problem.
The timeout parameter is fundamental: it represents a time budget, in microseconds, for the solver. The behavior will differ from satisfaction and optimization problems.
For satisfaction problems modeled with an CSP or EF-CSP, the solver stops as soon as it finds a solution. Then, it outputs 'true', writes 0 into the final_cost variable and the values of the variables composing the solution into the final_solution vector.
If no solutions are found within the timeout, the solver stops, outputs 'false', writes in final_cost the error of the best candidate found during the search (i.e., the candidate being the closest from a solution) and writes the best candidate's values into the final_solution vector.
For optimization problems modeled with an COP or EF-COP, the solver will always continue running until reaching the timeout. If a solution is found, it outputs 'true' and writes into the final_cost variable the cost of the best solution optimizating the given objective function. It also writes the values of the solution into the final_solution vector.
If no solutions are found, the solver outputs 'false' and adopt the same behavior as not finding a solution for satisfaction problems.
Finally, options to change the solver behaviors (parallel runs, user-defined solution printing, user-defined starting candidate, parameter tweaking, etc) can be given as a last parameter.
- Parameters
-
final_cost a reference to a double to get the error of the best candidate or solution for satisfaction problems, or the objective function value of the best solution for optimization problems (or the cost of the best candidate if no solution has been found). For satisfaction problems, a cost of zero means a solution has been found. final_solution a reference to a vector of integers, to get values of the best candidate or solution found. timeout a double for the time budget allowed to the solver to find a solution, in microseconds. options a reference to an Options object containing options such as parallel runs, a solution printer, if the solver must start with a custom variable assignment, parameter tuning, etc.
- Returns
- True if and only if a solution has been found.
◆ fast_search() [3/4]
|
inline |
Call Solver::fast_search with a chrono literal timeout in microseconds and default options.
Users should favor this Solver::fast_search method if they want default options.
- Parameters
-
final_cost a reference to a double to get the error of the best candidate or solution for satisfaction problems, or the objective function value of the best solution for optimization problems (or the cost of the best candidate if no solution has been found). For satisfaction problems, a cost of zero means a solution has been found. final_solution a reference to a vector of integers, to get values of the best candidate or solution found. timeout a std::chrono::microseconds for the time budget allowed to the solver to find a solution. Higher std::chrono durations (such as milliseconds, seconds, etc) would be automatically converted into microseconds.
- Returns
- True if and only if a solution has been found.
◆ fast_search() [4/4]
|
inline |
Call Solver::fast_search with a chrono literal timeout in microseconds.
Users should favor this Solver::fast_search method if they need to give the solver user-defined options.
- Parameters
-
final_cost a reference to a double to get the error of the best candidate or solution for satisfaction problems, or the objective function value of the best solution for optimization problems (or the cost of the best candidate if no solution has been found). For satisfaction problems, a cost of zero means a solution has been found. final_solution a reference to a vector of integers, to get values of the best candidate or solution found. timeout a std::chrono::microseconds for the time budget allowed to the solver to find a solution. Higher std::chrono durations (such as milliseconds, seconds, etc) would be automatically converted into microseconds. options a reference to an Options object containing options such as parallel runs, a solution printer, if the solver must start with a custom variable assignment, parameter tuning, etc.
- Returns
- True if and only if a solution has been found.
◆ get_variables()
|
inline |
Method to get the variables in the model. This method can be handy in some situations, if users do not know what the variables composing their problem instance are, and need them number in their programs.
- Returns
- A vector of the Variable objects composing the model variables.
The documentation for this class was generated from the following file:
