GHOST helps you define your own CSP/COP/EF-CSP/EF-COP model (please refer to Part 3 A short Constraint Programming tutorial is those terms are mysterious to you). To do so, you need to implement your own constraints, one class by constraint type, by inheriting from ghost::Constraint. If you are modeling an optimization problem, you need to implement your objective function with a class inheriting from ghost::Objective. You will also need to implement a class to declare your model, i.e., to declare your variables, their domains, your constraints and eventually your objective function, by inheriting from ghost::ModelBuilder.

Let's take the knapsack example of Part 3. As a reminder, this problem is about selecting objects with the highest total value, while respecting a capacity constraint. We will model together a CSP, COP, EF-CSP and EF-COP version of this problem. The code below can be found in the tutorial/wiki folder.

We need a constraint to ensure that the knapsack's capacity is not exceeded. Let's define our own constraint Capacity.

// constraint_capacity.hpp

class Capacity : public ghost::Constraint
{
  // Suppose we have a class ObjectData storing 
  // the size and the value of each object type.
  std::vector<double> _object_size;
  int _capacity;
  
  double required_error( const std::vector<ghost::Variable*>& variables ) const override;
	
public:
  Capacity( const std::vector<ghost::Variable>& variables,
            const std::vector<double>&& object_size,
            int capacity );
}

When you write a class inheriting from a ghost class, each function starting by required_ must be overridden. In ghost::Constraint, there is only one such function:

double ghost::Constraint::required_error( const std::vector<ghost::Variable*>& variables ) const;

This function must returns 0 when the current value of our variables satisfies the constraint, and 1 otherwise. Here, our constraint is satisfied if and only if the sum of the size of each object type (_object_size[i]) times the number of these objects we are taking with us (variables[i]->.get_value()) is less than or equal to the knapsack capacity.

// constraint_capacity.cpp

Capacity::Capacity( const std::vector<ghost::Variable>& variables,
                    const std::vector<double>&& object_size,
                    int capacity )
  : Constraint( variables ),
    _object_size( std::move( object_size ) ),
    _capacity( capacity )
{ }

double Capacity::required_error( const std::vector<ghost::Variable*>& variables ) const
{
  double total_size = 0.0;

  for( size_t i = 0 ; i < variables.size() ; ++i )
    total_size += ( variables[i]->get_value() * _object_size[i] );

  if( total_size <= _capacity )
    return 0.0;
  else
    return 1.0;
}

And that's it for this constraint! We almost have our CSP model of the knapsack problem. Indeed, the decision version of this problem consists in checking if it is possible to bring objects with us reaching at least a total value target, with target given as a parameter. So we need a second constraint checking we are reaching at least this target value.

// at_least.hpp

class AtLeast : public ghost::Constraint
{
  std::vector<double> _object_value;
  double _target;
  
  double required_error( const std::vector<ghost::Variable*>& variables ) const override;
	
public:
  AtLeast( const std::vector<ghost::Variable>& variables,
           const std::vector<double>&& object_value,
           double target );
}

// at_least.cpp

AtLeast::AtLeast( const std::vector<ghost::Variable>& variables,
                  const std::vector<double>&& object_value,
                  double target )
  : Constraint( variables ),
    _object_value( std::move( object_value ) ),
    _target( target )
{ }

double AtLeast::required_error( const std::vector<ghost::Variable*>& variables ) const
{
  double total_value = 0.0;

  for( size_t i = 0 ; i < variables.size() ; ++i )
    total_value += ( variables[i]->get_value() * _object_value[i] );

  if( total_value >= _target )
    return 0.0;
  else
    return 1.0;
}

Finally, we need a class describing how to declare our model

// model_builder.hpp
class TutorialBuilder : public ghost::ModelBuilder
{
public:
	TutorialBuilder();

	void declare_variables() override;
	void declare_constraints() override;
};

// model_builder.cpp
TutorialBuilder::TutorialBuilder()
	: ModelBuilder()
{ }

void TutorialBuilder::declare_variables()
{
	variables.emplace_back( 0, 51, std::string("bottle") );
	variables.emplace_back( 0, 11, std::string("sandwich") );	
}

void TutorialBuilder::declare_constraints()
{
	constraints.emplace_back( std::make_shared<Capacity>( variables, std::vector<double>{1, 1.25}, 30 ) );
	constraints.emplace_back( std::make_shared<AtLeast>( variables, std::vector<double>{500, 650}, 15000 ) );
}

There are several ways to declare varibles. Here, we use the constructor ghost::Variable::Variable(int starting_value, size_t size, const std::string& name). Despite the facultative name of the variable, this constructor takes the first value of the domain, here 0 for both variables, and the number n of elements in their domain. Thus, GHOST will instantiate domains with all natural numbers from 0 to n-1.

It's exactly the same Capacity constraint as defined in the CSP version. We do not care about the AtLeast constraint in the COP since the goal is to find the combination of objects maximizing the total value.

To implement our objective function, we need to write a class inheriting either from ghost::Maximize or ghost::Minimize, to express maximization and minimization problems, respectively, and to override the required_cost function.

Notice that functions in ghost::Maximize and ghost::Minimize starting by expert_ can also be overridden, but we advice to do so only if you know exactly how GHOST's solver works.

Let's implement our objective MaxValue

// max_value.hpp

class MaxValue : public ghost::Maximize
{
  std::vector<double> _object_value;

  double required_cost( const std::vector< ghost::Variable*>& ) const override;
public:
  MaxValue( const std::vector<ghost::Variable>&, const std::vector<double>&& object_value );
}

// max_value.cpp

MaxValue::MaxValue( const std::vector<ghost::Variable>& variables,
                    const std::vector<double>&& object_value )
	: Maximize( variables, "Max value" ),
	  _object_value( std::move( object_value ) )
{ }

double MaxValue::required_cost( const std::vector< ghost::Variable*>& variables ) const
{
  double total_value = 0.0;

  for( size_t i = 0; i < variables.size(); ++i )
    total_value += ( variables[i]->get_value() * _object_value[i] );

  return total_value;
}

We can conceder that MaxValue in the COP model somehow replaces the constraint AtLeast in the CSP model. You can notice that MaxValue::required_cost is then very similar to AtLeast::required_error.

Compare to the CSP version, we need here to only declare the constraint Capacity and to declare the objective function MaxValue. Variable declarations are unchanged.

// model_builder.hpp
class TutorialBuilder : public ghost::ModelBuilder
{
public:
	TutorialBuilder();

	void declare_variables() override;
	void declare_constraints() override;
	void declare_objective() override;
};

// model_builder.cpp
TutorialBuilder::TutorialBuilder()
	: ModelBuilder()
{ }

void TutorialBuilder::declare_variables()
{
	variables.emplace_back( 0, 51, std::string("bottle") );
	variables.emplace_back( 0, 11, std::string("sandwich") );	
}

void TutorialBuilder::declare_constraints()
{
	constraints.emplace_back( std::make_shared<Capacity>( variables, std::vector<double>{1, 1.25}, 30 ) );
}

void TutorialBuilder::declare_objective()
{
	objective = std::make_shared<MaxValue>( variables, std::vector<double>{500, 650} );
}

We need to slightly change the implementation of Capacity::required_error():

• it must return 0 if the constraint is satisfied,
• otherwise, it must return a value strictly greater than 0, so the more the knapsack's capacity is exceeded, the higher the value.

For instance, we can recode Capacity::required_error() like this:

double Capacity::required_error( const std::vector<ghost::Variable*>& variables ) const
{
  double total_size = 0.0;

  for( size_t i = 0 ; i < variables.size() ; ++i )
    total_size += ( variables[i]->get_value() * _object_size[i] );
		
  return std::max( 0., total_size - _capacity );
}

And it's done if we want to model the knapsack problem in its regular optimization version. If we want to model the satisfaction version of this problem, we need to slightly recode AtLeast::required_error() in the same fashion we recode Capacity::required_error():

double AtLeast::required_error( const std::vector<ghost::Variable*>& variables ) const
{
  double total_value = 0.0;

  for( size_t i = 0 ; i < variables.size() ; ++i )
    total_value += ( variables[i]->get_value() * _object_value[i] );

  return std::max( 0., _target - total_value );
}

The TutorialBuilder class is exactly the same one as for the CSP model.

We just have to take the Capacity class defined for the EF-CSP version, and not consider the AtLeast class, like for the COP model.

MaxValue and TutorialBuilder classes are exactly the same ones as for the COP model.

The main program is exactly the same for a CSP, a COP, an EF-CSP or an EF-COP model.

Writing a main program is very short and easy thanks to the problem declaration done in a model builder. To call GHOST's solver on their problem model, users just have to declare a ghost::ModelBuilder object and give it as a parameter while declaring the ghost::Solver object. After declaring two variables to get the best cost found and its solution vector, users just have to call Solver::fast_search() passing these variables cost and solution, as well as a timeout, i.e., a time budget allocated to the solver to find a solution.

For decision problems, the solver stops as soon as it finds a solution, giving the value 0 to the cost variable and the value of each variables of the problem into the solution vector. In that case, Solver::fast_search() returns the value true. If it was not able to find a solution within the time budget, it gives the satisfaction error of the best candidate found to cost and the value of this candidate into solution, and returns false.

For optimization problems, the solver has the same behavior, except that it will look for a better solution until the timeout is reached. If a solution has been found, cost will contain the optimization cost of the best solution found. Otherwise, it will contain the satisfaction error of the best candidate found.

  // Declaring the model builder
	TutorialBuilder builder;
	
	// Defining the solver and calling it
	ghost::Solver solver( builder );

	double cost;
	std::vector<int> solution;

	// Run the solver with a 500 microseconds budget
	bool found = solver.fast_search( cost, solution, 500us );
	
	// After 500 microseconds, the solver will write in cost and solution the best solution it has found.
	found ? std::cout << "Solution found\n" : std::cout << "Solution not found\n";
	std::cout << "Cost: " << cost << "\nSolution:";
	for( auto v : solution )
		std::cout << " " << v;
	std::cout << "\n";