constraint.hpp

Go to the documentation of this file.

/*
 * GHOST (General meta-Heuristic Optimization Solving Tool) is a C++ framework
 * designed to help developers to model and implement optimization problem
 * solving. It contains a meta-heuristic solver aiming to solve any kind of
 * combinatorial and optimization real-time problems represented by a CSP/COP/EF-CSP/EF-COP. 
 *
 * First developed to solve game-related optimization problems, GHOST can be used for
 * any kind of applications where solving combinatorial and optimization problems. In
 * particular, it had been designed to be able to solve not-too-complex problem instances
 * within some milliseconds, making it very suitable for highly reactive or embedded systems.
 * Please visit https://github.com/richoux/GHOST for further information.
 *
 * Copyright (C) 2014-2023 Florian Richoux
 *
 * This file is part of GHOST.
 * GHOST is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published
 * by the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * GHOST is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with GHOST. If not, see http://www.gnu.org/licenses/.
 */
 
 
#pragma once
 
#include <vector>
#include <map>
#include <utility>
#include <iostream>
#include <typeinfo>
#include <functional>
#include <cmath> // for isnan
#include <exception>
#include <string>
 
#include "variable.hpp"
 
namespace ghost
{
    namespace algorithms
    {
        class AdaptiveSearchErrorProjection;
        class CulpritSearchErrorProjection;
    }
 
    class Constraint
    {
        friend class SearchUnit;
        template<typename ModelBuilderType> friend class Solver;
        friend class ModelBuilder;
        friend class algorithms::AdaptiveSearchErrorProjection;
        friend class algorithms::CulpritSearchErrorProjection;
 
        std::vector<Variable*> _variables;
        std::vector<int> _variables_index; // To know where are the constraint's variables in the global variable vector
        std::map<int,int> _variables_position; // To know where are global variables in the constraint's variables vector 
 
        double _current_error; // Current error of the constraint.
 
        int _id; // Unique ID integer
        mutable bool _is_optional_delta_error_defined; // Boolean telling if optional_delta_error() is overrided or not.
 
        struct nanException : std::exception
        {
            std::vector<Variable*> ptr_variables;
            std::vector<Variable> variables;
            std::string message;
 
            nanException( const std::vector<Variable*>& ptr_variables ) : ptr_variables(ptr_variables)
            {
                message = "Constraint required_error returned a NaN value on variables (";
                for( int i = 0; i < static_cast<int>( ptr_variables.size() ) - 1; ++i )
                    message += std::to_string( ptr_variables[i]->get_value() ) + ", ";
                message += std::to_string( ptr_variables[ static_cast<int>( ptr_variables.size() ) - 1 ]->get_value() ) + ")\n";
            }
 
            nanException( const std::vector<Variable>& variables ) : variables(variables)
            {
                message = "Constraint optional_delta_error returned a NaN value on variables (";
                for( int i = 0; i < static_cast<int>( variables.size() ) - 1; ++i )
                    message += std::to_string( variables[i].get_value() ) + ", ";
                message += std::to_string( variables[ static_cast<int>( variables.size() ) - 1 ].get_value() ) + ")\n";
            }
 
            const char* what() const noexcept { return message.c_str(); }
        };
 
        struct negativeException : std::exception
        {
            std::vector<Variable*> ptr_variables;
            std::vector<Variable> variables;
            std::string message;
 
            negativeException( const std::vector<Variable*>& ptr_variables ) : ptr_variables(ptr_variables)
            {
                message = "Constraint required_error returned a negative value on variables (";
                for( int i = 0; i < static_cast<int>( ptr_variables.size() ) - 1; ++i )
                    message += std::to_string( ptr_variables[i]->get_value() ) + ", ";
                message += std::to_string( ptr_variables[ static_cast<int>( ptr_variables.size() ) - 1 ]->get_value() ) + ")\n";
            }
 
            const char* what() const noexcept { return message.c_str(); }
        };
 
        struct deltaErrorNotDefinedException : std::exception
        {
            std::string message;
 
            deltaErrorNotDefinedException()
            {
                message = "Constraint::optional_delta_error() has not been user-defined.\n";
            }
            const char* what() const noexcept { return message.c_str(); }
        };
 
        struct variableOutOfTheScope : std::exception
        {
            std::string message;
 
            variableOutOfTheScope( int var_id, int ctr_id )
            {
                message = "Variable* ID " + std::to_string( var_id ) + " is not in the scope of Constraint ID " + std::to_string( ctr_id ) + ".\n";
            }
            const char* what() const noexcept { return message.c_str(); }
        };
 
        inline bool is_optional_delta_error_defined() { return _is_optional_delta_error_defined; }
 
        // Call required_error() after getting sure the error does give a nan, rise an exception otherwise.
        double error() const;
 
        // Compute the delta error of the current assignment, giving a vector of variables index and their candidate values.
        // Calling optional_delta_error after making the conversion of variables index.
        // Getting sure the delta error does give a nan, rise an exception otherwise.
        double delta_error( const std::vector<int>& variables_index, const std::vector<int>& candidate_values ) const;
 
        // To simulate the error delta between the current configuration and the candidate configuration.
        // This calls delta_error() if the user overrided it, otherwise it makes the simulation 'by hand' and calls error()
        double simulate_delta( const std::vector<int>& variables_index, const std::vector<int>& candidate_values );
 
        // Return ids of variable objects in _variables.
        inline std::vector<int> get_variable_ids() const { return _variables_index; }
 
        inline void update( int index, int new_value ) { conditional_update_data_structures( _variables, _variables_position[ index ], new_value ); }
 
    protected:
        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 );
 
        inline double get_current_error() const { return _current_error; }
 
        inline int get_id() const { return _id; }
 
    public:
        Constraint( const std::vector<int>& variables_index );
 
        Constraint( const std::vector<Variable>& variables );
 
        Constraint( const Constraint& other ) = default;
        Constraint( Constraint&& other ) = default;
 
        Constraint& operator=( const Constraint& other ) = delete;
        Constraint& operator=( Constraint&& other ) = delete;
 
        virtual ~Constraint() = default;
 
        bool has_variable( int var_id ) const;
 
        friend std::ostream& operator<<( std::ostream& os, const Constraint& c )
        {
            return os << "Constraint type: " <<  typeid(c).name()
                      << "\nId: " <<  c._id
                      << "\n########";
        }
    };
 
    /**********************/
    /**********************/
    // PureOptimization is used when no constraints have been given to the solver (ie, for pure optimization runs). 
    class PureOptimization : public Constraint
    {
        double required_error( const std::vector<Variable*>& variables ) const
        {
            return 0.;
        }
 
        double optional_delta_error( const std::vector<Variable*>& variables, const std::vector<int>& indexes, const std::vector<int>& candidate_values ) const
        {
            return 0.;
        }
 
    public:
        PureOptimization( const std::vector<Variable>& variables )
            : Constraint( variables )
        { }
    };
 
}