Skip to content
Florian Richoux edited this page Jul 31, 2023 · 2 revisions

No Promises of finding a solution in time

GHOST contains a solver based on meta-heuristics. Meta-heuristics are powerful algorithms able to quickly solve large optimization problem instances. In addition, there are anytime, meaning that when you stop their run, they are able to output the best solution or candidate they found so far.

However, please keep in mind that GHOST cannot certify finding a solution of a problem within the timeout you gave to it. One major draw back with metaheuristics is that these algorithms are not able to show no solutions exist (if your problem is overconstrained), neither finding the optimal solution, nor finding all solutions of a problem. If you need such features, GHOST won't be the right tool for you.

Several, simple constraints are better than a big, monolithic one.

Keep in mind that it is always better to break down a large constraint into several smaller constraints. If your constraint takes a lot of variables within its scope and has a complex or long implementation of Constraint::required_error(), then look if you can divide it into an equivalent group of smaller constraints.

Give your constraints the minimal required scope of variables

Your constraint constructors are waiting for a vector of variables as a parameter. This vector is called the scope of your constraint. To allow GHOST's solver working at its top potential, keep in mind you always have to keep this scope as small as possible. In your model builder, give to your constructors a vector only containing variables they absolutely need.

Implement methods starting by expert_ only if you know what you are doing

GHOST's interface has been designed to be as simple to use as possible. Users have to implement all methods starting by required_, and everything should be working fine if they are properly coded. To reach better performances, GHOST's interface also let users to defined their own implementation of methods starting by expert_, but this implies having a good understanding of how GHOST's solver is working. Keep in mind you are not expect to implement expert_ methods if you don't know what you are doing.

Never write side effects

GHOST begin a framework, all methods you implement would be called by the solver in some way that are intentionally hidden from users. Do not write any side effects in your implementations.

Favor error functions over predicates

GHOST allow to model your constraints as error functions or predicates. Predicates are the canonical constraint representation in Constraint Programming and are simpler than error functions to model, giving you CSP and COP models.

To do so, you should implement Constraint::required_error() such that it outputs 0 if the given variables have an allowed combination of values, and a strictly positive value (such as 1) otherwise. We strongly advise to use the same strictly positive value for all your predicates, unless you intentionnaly want to model weighted constraint-based problems.

However to get far better performances, we strongly advice users to model their constraints as error functions (leading to EF-CSP and EF-COP models). For this, Constraint::required_error() must outputs a positive value representing how far the given combination of variable values is to satisfy the constraint. If it satisfies it, the output must be 0. Otherwise, the more violated the constraint is, the higher the output must be. Error functions are by nature harder to model than predicates, but keep in mind you should try to represent your constraints with error functions as often as possible.

Read the documentation

GHOST's interface has been extensively documented. Do not hesitate to look at the documentation if you have questions about a method: richoux.github.io/GHOST/