GHOST
|
#include <constraint.hpp>
Public Member Functions | |
Constraint (const std::vector< int > &variables_index) | |
Constraint (const std::vector< Variable > &variables) | |
Constraint (const Constraint &other)=default | |
Default copy contructor. More... | |
Constraint (Constraint &&other)=default | |
Default move contructor. More... | |
Constraint & | operator= (const Constraint &other)=delete |
Copy assignment operator disabled. More... | |
Constraint & | operator= (Constraint &&other)=delete |
Move assignment operator disabled. More... | |
virtual | ~Constraint ()=default |
Default virtual destructor. More... | |
bool | has_variable (int var_id) const |
Protected Member Functions | |
virtual double | required_error (const std::vector< Variable * > &variables) const =0 |
virtual double | optional_delta_error (const std::vector< Variable * > &variables, const std::vector< int > &indexes, const std::vector< int > &candidate_values) const |
virtual void | conditional_update_data_structures (const std::vector< Variable * > &variables, int index, int new_value) |
double | get_current_error () const |
int | get_id () const |
Inline method to get the unique id of the Constraint object. More... | |
This is the base class from which users need to derive their Constraint classes.
ghost::Constraint cannot be directly used to encode user-defined constrains, since this is an abstract class. To declare a problem with GHOST, users have to make their own derived constraint classes.
ghost::Constraint::Constraint | ( | const std::vector< int > & | variables_index | ) |
Constructor with a vector of variable IDs. This vector is internally used by Constraint to know what variables from the global variable vector it is handling.
variables | a const reference to a vector of IDs of variables composing the constraint. |
ghost::Constraint::Constraint | ( | const std::vector< Variable > & | variables | ) |
Constructor building a vector of variable IDs by calling v->get_id() from all variables v.
variables | a const reference to a vector of variable composing the constraint. |
|
default |
Default copy contructor.
|
default |
Default move contructor.
|
virtualdefault |
Default virtual destructor.
|
protectedvirtual |
Update user-defined data structures in the constraint.
Like any methods prefixed by 'conditional_', this method must be overriden under some conditions: if some inner data structures are defined in derived constraint classes and need to be updated while variable values change (i.e., when the solver asssign 'new_value' to variables[index]), this method must be implemented to define how data structures must be updated.
variables | a const reference of the vector of raw pointers to variables of the constraint. |
index | an integer to get the variable 'variables[index]' that has been updated by the solver. |
new_value | an integer to know what is the new value of 'variables[index]'. |
Reimplemented in ghost::global_constraints::LinearEquation.
|
inlineprotected |
Inline method returning the current error of the constraint (automatically updated by the solver). This can be helpful for implementing optional_delta_error.
|
inlineprotected |
Inline method to get the unique id of the Constraint object.
bool ghost::Constraint::has_variable | ( | int | var_id | ) | const |
Determine if the constraint contains a variable given its id.
var_id | an integer being a variable ID |
|
delete |
Copy assignment operator disabled.
|
delete |
Move assignment operator disabled.
|
protectedvirtual |
Virtual method to compute the difference, or delta, between the current error and the error of a candidate assignment.
The current assignment, as well as its error, are automatically stored in the class Constraint. Giving a vector of variable indexes and their respective candidate value, this methods ouputs the difference between the error of the current assignment in 'variables' given as input and the error we would get if we assign new candidate values.
The ouput can be negative, positive, or equals to 0. If the candidate error is strictly lower (then better) than the current error, the ouput is negative. If errors are the same, the ouputs equals to 0. Finally, if the candidate error is strictly higher (then worst) than the current error, the ouput is positive.
For EF-CSP/EF-COP models, this method can be VERY important to have faster computation. Although optional (the solver still works without it), we strongly advise users to define it properly, unless the overridden required_error method is trivial to compute. Having this method may make a big difference for the solver to quickly find better solutions. However, if the problem is modeled as an CSP/COP, users can just skip the implementation of this method.
Like any methods prefixed by 'optional_', overriding this method is not mandatory.
variables | a const reference of the vector of raw pointers of variables in the scope of the constraint. The solver is actually calling this method with the vector of variables that has been given to the constructor. |
indexes | the vector of indexes of variables that are reassigned. |
candidate_values | the vector of their respective candidate values. |
Throws | an exception if the computed value is NaN. |
Reimplemented in ghost::global_constraints::LinearEquation.
|
protectedpure virtual |
Pure virtual method to compute the error of the constraint regarding the values of variables given as input.
This method is fundamental: as a predicate, it evalutes if the given values of variables violate this contraint, and as an error function, it evaluates how much.
Let's consider the following example to understand error functions: consider the contraint (x = y).
If x = 42 and y = 42, then these values satify the contraint. The error is then 0.
If x = 42 and y = 40, the constraint is not satified, but intuitively, we are closer to have a solution than with x = 42 and y = 10,000. Thus the error when y = 40 must be strictly lower than the error when y = 10,000.
Thus, a required_error candidate for the contraint (x = y) could be the function |x-y|.
This method MUST returns a value greater than or equals to 0.
Users have the choice: while modeling CSP or COP problems, required_error must implement the logic of a predicate and should outputs 0 if current values of variables satisfy the user-defined constraint, and something strictly higher than 0 otherwise, like 1 for instance.
While modeling EF-CSP/EF-COP problems, required_error needs to express an error function. It still must outputs 0 for satisfying values of variables, but must outputs a value strictly higher than 0 otherwise, such that the higher this value, the further current values of variables are from satisfying the user-defined constraint.
Like any methods prefixed by 'required_', overriding this method is mandatory.
variables | a const reference of the vector of raw pointers to variables in the scope of the constraint. The solver is actually calling this method with the vector of variables that has been given to the constructor. |
Throws | an exception if the computed value is negative or is NaN. |
Implemented in ghost::global_constraints::LinearEquation.